Levenshtein Algorithm

The Levenshtein distance between two text strings is the minimum number of single-character edits—insertions, deletions and substitutions—needed to transform one string into the other. It is the best known of the so-called “edit distances”: the smaller it is, the more the two strings resemble each other. For example, turning kitten into sitting costs three edits.

Where it comes from

It was defined by the Soviet mathematician Vladimir Levenshtein in 1965 (its English translation appeared in 1966), in a paper on codes capable of correcting errors. He was the first to formalize this distance and prove that it behaves as a true distance measure.

How it is computed

The computation is done by dynamic programming, filling in a matrix that compares the prefixes of both strings: each cell combines the solutions of the smaller subproblems. The classic algorithm for this is Wagner and Fischer's (1974), and its cost is proportional to the product of the lengths of the two strings. There is even a recent theoretical result suggesting that this quadratic cost is, in essence, unbeatable unless certain conjectures of complexity theory fall.

Properties and relatives

The Levenshtein distance is a metric: it satisfies, among others, the triangle inequality. It has close relatives: the Hamming distance, which allows only substitutions and requires strings of equal length, and the Damerau-Levenshtein distance, which adds a fourth operation, the swap of two adjacent characters, very useful for modeling typing errors.

What it is for

Its applications are numerous: spell checking and autocompletion, approximate matching of strings (fuzzy matching), plagiarism detection and, very prominently, bioinformatics, where comparing DNA sequences is, at bottom, measuring how many mutations—insertions, deletions or substitutions of nucleotides—separate them.