Cover V10, I06


Fuzzy Text Searches with agrep and afind

Alex Golomshtok and Yefim Nodelman

In the past few years, the advents of storage and networking technology and the Internet have contributed to a dramatic increase in the amount of information accessible from the desktop. Users are now faced with the problem of information overload -- it can be difficult to locate the resources relevant to their needs. Under these conditions, the ability to effectively search through vast amounts of data becomes a primary requirement for any modern computing environment.

Most of the popular programming languages now are equipped with text-searching and pattern-matching facilities of varying degrees of sophistication. Most common are the "all-or-none" search facilities that incorporate either exact string matching or wildcard and regular expression matching algorithms. When the precise search string is known in advance, the exact string matching algorithms usually offer the best performance, although the speed of the search is proportional to the length of the search argument and the quality of the matching algorithm. For very short search patterns, for instance, with length of the pattern not exceeding four characters, the brute-force matching algorithms are usually the fastest. For longer search patterns, more sophisticated algorithms (e.g., Rabin-Karp Checksum [1] or Boyer-Moore [2] Algorithm) are known to provide superior performance.

Regular expressions [3] are often used when an exact search pattern is not known in advance. The power of regular expressions comes from the ability to express a search pattern in generic terms, potentially representing an infinite set of search arguments with a single expression. A pattern like "[A-Za-z]+", for instance, will match any string comprised by the upper and lower letters of the alphabet. In addition to expressing the patterns using generic "meta-characters", regular expression implementations often provide for anchors or ability to control the exact position of a match within the search text, and back-references that allow for easy text replacement and substitution. Regular expressions are the natural solution to many pattern-matching problems, such as looking for files and directories, monitoring and extracting the information from log files, filtering mail messages, etc.

Despite all their power, exact matching as well as regular expressions are usually an all-or-nothing proposition. These algorithms make it difficult, if not impossible, to account for typos, alternative spellings, spelling errors, and errors originated from data transmission. To solve these types of problems efficiently, you would have to employ an alternative technique known as approximate matching. Approximate string matching is fundamental to modern text processing and is heavily used by such computer applications as word processors or search and indexing engines.

Based on the needs of a particular application, the actual algorithm behind the approximate matching mechanism may vary. Phonetic algorithms such as soundex [4], for example, allow for matching strings that sound similarly. A typical soundex implementation is simply an indexing system that translates the strings into alphanumeric soundex codes by ignoring the vowels and assigning "weights" to the consonants. Since similar-sounding consonants are assigned the same weight (e.g., "B", "P", "F", and "V" are all assigned "1"), similar-sounding strings are likely to produce equal soundex codes. Soundex is a very popular technology, the most famous application of which was the initiative of the U.S. Bureau of the Census to create an index for individuals listed in the U.S. census records after 1880.

While being efficient and easy to implement, soundex is limited due to its phonetic nature; different natural languages require different implementations. The German soundex, for instance, usually uses six character codes as opposed to four-character English codes, and the consonants are grouped based on different rules.

Yet another family of string-matching algorithms, known as fuzzy matching algorithms, takes an entirely different approach of calculating various measures to assess the degree of proximity between strings. There are two major measures that reflect the degree of proximity -- k-mismatches and k-differences. The k-mismatches measure, also known as Hamming distance, expresses the difference between two strings by the number of characters that need to be changed to obtain one from the other, where "k" is the maximum number of differences allowed. For instance, "butter" and "ladder" have a Humming distance of four as four characters need to be replaced to obtain one from the other. The k-differences measure or Levenshtein distance [5] indicates how many "edits" (i.e., insertions, deletions, or substitutions) are necessary to transform one string into the other, where "k" is the maximum number of edits allowed. The Levenshtein distance between "GUMBO" and "GAMBOL", for example, is two because two edits are necessary.

There are numerous fuzzy matching algorithms that utilize k-mismatches (such as Baeza-Yates-Gonnet [6]), and k-differences (such as Wu-Manber [7]). These algorithms are efficient, versatile, and language independent, which makes them suitable for many text-processing tasks.

