A Faster Algorithm for 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
O ( log n), being n the maximum size of the text.
The running time achieved is O (n) for small patterns (i.e. of length
m = O (sqrt ( log n))), independently
of the maximum number of errors allowed, k.
This algorithm is then used to design two general algorithms.
One of them partitions the problem into subproblems, while the other
partitions the automaton into sub-automata. These algorithms are
combined to obtain a hybrid algorithm which on average is
O (n) for moderate k/m ratios,
O (sqrt (mk/ log n) n) for
medium ratios, and O ((m-k)kn/ log n) for large ratios.
We show experimentally that this hybrid algorithm is faster
than previous ones for moderate size of patterns and error ratios,
which is the case in text searching.