DamerauLevenshtein

Damerau–Levenshtein distance is a string metric for measuring the difference between two sequences. It quantifies the minimum number of edit operations required to transform one string into the other. The standard operations are insertion, deletion, and substitution, and the Damerau extension adds the transposition of two adjacent characters as a single operation. This makes the distance more permissive than the Levenshtein distance for strings that differ by swapped letters.

Two related variants are commonly discussed. The true Damerau–Levenshtein distance allows arbitrarily many edits on overlapping substrings and is a true metric; computing it is more involved. The Optimal String Alignment distance, sometimes called restricted DL distance, constrains edits so that no substring is edited more than once, and is easier to compute with a simpler dynamic programming approach. In practice, the true distance and the restricted distance may yield different values for the same pair of strings.

Computationally, both versions can be computed by dynamic programming. The standard DP algorithm runs in O(nm) time and O(nm) space for the true distance; variants exist to reduce space usage to O(min(n, m)) with slight time trade-offs. The distance is widely used in spell checking, OCR post-processing, fuzzy matching, and natural language processing, where tolerant matching helps identify intended words despite typographical errors and transpositions.

Origin and usage: the method is named after Frederick J. Damerau and Vladimir Levenshtein; Damerau proposed transposition in 1964, Levenshtein introduced the edit distance in the 1960s. Today, the Damerau–Levenshtein distance remains a standard tool in text processing and computational linguistics for assessing string similarity and guiding correction and search algorithms.