Fast i-. i The string-matching problem is a very common problem. We are searching for a string P = PtP2.. "Pro inside a large text file T = tlt2...t., both sequences of characters from a finite character set Z. The characters may be English characters in a text file, DNA base pairs, lines of source code, angles between edges in polygons, machines or machine parts in a production schedule, music notes and tempo in a musical score, and so forth. We want to find all occurrences of P in T; namely, we are searching for the set of starting positions F = {i[1 ---i---n -m + 1 such that titi+ l""ti+ m -1 = P}" The two most famous algorithms for this problem are the Boyer-Moore algorithm [3] and the Knuth Morris Pratt algorithm [10] . There are many extensions to this problem; for example, we may be looking for a set of patterns, a pattern with "wild cards," or a regular expression. String-matching tools are included in every reasonable text editor, word processor, and many other applications. In some instances, however, the pattern and/or the text are not exact. For example, we may not remember the exact spelling of a name we are searching, the name may be misspelled in the text, the text may correspond to a sequence of numbers with a certain property and we do not have an exact pattern, the text may be a sequence of DNA molecules and we are looking for approximate patterns. The approximate string-matching prob -" lem is to find all substrings in T that are close to P under some measure of closeness. The most common measure of closeness is known as the edit distance (also the Levenshtein measure [13] ). A string P is said to be of distance k to a string Q if we can transform P to be equal to Q with a sequence of k insertions of single characters in (arbitrary places in) P, deletions of single characters in P, or substitutions of characters. In some cases we may want to define closeness differently. For example, a policeman may be searching for a license plate ABC123 with the knowledge that the letters are correct, but there may be an error with the numbers. In this case, a string is of distance 1 to ABC123 if only one error occurs and it is within the digits area. Maybe there are always three digits in a license plate, in which case only substitutions are allowed. Sometimes one wants to vary the cost of the different edit operations, say deletions cost 3, insertions 2, and substitutions 1. Many different approximate string-matching algorithms have been suggested ([4, 5, 6, 8, 11, 12, 16, 19, 20] is a partial list). In this article we present a new algorithm which is very fast in practice, reasonably simple to implement, and supports a large number of variations of the approximate stringmatching problem. The algorithm is based on a numeric scheme for exact string matching developed by COMMUNICATIONS OF THE ACM/October 1992/Vol.35, No.10 83 Baeza-Yates and Gonnet [2] . The algorithm can handle most of the common types of queries, including arbitrary regular expressions, and several variations of closeness measures. In our experiments, the algorithm was at least twice as fast as other algorithms we tested (which are not as flexible), and for many cases an order of magnitude faster. For example, finding all occurrences of Homogenos allowing two errors in a 1MB bibliographic text takes about 0.4 sec on a SUN SparcStation II. We actually used this example and found a misspelling in our text. The algorithms in this article served as a basis for a software package for Unix called agrep, which has been in use since June 1991. Agrep, which at the date of this writing is at version 2.04, is available by anonymous ftp from cs.arizona.edu. We describe agrep briefly at the end of this article. For more information see [15, 23, 24] . We begin by describing the algorithm for the pure string-matching problem (i.e., the pattern is a simple string). We then present many variations and extensions of the basic algorithm, culminating with matching arbitrary regular expressions with errors. Experimental results are given, as are details of agrep. We first describe the case of exact string matching. The algorithm for this case is essentially identical to that of [2] . We present it here for completeness and because we use a slightly different notation. We then show how to extend the algorithm to search with errors. We then describe how to speed up the search with errors by using afiltering search technique. Let R be a bit array of size m (the size of the pattern). We denote by Rj the value of the array R after the j character of the text has been pro- Table lb . This discussion assumes, of course, that the pattern's size is no more than the word size, which is often the case. If the pattern's size is twice the word size, then four arithmetic operations will suffice. If the pattern is very large (e.g., in some biological applications the pattern size can be in the thousands), then other methods will be better. For most text-searching problems, small patterns are the norm. We discuss this issue later, but for now we will assume that the pattern's size is no more than the word size. This algorithm is clearly very easy to implement. Its running time is totally predictable because it essentially depends only on the size of the text (assuming again that the pattern fits into a word) and not on the actual text or the alphabet. We now show how to adapt the previous algorithm to allow errors. (Baeza-Yates and Gonnet [2] showed how to handle only mismatches by essentially counting k of them with a log2k size counter, but they did not handle insertions or deletions.) We start with a very simple case: only one insertion is allowed into the pattern at any position. In other words, we want to find all intervals of size at most m + 1 in the text that contain the pattern as a subsequence. We define the R and S arrays as before, but now we have two possibilities for each prefix match. We can have an exact match or a match with one insertion. Therefore, we introduce there is a match with at most one insertion (sometimes both will equal 1 at the same time). The transition for the R array is the same as before. We need only to specify the transition for R 1. There are two cases for a match with at most one insertion of the first i characters of P up to tj+l: I 1. There is an exact match of the first i characters up to tj. In this case, inserting tj+ 1 at the end of the exact match creates a match with one insertion. I2. There is a match of the first i -1 characters up to tj with one insertion and tj+ 1 = Pi. In this case, the insertion is somewhere inside the pattern and not at the end. Case I1 can be handled by just copying the value of R to R 1 and case I2 can be handled with a right shift of R 1 and an AND operation with Si such that si= §+l. So, to compute R] we need one additional shift (the shift of R is done already), one AND operation and one OR operation. An example (with the same pattern and text as the example for the exact matching) is given in Table 2 . Consider now allowing one deletion from the pattern (and no insertions). We will define R, R 1 (which now indicates one deletion), and S as before. There are again two cases for a match with at most one deletion of the first i characters of P up tO /j+l: D1. There is an exact match of the first i-1 characters up to tj+l (which is indicated by the new value of the R array Rj+l [i-1]). This case corresponds to deleting pi and matching the first i -1 characters. D2. There is a match of the first i-1 characters up to tj with one deletion and tj+ x = pi. In this case, the deletion is somewhere inside the pattern and not at the end. Case D2 is handled as before (it is exactly the same), and case D1 is handled by a right shift of the new value of Rj+ 1. Finally we will consider a substitution. That is, we allow replacing one character of P with one character of T. (We can achieve substitution with one deletion and one insertion, but in many cases we want substitution to count as only one error.) We again have two cases: S1. There is an exact match of the first i -1 characters up to tj. This case corresponds to substituting tj+ l with pi (whether or not they are Table I 1"uble 2. An example for approximate matching with one insertion equal--the equality will be indicated in R) and matching the first i-1 characters. $2. There is a match of the first i -1 characters up to tj with one substitution and tj+ 1 = Pi. In this case, the substitution is somewhere inside the pattern and not at the end. Case $2 is again the same. Case S1 corresponds to looking at Rj [i -1] as opposed to looking at Rj+l [i -1] in case D 1. Still very few operations cover one substitution as well. We are now ready to consider the general case of up to k errors, where an error can be either an insertion, a deletion, or a substitution (the Levenshtein or the editdistance measure). Overall, instead of one additional R 1 array, we will maintain k additional arrays R 1, R 2, following expression for Rd+l : R~ = 11..100...000 d ones. Overall, we have a total of two shifts, one AND, and three ORs for each R d. The time and space analysis of the algorithm is as follows. where m is not too large, which are the cases the algorithm was designed for, the running time is ef- An important feature of this algorithm is that it can be relatively easily extended to several more complicated patterns. Several such extensions will be described. For example, if r = 1, then we will need to check any time there is a character match, which is probably too often. On the other hand, if r = 3, m = 12 (which implies k = 3), the alphabet size is 26, and the text is uniformly random (i.e., each character appears with the same probability), the expected number of matches of any of the Pj's is about 0.02% of the time. In this case, it is obviously advantageous to search for exact matches and use the approximate scheme only for the rare occasions at which a match occurs. The running time in this case is essentially the same as the running time of a search without errors. (Experiments using this partition scheme for different alphabet sizes are given later.) The main advantage of this scheme is that the algorithm for exact matching presented earlier can be adapted in an elegant way to support it. We illustrate the idea with an example. Suppose the pattern is ABCDEFGHIJKL (m = 12) and k = 3. We divide the pattern into k + 1 = 4 blocks: ABC, DEF, GHI, and JKL. We need to find whether any of them appears in the text. We create one combined pattern by interleaving the four blocks: ADGJBEHKCFIL. We then build the mask vector R as usual for this interleaved pattern (see section on Exact Matching). The only difference is that, instead of shifting by one in each step, we shift by four! There is a match if any of the last four bits is 1. (When we shift we need to fill the first four positions with ls, or better yet, use shift-OR.) Thus, the match for all blocks can be done exactly the same way as regular matches and it takes essentially the same running time. An important feature of our algorithm is its flexibility. In addition to asking about a single string, the algorithm supports range of characters (e.g., "0-9"), complements (e.g., everything except blank), arbitrary sets of characters (e.g., {a,e,i,o,u}), unlimited "wild cards," and combinations. Searching for several strings at the same time is also possible, although the size of the pattern becomes the sum of the sizes of the different strings (and might thus require more than one word to represent). Except for the unlimited wild cards, all these extensions were developed by Baeza-Yates and Gonnet [2] for exact matching. We can apply them all to approximate matching in a straightforward manner. This is a major strength of the algorithm: most extensions (at least all those that we tried) that work for exact matching can also be used for approximate matching. Previous algorithms for approximate matching with complements or wild cards, for example, were quite complicated (see, for example, [1, 18] ). The running time for all these extensions is the same as the running time of the basic algorithm given earlier. In addition to these extensions, we also support two extensions that are specific to approximate matching. One deals with patterns in which some parts need to match exactly and other parts may contain errors. Another extension is matching with some nonuniform costs; for example, we can define the cost of insertions to be twice that of deletions. The most complicated patterns we can handle are arbitrary regular expressions. The ability to efficiently match regular expressions allowing errors enabled us to extend the grep family and implement the approximate patternmatching tool agrep. We now describe the extensions in more detail. October 1992/Vo1.35, No.10/COMMUNICATIONS OF THE ACM Replacing one character with a set of allowable characters is very easy to achieve with this algorithm (as was shown in [2]). Suppose the pattern we want to find is ABC followed by one digit followed by XYZ, and that we allow up to k errors. We denote this pattern by ABC[0-9]XYZ. The only thing we need to do to accept any digit in the fourth position is to put 1 in the fourth position in the S arrays for all digits. That is, in the preprocessing stage, when we decide for each character the positions that this character matches in the pattern, we include all the characters in the set within that position. The rest of the algorithm is identical with the regular algorithm. A complement of a character is a special case of a set of characters and it can obviously be handled in the same way. A single wild card is a symbol that matches all characters. As such, it is a special case of a set of characters and can be handled as we discussed in the previous section. Sometimes, however, we want to indicate that we allow an unbounded number of characters to appear in the middle of the pattern (or even do it several times in the middle of the pattern We first try to find the pattern with no errors. If we are unsuccessful, we try with one error, then with three errors, then with 7 errors, and so on, essentially doubling the number of errors (and adding one) at each attempt. If the number of errors turns out to be k, then the running time will be O (1-n + 2"n + 4-n+'-'+ 2b.n), where 20 is the first power of 2 greater than k. In the worst case, we perform 4 times as many operations as we would have had we known k (in most cases, the factor is actually 2 or 3). Sometimes we do not want to allow parts of the pattern to have errors. For example, we may look for license plate ABC123, and we know that the letters are correct but the numbers may have one error in them. We denote this pattern by <ABC>123. We can modify the algorithm to shield parts of the pattern from having any errors in them. Let's assume that I is the set of indexes in the pattern where no error is allowed, and let M be a masking array (of size m) that has a 0 in the indexes of I and a 1 otherwise. We would like to modify (2.1) such that insertions, deletions, and substitutions can only occur outside of I. This is done by masking these cases with M. The expression in  If we have several patterns and we want to find all occurrences of any of them, then we can either search them one at a time or together. The advantage of searching for all of them together is that it can be done in one scan (and in one command). Suppose we are looking for P1, Pz, .... Pr. We concatenate all the patterns and put them in one array (using as many words as needed), and apply the algorithm on that array with the following modifications. Let M be a bit array the size of the combined pattern, and let bit i  Suppose that the pattern occupies several words and it is a simple string. The algorithm proceeds in the same fashion by computing the R a arrays for all words. However, unless the number of errors is large, the first part of the pattern will not be matched quite often. If there is no match with k errors starting after position r of the pattern, then there is no need to maintain the R arrays corresponding to positions larger than r (their values will be 0). Thus, most of the time there will be no need to maintain the R a arrays for the right side of the pattern. We only need to be alerted when the last bit of the last R a array that we maintain gets the value of 1. In that case, we start maintaining the Ra arrays for the next part of the pattern. This improvement does not work for sets of patterns or regular expressions. The algorithm can be extended to allow any regular expression as a pattern. We describe the method here only briefly; for more details see [23] . Other algorithms for approximate matching to regular expressions can be found in [17, 22, 25] . First, we illustrate the algorithm with a simple example. We do not try to optimize the algorithm here; we try to make it as simple as possible to describe. Let the pattern be P = ab(cdle)*fg (i.e., starting with ab and ending with fg with any number of either cd or e in between). This regular expression is translated to the nondeterministic finite automata shown in Figure 1 (for more on such translations, see [9] ). We now assign a bit array to represent the automata. We number the states including the null states that do not correspond to any character. This "linearizes" the automata. Each state corresponds to one entry in the array. Thus, for P we have an array of size I 1. Notice that all the non-e moves go to the next state and thus can be handled by essentially a shift and an AND operation. We need to find a way to deal with arbitrary jumps required by the e moves (e.g., from state 2 to state 8) and with "nonjumps" that happen to be in consecutive states (e.g., from state 5 to state 6). The nonjumps can be handled easily with a mask. The arbitrary jumps are harder to handle. The meaning of an e move from state i to statej is that if, at any point, we match up to state i then the same match holds also up to statej. In other words, if there is a 1 corresponding to state i in the array, then the e move from i toj implies that there should be a 1 corresponding to state j. The main observation is that a given bit array and set of e moves completely determine the value of the bit array after the e moves are taken. Thus, the set of e moves defines a function that maps a bit array to another. We need to be able to implement this function efficiently. Let f denote the function that maps one bit array to another by applying all the e moves. We divide the bit array into bytes (i.e., groups of 8 bits each). Consider the first 8 bits of the bit array. The values of these bits determine which l's should be set when we apply the e moves on states 1 to 8. Since there are only 256 (=28 ) possible values for 8 bits, we can preprocess all possibilities and construct a table of size 256 which will hold, for each possible byte, the whole bit array with ls only in places corresponding to the e moves. (We need the whole array and not just the first 8 bits, because there might be forward jumps.) We can do that for each byte. Given now a current value of R, we first apply the regular algorithm, taking care of regular non e moves, then we divide the array into bytes, find the corresponding arrays in the tables (we have one table per byte), and OR all of them to R. This implements all the jumps, and if the pattern occupies no more than 32 bits (as is often the case), only four more steps are required. (If the text is large, it is worthwhile to preprocess 16 bits for a table of size 65536 and half as many steps; this is the choice made in agrep.) The running time of this algorithm is where p is the size of the regular expression. If the regular expression is not too large and n is large, the effective running time is O(nk). Here we present some experimental results involving the algorithms discussed in the previous sections. The purpose of these experiments is to show that our algorithms are very efficient for small patterns. We used only patterns that are smaller than the computer word size, thus the comparisons to other algorithms are not general and may not be fair. All tests were run on a SUN SparcStation II running Unix. The numbers given here should be taken with caution. Any such resuits depend on the architecture, the operating system, and the compilers used. Note also that the current version of agrep employs some newer algorithms, so its current We tested the partition algorithm against two other algorithms, one by Ukkonen [20] (which we implemented) and one by Galil and Park [6] (labeled MN2; the program was provided for us by W.I. Chang) which is based on another technique by Ukkonen [21] . These two algorithms are both improvements of the basic dynamic programming algorithm and their expected running time is O(nk). We used random text (of size 1 million) and pattern (of size 20), and two different alphabet sizes. In this case, since we use the idea of partitioning the pattern, the size of the alphabet makes a big difference. A large alphabet leads to very few accidental exact matches, thus the running time is essentially the same as the one for exact matching. A small alphabet leads to many matches and the algorithm's performance degrades. The case of binary alphabet serves as the worst case for this purpose. Results are shown in Table 3 . The second test was for more complicated patterns, including some of the extensions discussed in the previous section. (Anything within the <> brackets must match exactly; a "#" stands for a wild card of arbitrary length; a ";" serves as the Boolean AND operation, namely all patterns must appear within the same line; a "]" is the regular expression union operation; and a "*" is the Kleene closure.) The results are given in Table 4 (the file was a bibliographic text of size 1MB). Another algorithm for approximate matching to arbitrary regular expressions is by Myers and Miller [ 17]. (Recently, we improved some parts of this algorithm [25] .) The running times of the Myers and Miller algorithm for the cases we tested, which include only small regular expressions and small errors, are more than an order of magnitude slower than our algorithm; however, this is not a fair comparison because their algorithm can handle more general cost functions and its running time is independent of the number of errors. Having such flexible algorithms motivated us to develop an approximate matching tool for Unix. Agrep has been in wide use since June 1991, and it has gone through two major revisions. It includes several new algorithms in addition to the ones described in this article (e.g., a new multipattern algorithm and an improved approximate string matching for simple strings). It is used similarly to grep/egrep/ fgrep and it supports most of the features of the grep family (although it is not 100% compatible), but it supports many additional features (mostly but not all related to approximate matching). Agrep is at least as fast and in many cases faster than all other greps that we know of. One notable difference between agrep and the previous greps (besides the ability to search approximately) is that agrep is record oriented (rather than line oriented). A record (e.g., a paragraph, a mail message) is defined by the user (with the default being a line). Agrep outputs all records that match the query (see the -d option described below). Agrep is available, free of charge, by anonymous [24] ). -d 'delim' delim is a user-defined symbol (or string) for record delimiter (the default is the new-line symbol). This enables searching paragraphs (in which case delim = '$$') or mail messages (delim = '^From'). -k finds all occurrences with at most k errors (insertions, deletions, or substitutions), where k is a positive integer. -B finds all matches with minimum number of errors (e.g., if the best match has 2 errors, this is the same as running agrep with -2, but of course 2 is unknown). -Dc each deletion counts as c errors; c must be a nonnegative integer; the default value of c is 1 -Ic each insertion counts as c errors; c must be a nonnegative integer; the default value of c is 1 -Sc each substitution counts as c errors; c must be a nonnegative integer; the default value of c is 1 agrep -1 -I2 -D2 555-1234 phonelist finds all numbers that differ from 555-1234 in at most one digit; setting the cost of insertions and deletions to 2 prevents them in this case. agrep -B -d '$$' Shmidth addresslist finds all addresses (assuming the addresses are separated by a blank line) containing the best match to Shmidth. agrep -d "From ' 'breakdown;arpanet' mail-file outputs all mail messages (the pattern '^From ' separates mail messages in a mail file) that contain breakdown and arpanet (the symbol ; stands for the Boolean AND). agrep -B -w otomaton/usr/dict/ words finds the closest words in the dictionary to otomaton; the -w option forces the match to be against the whole word rather than a part of it. (The best match has two errors and there are two of them: automaton and tomato.) agrep -d '$$' -1 '<wordl > <word2>' finds all paragraphs that contain word 1 followed by word2 with at most one error in place of the blank between the words (the <> indicate that no error is allowed inside). In particular, if wordl is the last word in a line and word2 is the first word in the next line, then the space will be substituted by a new line symbol and it will match. Thus, this is a way to overcome separation by a new line. Note that -d '$$' (or another delim that spans more than one line) is necessary, because otherwise agrep searches only one line at a time. agrep -5 'a#b#c#d#e#f#g#h#i#j' /usr/dict/words finds all words that have at least 5 of the first 10 letters of the alphabet in order; the # sign signals unlimited wild cards, which means here that any insertion is for free (there is actually a special option -p for that purpose). Try it; the answer starts with academia and ends with sacrilegious, which must mean something. Searching text in the presence of errors is commonly done by hand--one tries all possibilities. This is frustrating, slow, and with no guarantee of success. The new algorithm presented in this article for searching with errors can alleviate this problem and make searching in general more robust. It also makes searching more convenient by not having to spell everything precisely. The algorithm is very fast and general and it should find numerous applications. There is one important area of searching with errors that we did not address--searching an indexed file. Throughout the article we assumed that the files are not indexed (preprocessed) in any way, thus a sequential scan through them is necessary. We believe that the problem of finding good indexing schemes that allow approximate search is the unresolved problem in this area. We note, however, that with the speed of current computers, scanning large files (up to tens of MB) can be done reasonably fast. One can argue that since the size of our data increases as our speed of processing it increases, waiting for faster computers will not help and indexing will always be necessary. This is certainly true for some applications, but not for all. Some applications have a reasonable upper bound on their size and sequential search for those applications is (and will remain) realistic. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. ©ACM0002-0782/92/1000-083 $1.50 CARE plants the most wonderful seeds on earth. Seeds of self-sufficiency that help stai'ving people become healthy, productive people. And we do it village by village by village. Please help us turn cries for help into the laughter of hope.
A first solution REF , based on Thompson's construction, uses a table of size O (2 2m ) that can be split into t tables of size O(2 2m/t ) each, at a search cost of O(tn) table inspections.
Fast text searching: allowing errors
CACM
Computer Science