Approximate string matching

Approximate string matching, often called fuzzy string searching, is the technique of finding strings that match a pattern approximately rather than exactly. The problem is usually split into finding approximate substring matches inside a given string and finding dictionary strings that match the pattern approximately. Closeness is measured by the edit distance, the number of primitive operations such as insertion, deletion, substitution and sometimes transposition needed to turn a string into an exact match. A brute-force solution takes cubic time, while the solution proposed by Sellers uses dynamic programming and takes time proportional to the product of pattern and text length. Wagner and Fischer gave a related dynamic programming algorithm for Levenshtein distance. Later work includes the bitap algorithm used in the Unix utility agrep, algorithms whose cost depends on a bound k on the edit distance, and similarity joins for large data collections.