Very Fast and Simple Approximate String Matching
Gonzalo Navarro and Ricardo Baeza-Yates
We improve the fastest known algorithm for approximate string matching, which
can only be used for low error levels. By using a new
method to verify potential matches and a new optimization technique for
biased texts (such as English), the algorithm also becomes the fastest
one for medium error levels. This includes most of the interesting cases
in this area.