levenshtein

Levenshtein distance, commonly called edit distance, is a metric for measuring how dissimilar two strings are by counting the minimum number of single-character edits required to transform one string into the other. The permissible edits typically are insertions, deletions, and substitutions of a single character, each with a cost of one. A variant, the Damerau-Levenshtein distance, also allows transpositions of two adjacent characters with a cost of one.

History: The distance is named after Vladimir Levenshtein, who introduced it in 1965 in studies of error-correcting codes. It has since become a fundamental tool in string processing and bioinformatics.

Algorithm: The standard computation uses dynamic programming. Given strings A of length n and B of length m, construct a (n+1) by (m+1) matrix d where d[i][j] is the distance between the prefixes A[:i] and B[:j]. Initialize d[i][0] = i and d[0][j] = j. For each i, j, set cost = 0 if A[i-1] == B[j-1], else 1. Then d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + cost). The result is d[n][m]. Time complexity is O(nm); memory can be reduced to O(min(n,m)) with a rolling array.

Variants and related measures: Weighted Levenshtein distances use different costs for insertion, deletion, and substitution. Normalized forms such as similarity scores or ratios can be derived from the distance. Damerau-Levenshtein distance generalizes this further by including transpositions.

Applications: It is widely used in spell checking, fuzzy string matching, search and autocomplete, OCR error correction, DNA and protein sequence comparison, and various natural language processing tasks.

See also: edit distance; Damerau-Levenshtein distance.