Daylight v4.9
Release Date: 1 February 2008


ares - approximate regular-expression search




This file documents the Daylight ARES utility, a regular expression matcher with the capability of doing approximate matching. Although ARES was primarily designed for the Merlin server, ARES is likely to be used in other components of the Daylight software. This document is intended to be an authoritative ARES reference for all such applications. End users are likely to find sections 1-6 most useful.

ARES implements a very general form of string searching: approximate regular expression matching. Since a regular expression can represent a simple string, ARES provides the ability to do approximate matching of simple strings. One can also use ARES for exact matching of strings or regular expressions by setting the number of allowable errors to zero. (However, faster methods are available for exact string matching.)

Approximate string searching differs from conventional string searching several important ways. Most importantly, strings are defined to match a pattern even if they don't match the pattern exactly, i.e., the string matches the pattern with a certain number of "errors". With ARES, each character insertion, deletion, or substitution counts as one error. For instance, if you use ARES to look for names containing "PARACETIMAL", names containing "PARACETAMOL" will be found with 2 (substitution) errors.

ARES allows you to specify parts of the pattern which must be matched exactly by enclosing them in angle brackets, e.g., the pattern "HYDRONOL" matches HYDROKON with two errors, but the pattern "HYDRON<OL>" will not match HYDROKON at any error level, since "OL" is required exactly.

With approximate string searching, one tends to look for complete strings (as opposed to substrings) more often than one does with exact matching. For instance, when looking for the name "ALUMINUM", you might wish to also find the name "ALUMINIUM" (British spelling?) but not "ALUMINIUM CHLORIDE". Although one can do this with a simple regular expression (^ALUMINUM$), ARES provides an simple option to search for "whole" strings.

ARES accepts patterns written as regular expressions. Although regular expressions allow complex patterns to be specified, the concept of insertion, deletion, and substitution errors is just as valid as with simple string patterns. More information on ARES' regular expression language may be found below.


The user interface is implementation-dependent, but generally will consist of following elements:

- User input area: enter string or regular expression to
search for here.  The search string is limited to about
30 characters, excluding "magic characters" (regular
expression meta-characters).

- "Whole line" option: if selected, search for entire lines which match the input pattern; if not, look for lines containing the input pattern as a substring.

- "No magic" option: if selected, all characters in the input pattern are treated as themselves with no special "regular expression" meaning. If not selected, the characters ^ $ * [ ] . | ( ) < > # and \\ have special meanings unless preceded by \\ (see below).

- "Ignore case" option: if selected, upper and lower case letters are considered to be identical; if not selected, search is case-sensitive.

- "Number of errors": maximum number of errors (mismatches) which are allowed in a match. 0 requires an exact match, positive values allow approximate matching. Each insertion, deletion, or substitution of a character is counted as one error. Some interfaces may provide a "Best match" choice, which looks for 0-error (exact) matches and if none are found, looks for 1-error matches, then 2-error matches, etc, until one or more matches are found.


^ ....... beginning of line
$ ....... end of line
* ....... 0 or more of previous expression
[..] .... character list, [^..] is complement,
          [a-z] is range
. ....... any character
| ....... OR (union)
( ) ..... delimit a regular expression,
          e.g., (pattern1)|(pattern2)
# ....... wildcard (equivalent to .*)
\\ ....... unmagic next character

All other characters match only themselves.


max pattern ..... 30 char (excluding meta-chars)
max errors ...... 4
max line ........ no limit
max record ...... no limit


The following examples were done with all TRADE NAMEs in wdi93demo. options: whole=FALSE, nomagic=FALSE, nocase=FALSE

  Matches METHOTREXATE and METOTREXATO with 1 error (insertion).

PARACETIMAL Matches PARACETAMOL with 2 errors (substitutions).

PENNICILIN Matches "PENICILLIN" with 2 errors (insertion and deletion).

MOREFINE Matches MORPHINE and MORFIN with 2 errors. Also matches CEPOREXINE with 2 errors (as substring).

Matches MORPHINE and MORFIN with 2 errors. Won't match CEPOREXINE at any error level (angle brackets mean "MOR" is required).


options: whole=FALSE, nomagic=FALSE, nocase=FALSE, okerrs=0

COLD Matches "COLD" anywhere, e.g. COLDRIN, CALMANTICOLD, and NICOLDA.

^COLD Matches "COLD" at beginning of line only, e.g., matches COLDRIN but not CALMANTICOLD or NICOLDA.

COLD$ Matches "COLD" at end of line only,

COLD$ Matches "COLD" at end of line only, e.g., matches CALMANTICOLD but not COLDRIN or NICOLDA.

