Damerau-Levenshtein Distance Algorithm

The Damerau-Levenshtein distance, named after Frederick Damerau and Vladimir Levenshtein, is a string metric measuring the edit distance between two sequences as the minimum number of insertions, deletions, substitutions of a single character, or transpositions of two adjacent characters required to change one word into the other. It differs from the classical Levenshtein distance specifically by including transpositions among its allowed operations alongside the three classical single-character edits. In his original paper, Damerau reported that in an investigation of spelling errors in an information-retrieval system, more than 80 percent were the result of a single error of one of these four types, and while the metric's original motivation was to measure the distance between human misspellings for applications such as spell checkers, it has since also been used in biology to measure variation between protein sequences.