Faster Approximate String Matching

Ricardo Baeza-Yates and Gonzalo Navarro

We present a new algorithm for on-line approximate string matching. The algorithm is based on the simulation of a non-deterministic finite automaton built from the pattern and using the text as input. This simulation uses bit operations on a RAM machine with word length w = Omega ( log n) bits, where n is the text size. This is essentially similar to the model used in Wu and Manber's work, although we improve the search time by packing the automaton states differently. The running time achieved is O (n) for small patterns (i.e. whenever mk = O ( log n)), where m is the pattern length and k the number of allowed errors. This is in contrast with the result of Wu and Manber, which is O (kn) for m=O ( log n). Longer patterns can be processed by partitioning the automaton into many machine words, at O (mk/w n) search cost. We allow generalizations in the pattern, such as classes of characters, gaps and others, at essentially the same search cost.
We then explore other novel techniques to cope with longer patterns. We show how to partition the pattern into short subpatterns which can be searched with less errors using the simple automaton, to obtain an average cost close to O ( sqrt (mk/w) n). Moreover, we allow to superimpose many subpatterns in a single automaton, obtaining near O ( sqrt (mk/(sigma w))m n) average complexity (sigma is the alphabet size).
We perform a complete analysis of all the techniques and show how to combine them in an optimal form, obtaining also new tighter bounds for the probability of an approximate occurrence in random text. Finally, we show experimental results comparing our algorithms against previous work. Those experiments show that our algorithms are among the fastest ones for typical text searching, being the fastest in some cases. Although we aim mainly to text searching, we believe that our ideas can be successfully applied to other areas such as computational biology.