Damerau–Levenshtein distance
From The Art and Popular Culture Encyclopedia
|
Related e |
|
Featured: |
In information theory and computer science, Damerau–Levenshtein distance is a "distance" (string metric) between two strings, i.e., finite sequence of symbols, given by counting the minimum number of operations needed to transform one string into the other, where an operation is defined as an insertion, deletion, or substitution of a single character, or a transposition of two characters. Damerau in his seminal paper not only distinguished these four edit operations but also stated that they correspond to more than 80% of all human misspellings. Damerau concentrated on single-character misspellings. Edit distance was introduced by Levenshtein.
While the original motivation was to measure distance between human misspellings to improve applications such as spell checkers, Damerau-Levenshtein distance has also seen uses in biology to measure the variation between DNA.
