This library implements the Wu-Manber algorithm for string searching with errors, popularized by the agrep Unix command and the glimpse file indexing tool. It was developed as part of a search engine for a largish MP3 collection; the "with error" searching comes handy for those who can't spell Liszt or Shostakovitch.

Given a search pattern and a string, this algorithm determines whether the string contains a substring that matches the pattern up to a parameterizable number N of errors. An error is either a substitution (replace a character of the string with another character), a deletion (remove a character) or an insertion (add a character to the string). In more scientific terms, the number of errors is the Levenshtein edit distance between the pattern and the matched substring.

The search patterns are roughly those of the Unix shell, including one-character wildcard (?), character classes ([0-9]) and multi-character wildcard (*). In addition, conjunction (&) and alternative (|) are supported. General regular expressions are not supported, however.

The algorithm is described in S. Wu and U. Manber, Fast Text Searching With Errors, tech. rep. TR 91-11, University of Arizona, 1991.

(pattern STRING [TRANSL]) => PATTERN

Compiles a search pattern. The syntax for patterns is similar to that of the Unix shell.
The following constructs are recognized:

• ?: match any single character
• *: match any sequence of characters
• [..]: character set: ranges are denoted with -, as in [a-z]; an initial ^, as in [^0-9], complements the set
• &: conjunction (e.g. sweet&sour)
• |: alternative (e.g. high|low)
• (..): grouping
• \: escape special characters; the special characters are \?*[]&|().

The optional argument TRANSL is a character translation table.

(string->pattern STRING [TRANSL]) => PATTERN

Returns a pattern that matches exactly the given string and nothing else.

(string-match PAT STRING [NUMERRS] [WHOLEWORD]) => BOOL

Tests whether the string STRING matches the compiled pattern PAT. The optional keyword parameter NUMERRS is the number of errors permitted. One error corresponds to a substitution, an insertion or a deletion of a character. NUMERRS default to 0 (exact match). The optional keyword parameter WHOLEWORD is true if the pattern must match a whole word, false if it can match inside a word. It defaults to false (match inside words).

(substring-match PAT STRING POS LEN [NUMERRS] [WHOLEWORD] )

Same as string-match, but restricts the match to the substring of the given string starting at character number POS and extending LEN characters.

(errors-substring-match PAT STRING POS LEN [NUMERRS] [WHOLEWORD])

Same as substring-match, but returns the smallest number of errors such that the substring matches the pattern. That is, it returns 0 if the substring matches exactly, 1 if the substring matches with one error, etc. Returns -1 if the substring does not match the pattern with at most NUMERRS errors.

agrep was originally written by Xavier Leroy and ported to Chicken by Ivan Raikov.

Copyright 2009-2015 Ivan Raikov.

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

A full copy of the GPL license can be found at http://www.gnu.org/licenses/.