Damerau–Levenshtein distance

From Wikipedia, the free encyclopedia

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^[1] 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,^[2] who generalized this concept with multiple edit operations, but did not include transpositions in the set of basic operations.

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.

1 The algorithm
2 Algorithm discussion
- 2.1 Application: DNA
3 See also
4 References
5 External links

[edit] The algorithm

Adding transpositions sounds simple, but in reality there is a serious complication. Firstly, let us consider a direct extension of the formula used to calculate Levenshtein distance. Below is pseudocode for a function DamerauLevenshteinDistance that takes two strings, str1 of length lenStr1, and str2 of length lenStr2, and computes the Damerau-Levenshtein distance between them:

int DamerauLevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
   // d is a table with lenStr1+1 rows and lenStr2+1 columns
   declare int d[0..lenStr1, 0..lenStr2]
   // i and j are used to iterate over str1 and str2
   declare int i, j, cost
 
   for i from 0 to lenStr1
       d[i, 0] := i
   for j from 1 to lenStr2
       d[0, j] := j
 
   for i from 1 to lenStr1
       for j from 1 to lenStr2
           if str1[i] = str2[j] then cost := 0
                                else cost := 1
           d[i, j] := minimum(
                                d[i-1, j  ] + 1,     // deletion
                                d[i  , j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )
           if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
               d[i, j] := minimum(
                                d[i, j],
                                d[i-2, j-2] + cost   // transposition
                             )
                                
 
   return d[lenStr1, lenStr2]

Basically this is the algorithm to compute Levenshtein distance with one additional recurrence:

           if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
               d[i, j] := minimum(
                                d[i, j],
                                d[i-2, j-2] + cost   // transposition
                             )

Let us calculate pair-wise distances between the strings TO, OT and OST using this algorithm. The distance between TO and OT is 1. The same for OT vs. OST. But the distance between TO and OST is 3, even though the strings can be made equal using one deletion and one transposition. Clearly, the algorithm does not compute precisely the value we want. Furthermore, the triangle inequality does not hold.

In reality this algorithm calculates the cost of the so-called optimal string alignment, which does not always equal the edit distance. It is also easy to see that the cost of the optimal string alignment is the number of edit operations needed to make the strings equal under the condition that no substring is edited more than once. We will also call this value a restricted edit distance. As noted by G. Navarro,^[3] in the general case, i.e. when a set of elementary edition operations includes substitutions of arbitrary length strings, unrestricted edit distance is hardly computable. However, the goal is achievable in the simpler case of Damerau–Levenshtein distance. It is also possible (see^[4] for details) to compute unrestricted distance treating reversals of arbitrary, not obligatory adjacent characters as a single edit operation.

To devise a proper algorithm to calculate unrestricted Damerau–Levenshtein distance note that there always exists an optimal sequence of edit operations, where once-transposed letters are never modified afterwards. Thus, we need to consider only two symmetric ways of modifying a substring more than once: (1) transpose letters and insert an arbitrary number of characters between them, or (2) delete a sequence of characters and transpose letters that become adjacent after deletion. The straightforward implementation of this idea gives an algorithm of cubic complexity: $O\left (M \cdot N \cdot \max(M, N) \right )$ , where M and N are string lengths. Using the ideas of Lowrance and Wagner,^[5] this naive algorithm can be improved to be $O\left (M \cdot N \right)$ in the worst case.

It is interesting that the bitap algorithm can be modified to process transposition. See the information retrieval section of^[6] for an example of such an adaptation.

[edit] Algorithm discussion

The above-described pseudo-code calculates only restricted edit distance. Damerau–Levenshtein distance plays an important role in natural language processing. In natural languages, strings are short and the number of errors (misspellings) rarely exceeds 2. In such circumstances, restricted and real edit distance differ very rarely. That is why this limitation is not very important. However, one must remember that restricted edit distance does not always satisfy the triangle inequality and, thus, cannot be used with metric trees. An extension of the edit distance algorithm, that does satisfy the triangle inequality is described in the paper F.J. Damerau. A technique for computer detection and correction of spelling errors, Communications of the ACM, 1964.

[edit] Application: DNA

Since DNA frequently undergoes insertions, deletions, substitutions, and transpositions, and each of these operations occurs on approximately the same timescale, the Damerau-Levenshtein distance is an appropriate metric of the variation between two strands of DNA. More common in DNA, protein, and other bioinformatics related alignment tasks is the use of closely related algorithms such as Needleman-Wunsch or Smith-Waterman.