Perl and Fuzzy String Matching

Perhaps one of the most exciting features of Perl is its unsurpassed support for regular expressions that has been an intrinsic part of the language since its inception. One thing that Perl lacks, however, is built-in fuzzy or approximate text-matching facilities. This niche is filled with Perl extension modules, thanks to the enthusiasm of numerous Perl developers. Currently, the Comprehensive Perl Archive Network (CPAN) ( offers several modules that perform fuzzy string matching and calculate similarities between strings.

One of these modules, String::Approx by Jarkko Hietaniemi [8], allows for approximate string matching and substitutions using Wu-Manber k-differences algorithm. This module performs fuzzy matching based on a set of inputs that control such aspects of matching process as maximum degree of proximity, case sensitivity, and more.

Yet another extension, String::Similarity by Mark Lehmann [9], is designed to calculate the similarity index between two string arguments. This module is based on an O(ND) Difference Algorithm [10], which also calculates the k-differences measure for its input arguments.

These modules bring the benefits of fuzzy matching to Perl users while encapsulating the complexities of the underlying algorithms and exposing enough functionality to solve nearly any text searching and matching problem.


To illustrate how approximate string matching may be applied to everyday computing tasks, we developed several useful utilities that extend the functionality of traditional UNIX programs such as find and grep. The afind script recursively descends the directory hierarchy searching for files, named such that the degree of similarity between the file name and a search string does not exceed a certain percentage. The similarity search limit percentage is controlled via a command-line parameter. The script outputs a list of files that match the criteria, sorted by similarity index (most similar first).

The script takes several command line options. Option -l specifies the similarity limit as a percentage -- a higher number will force the script to output closer matches. Option -h causes the script to print the usage string and exit immediately. Finally, option -v forces verbose output, which can be very useful for diagnostic purposes. The remaining two arguments are the name of the directory to use as a starting point for the search and a search pattern. The directory name can be omitted, in which case the current working directory will be used as a starting point.

The following is the complete source code listing for the afind script:

1  #!/usr/local/bin/perl
3  use Getopt::Std;
4  use File::Find;
5  use String::Similarity;
7  $| = 1;
9  $usage = qq(Usage: afind -lvh [directory] search_pattern\n);
11  die $usage
12    unless  getopts( qq(l:vh) );
13  die $usage
14     unless @ARGV;
15  die $usage
16     if $opt_h;
18  $limit   = ( $opt_l =~ /^(\d{1,2}|100)$/ ) ? ( $opt_l/100.0 ) : 0.75;
19  $dir     = @ARGV > 1 ? shift : q(.);
20  $pattern = shift;
22  die qq(Directory $dir doesn't exist!\n)
23     unless -d $dir;
25  File::Find::find( \&wanted, $dir );
27  foreach $file ( sort { $b->{ sindex } <=> $a->{ sindex } } @files ) {
28     printf "%.2f\t%s\n",$file->{ sindex }, $file->{ name };
29  }
30  exit( 0 );
32  sub wanted {
33     my $sindex   = similarity( $pattern, $_, $limit );
34     print qq(Processing $File::Find::name ( $sindex )...\n)
35        if $opt_v && -t;
36     push( @files, { name => $File::Find::name, sindex => $sindex } )
37        if $sindex >= $limit;
38  }
Lines 3 through 5 load several Perl extension modules, used by the script Getopt::Std [11] that facilitates parsing the command-line arguments, File::Find [12] that provides the framework for traversing directory structures and, finally, String::Similarity [9] that provides the functionality for fuzzy pattern matching. Line 7 sets a special variable $| to a non-zero value, which turns off the IO buffering and forces the flush after every print statement on currently selected output channel. Line 9 sets up the variable that contains the usage string for afind; this string is output by lines 11 through 16 in case the script is invoked with wrong or insufficient command-line arguments. Lines 11 and 12 call the getopts routine from the Getopt::Std module in order to parse the command-line arguments. This routine takes a single argument -- a string that contains all allowed command-line options, in our case single character options l, v, and h. The switches that take arguments, such as l, are followed by colons. On completion, the getopts routine sets up variables for every command-line argument. For afind, three option variables will be set -- $opt_v, $opt_h, and $opt_l. Because $opt_v and $opt_h do not take arguments, they will be assigned a Boolean true or false value based on whether the command-line switches for these options are supplied. $opt_l, however, if set, will contain the value for the similarity limit parameter.

The getopts routine stops processing command-line arguments as soon as it encounters an argument that does not look like a command-line switch (i.e., does not have the dash as a first character). Therefore, after getopts returns, the @ARGV array is expected to contain at least one argument (the search string) because the starting directory is optional. Lines 13 and 14 validate this condition by checking the @ARGV array, which in scalar context evaluates to the number of remaining command-line arguments. Finally, lines 15 and 16 print the "usage" string and exit the program if the "help" option is set.

Lines 18 through 23 perform some rudimentary validity checking of input arguments. Line 18 ensures that the similarity limit value, if supplied, is a valid percentage (i.e., an integer between 0 and 100). If no valid value is supplied, the limit is set to a default value of 75% (0.75). Line 19 checks if the starting directory command-line parameter is present, otherwise the default starting point is set to the current working directory. Line 20 simply obtains the value of the command-line search pattern argument and lines 22 and 23 validate the starting directory.

Line 25 invokes the find routine from the File::Find module. This routine traverses the directory hierarchy recursively starting from the directory, identified by the second parameter, the $dir variable. For every directory entry encountered by File::Find, it invokes a user-supplied subroutine; reference to this subroutine is passed to File::Find as a first parameter.

This subroutine, called wanted (see lines 32 through 38), performs the bulk of the work. Every time it is called, File::Find sets the default input variable $_ to the base name of the directory entry being processed. The subroutine calls "similarity" function, which is part of the String::Similarity module, to calculate the similarity index between the search pattern, contained in the global variable $pattern and $_, which is set to the current file or directory name. The similarity index ($sindex), calculated by the similarity function, may take values between 0 and 1, where 1 means that two string arguments are identical. The third parameter to the similarity function ($limit) is optional; it sets the minimum similarity that the input string arguments must satisfy.

Based on this parameter, the similarity function stops analyzing its input arguments as soon as it determines that the result is likely to fall below the limit. In this case, the returned similarity index will be invalid but lower than the limit. Therefore, setting the limit may significantly boost the performance of the algorithm, especially when comparing long strings. Lines 34 and 35 of the wanted subroutine simply check whether the verbose output is requested and output the full name of the current file or directory, contained in the $File::Find::name variable, along with the calculated similarity index. This feature comes handy while debugging the script or checking the results of the similarity search.

Finally, lines 36 and 37 save the name and the similarity index of those files (and directories) that satisfy search criteria (i.e., have the similarity index that exceeds the search limit). File names and corresponding indexes are saved into an anonymous hash with two keys, name and sindex, and the reference to this hash is pushed into a global @files array.

Upon the completion of the File::Find::find function, the script iterates through the global @files array that contains one entry for every file or directory that satisfies the search criteria. The array is sorted in descending order by the similarity index using a user-defined anonymous sort subroutine [13]. Each iteration of the foreach loop at line 27 assigns the reference to a hash, containing the current file information to the variable $file. Then, line 28 outputs the full name of the file along with its similarity index. Running afind on the system with the following command:

afind /etc sesytem
produces the following output:

0.77 /etc/system
While changing the similarity limit from the default of 75% to 50%:

afind -l50 /etc sesytem
yields the following:

0.77 /etc/system
0.62 /etc/setmnt
0.57 /etc/lp/Systems
0.57 /etc/uucp/Systems
agrep The agrep script is an example of another application of an approximate string-matching technique to the well-known computing problems. This script works in a way similar to a traditional UNIX grep utility -- it searches input files for occurrences of a particular string, specified by a command-line argument.

The script requires at least two command-line arguments -- the search pattern and the name of the file to search for occurrences of the pattern. Multiple file names or filenames with wildcards may be supplied. Note that the agrep script relies on a shell to perform the wildcard expansion; if the wildcard arguments are quoted so that the expansion does not take place, the script will process these arguments as exact file names.

The behavior of the script and the amount of output can be controlled via three command-line switches: -l, which specifies the similarity search limit similar to the parameter of the afind script; -i, which causes the search algorithm to ignore the case of the letters while comparing; and -n, which directs the script to only output the names of the files that contain the search pattern instead of printing the actual matches (similar to the -l option of a traditional grep).

The following is a complete source code for the agrep script:

1  #!/usr/local/bin/perl
3  use Getopt::Std;
4  use String::Approx 'amatch';
6  $| = 1;
8  $usage = qq(Usage: agrep -linh search_pattern [files...]\n);
10  die $usage
11    unless  getopts( qq(l:inh) );
12  die $usage
13     unless @ARGV;
14  die $usage
15     if $opt_h;
17  $limit   = ( $opt_l =~ /^(\d{1,2}|100)$/ ) ?
18     q($opt_l%) : q(15%);
19  $pattern = shift;
21  foreach $file ( @ARGV ) {
22     next if -B $file;
23     open( _F, $file ) || do {
24        print STDERR qq(Can't open file $file - $!.\n);
25        next;
26     };
27     @lines = <_F>;
28     foreach $match ( amatch( $pattern,
29        [ $limit, $opt_i && qq(i) ], @lines ) ) {
30        print qq($file: ), $opt_n ? qq(\n) : $match;
31        last

32           if $opt_n;
33     }
34     close( _F );
35  }
Lines 3 through 15 are very similar to the corresponding code of the afind script with one exception -- instead of loading the String::Similarity [10] module, the agrep uses another Perl extension for approximate string matching, String::Approx [9]. This module exposes numerous functions, however, the agrep script will only use one of them -- amatch.

The similarity search limit parameter, taken by the String::Aprox module, is different from the corresponding parameter of the String::Similarity module. It is expressed either as an absolute number of allowed "edits" (i.e., k-differences measure) or a percentage value of the number of allowed "edits" relative to the length of the string (i.e., 10% means that every 10th character may be an "edit"). For the sake of consistency, agrep uses the percentage values to control the similarity limit with the default set at 15%.

Line 21 of the script iterates over the @ARGV array that contains the names of the files to be searched for the occurrences of the pattern. Every iteration of the loop assigns the name of the file from the @ARGV to the variable $file. Line 22 skips to the next iteration of the loop if the current file is a binary; for the sake of simplicity we excluded the processing for binary files from the script. Lines 23 through 27 open the current file for read access and load the file data into a global array @lines. Finally, the foreach loop at line 28 invokes the amatch function of the String::Approx module, collects the matches one-by-one into the $match variable, and prints them out.

The amatch function is the simplest of the functionality, exposed by the String::Approx. It takes a search pattern as its first parameter, then a number of optional modifiers and an optional array of input strings. The third parameter, the array of inputs, may be omitted, in which case, the amatch will assume that the default input $_ contains the string to be matched. In list context, this function returns all input lines that match the pattern; in scalar context, it simply returns a true or false value based on whether any of the inputs match the pattern.

The behavior of amatch can be controlled via a number of optional modifiers, passed as a second parameter. One of the modifiers is the similarity limit, discussed previously. As mentioned before, the limit here is a total number of "edits" -- insertions, deletions, and substitutions allowed in the search. This, however, can be controlled at a much finer level by supplying explicit numbers for each type of "edit". For instance, "I10%", "D20%", and "S5%" will allow for 10% of insertions, 20% of deletions, and 5% of substitutions, respectively. Another modifier, used by agrep, is the case-sensitivity modifier i, which turns off case-sensitive matching. Other modifiers are available. For instance, the exact positions within the input argument where the search should begin and end can be controlled via initial_position and final_position modifiers. Running agrep on the system:

agrep sysshm /etc/system
produces the following output:

/etc/system: *                exclude: sys/shmsys
/etc/system: set shmsys:shminfo_shmmax=1610612736
/etc/system: forceload: sys/shmsys
Bumping up the similarity limit from the default 15% to 25%:

agrep -l25 sysshm /etc/system
will yield the following:

/etc/system: *ident   "@(#)system    1.15    92/11/14 SMI" /* SV
/etc/system: * root device and root filesystem configuratio
/etc/system: *    the root filesystem) rather than at first
/etc/system: set shmsys:shminfo_shmmax=1610612736
/etc/system: forceload: sys/msgsys
/etc/system: forceload: sys/shmsys
/etc/system: forceload: sys/semsys
The output of agrep is not sorted by relevance or similarity index simply because the amatch function does not return the calculated edit distance. However, another function of the String::Approx module, adist, is specifically designed to calculate and return the edit distance between the input string and the pattern. Also, function aslice may be directed to return the calculated edit distance via optional modifier minimal_distance. This function is especially useful as it provides the starting position and the length of the match.


Approximate string matching is an extremely powerful technique, quickly gaining popularity within the modern software development community. More and more often we see the new software products, reaping the benefits of those fuzzy searching algorithms, which up until a few years ago were thought of as a subject for a Ph.D. in Computer Science rather than something that had any practical application. Languages like Perl make these algorithms easy to use, which leaves no excuse for not exploring the power of the approximate text matching capabilities.

We hope that this article stimulated your interest, and we encourage you to become familiar with Perl text-processing extension modules. Apart from the two modules discussed here, CPAN offers some more: stemming and inflection modules, such as Text::Stem and Lingua::EN::Inflect, which may be very useful for spell checking applications; and Text::Soundex, which encapsulates the soundex algorithm implementation and others. Altogether, these modules will enable you to produce powerful and user-friendly software applications.


1. R. Karp and M. Rabin. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31:249-260, 1987.

2. R. Boyer and J. Moore. A fast string-searching algorithm. Communications of the ACM, 20:762-772, 1977.

3. J. Friedl and A. Oram. Mastering Regular Expressions: Powerful Techniques for Perl and Other Tools. O'Reilly & Associates. 1997.

4. D. Knuth. The Art of Computer Programming: Sorting and Searching, Vol. 3. Addison-Wesley, 1998.

5. V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Sov. Phys. Dokl., 6:707-710, 1966.

6. G. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures. Addison-Wesley, 1991.

7. S. Wu and U. Manber. Fast text searching allowing errors. Communications of the ACM, 35:83-91, 1992.

8. J. Hietaniemi. String::Approx, Latest Version 3.15, Feb, 2000. CPAN directory JHI.

9. M. Lehmann. String::Similarity, Latest Version 0.02, Nov 2000. CPAN directory MLEHMANN.

10. E. Myers. An O(ND) Difference Algorithm and its Variations. Algorithmica, Vol 1. No. 2. 251-266, 1986.

11. G.Sarathy. Getopt::Std, Latest Version - Perl 5.6.1, Jan 2001. CPAN directory GSAR.

12. G.Sarathy. File::Find, Latest Version - Perl 5.6.1, Nov 2000. CPAN directory GSAR.

13. L. Wall, T. Christiansen, R. L. Schwartz. Programming Perl. O'Reilly & Associates, 1996.

Alexander Golomshtok is a professional consultant who, for the last decade, has been hanging around downtown New York developing large-scale software systems and infrastructure solutions for Wall Street firms. He can be reached at:

Yefim Nodelman is a seasoned systems administrator with seven years of professional experience in supporting UNIX and Windows NT ystems. He can be reached at: