Damerau–Levenshtein distance  

From The Art and Popular Culture Encyclopedia

(Redirected from Damerau-Levenshtein)
Jump to: navigation, search

Related e



Kunstformen der Natur (1904) by Ernst Haeckel
Kunstformen der Natur (1904) by Ernst Haeckel

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.

Unless indicated otherwise, the text in this article is either based on Wikipedia article "Damerau–Levenshtein distance" or another language Wikipedia page thereof used under the terms of the GNU Free Documentation License; or on original research by Jahsonic and friends. See Art and Popular Culture's copyright notice.

Personal tools