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.