Levenshtein distance

In short: The Levenshtein distance counts the minimum number of single-character insertions, deletions and substitutions needed to turn one word into another.

In more detail: “kitten” → “sitting” has distance 3 (k→s, e→i, append g). It underlies spell checking, “did you mean …?” and fuzzy search.

In Depth

• Method: Dynamic programming with a table d[i][j] for the distance between the first i characters of A and the first j characters of B.
• Recurrence: d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + (a[i]≠b[j])).
• Cost: O(m·n) time, O(min(m, n)) memory when keeping only two rows.
• Variants: Damerau-Levenshtein also counts swapping adjacent characters. Hamming distance applies only to words of equal length.
• In practice: For big dictionaries one uses indexes such as BK-trees or n-grams instead of comparing every word.

See also: Text search algorithms