[A-Z]COLD[A-Z] Matches "COLD" embedded between letters A-Z, e.g., matches NICOLDA but not COLDRIN or CALMANTICOLD.

^[AEIOU][^AEIOU]*[AEIOU]$ Matches lines starting with a vowel [AEIOU] followed by zero or more non-vowels, and ending with a vowel. The first ^ means "beginning of line" and the second ^ (inside brackets) causes the set of characters [AEIOU] to be complemented. Matches ALCYDE, A.S.A, ASPRO, EVE, etc.

A.S.A Matches "A" followed by any character followed by "S" followed by any character followed by "A", e.g., A.S.A, A-S-A, and HEADSTART.

A\\.S\\.A Matches "A" followed by a period followed by "S" followed a period followed by "A", e.g., matches A.S.A. but not A-S-A or HEADSTART.

Y.*Y.*Y or Y#Y#Y (mean the same thing) Matches line containing three Y's (a "Y" followed by any number of characters followed by a "Y" followed by any number of characters followed by a "Y"), e.g., matches ACETYLSALISYLSYRE.

(BASPO|STAND).*N Matches "BASPO" or "STAND" followed zero or more other characters followed by "N", e.g., BASPORIN, STANDACILLIN, and BASPORIDINA.

(BASPO|STAND).*N$ Matches "BASPO" or "STAND" in a line ending with "N", e.g., BASPORIN and STANDACILLIN, but not BASPORIDINA.

^S(AL)*ATE Matches "S" at beginning of line, followed by zero or more "AL"s, followed by "ATE", e.g., SALALATE, SATELLITE, and SATELOL.

^[AEIOU]*.([AEIOU].)*[AEIOU]*$ Matches lines where every other letter is a vowel, e.g., matches DOPAMINE, FUROSEMIDE, PARACETAMOL, PIXIE, AXIS, NALIDIXATE-ACID, etc.


The magic character '+' (one or more of) is not supported. A workaround is to use "(pattern)(pattern)*" instead of "(pattern)+".

The magic character '.' (any character) is not effective at the beginning (or end) of a line, e.g., the pattern ".COLD" matches COLDRIN, but shouldn't. A workaround is to use a pattern like "^..*COLD" which works correctly.

The magic character '#' is exactly equivalent to ".*" and is redundant. It is provided for forward compatibility with approximate string (not regular expression) searches. However, the same thing is not done for other such characters, e.g., ',' (or) and ';' (and).

There is no way to specify a NULL character as part of a pattern.

ARES uses algorithms which are general enough to do approximate regular expression matching. Faster algorithms are available for less general cases, e.g., approximate matching of simple strings and exact regular expression matching. Such methods should be used as appropriate (but aren't, yet).

An internal buffer which holds strings to be searched is part of each search context. This buffer is re-allocated as needed, so there is no fixed limit on the size of strings which may be searched. However, on a single CPU machine, only a single dy_ares_test() runs at once, so it would be more efficient to use a single shared buffer.

In the case of a large number of strings which are much smaller than the available buffer size (typical for a server), most of the processing time is spent setting things up. This can be improved substantially by encoding multiple lines per string (i.e., with newlines). For instance, wdi93demo contains 16239 TRADE NAMEs in 1235 datatrees. Doing the search as 16239 dt_ares_test() calls takes 0.69 sec on a Sun IPX. Doing the same searches with 1235 multi-line calls takes 0.34 sec (200% faster). Unfortunately (this is the bug) the dy_ares_test() interface doesn't tell you which lines hit.

For substring searches, it would be nice if ARES would return information about which characters matched (perhaps the first and last in the match?)

The code is optimized for machines with 32-bit words.


The algorithm used here is pretty much as described in the following papers:

Boyer, R.S. and Moore, J. S., "A fast string searching algorithm", Proc. ACM-SIGIR Conf on Info. Retriv., Cambridge MA, June 1989, pp 168-175.

Myers E.W. and Miller, W., "Approximate matching of regular expressions", Bull. of Mathematical Biology, 51, 1989, pp 5-37.

Tarhio J. and Ukkonen, E., "Approximate Boyer-Moore string matching", Technical Report A-1990-3, Dept. Comp. Sci., U. Helsinki, (March 1990).

Wu, S. and Mamber, U., "Fast text searching with errors", Technical Report TR-91-11, Dept. Comp. Sci., U. Arizona (June 1991).

The algorithm is structured in the manner of Wu and Mamber's use of the Boyer-Moore algorithm in agrep (re and re1), but reimplemented to provide reentrant code. This implementation doesn't use the agrep, mgrep, or monkey algorithms, and does not operate in sub-linear time. agrep contains all of these and is available by ftp from (IP

Related Topics