Damerau–Levenshtein distance

Damerau-Levenshtein distance is an extension of Levenshtein distance that counts transposition as a single edit operation. Strictly speaking, Damerau-Levenshtein distance equals to the minimal number of insertions, deletions, substitutions and transpositions needed to transform one string into the other. 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. It is worth noting that Damerau concentrated on single-character misspellings. The edit distance itself was introduced by Levenshtein ^[2] , who generalized this concept by allowing multiple edit operation, but did not include transpositions into a set of basic operations.

The algorithm

Adding transpositions sounds simple, but in reality there is a serious complication. Firstly, let us consider a direct extension of 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 0 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 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 among strings TO, OT and OST using this algorithm. Distance between TO and OT is 1. The same is for OT and OST. But the distance between TO and OST equals to 3, even though strings can be made equal using one deletion and one transposition. Clearly, the algorithm does not compute the value we want. Obviously, triangle inequality is also broken.

In reality this algorithm calculates the cost of the so-called optimal string alignment, which does not always equal to the edit distance. It is also easy to see, that the cost of optimal string alignment is the number of edit operations needed to make strings equal under a 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 a general case, e.g. 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 that treats 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 to modify substring more than once: transpose letters and insert arbitrary number of characters between them, delete a sequence of characters and transpose letters that become adjacent after deletion. The straightforward implementation of this idea gives an algorithm of qubic complexity: $O\left(M\star N\star \max(M,N)\right)$ , where M and N are string lengths. Using ideas of Lowrance and Wagner ^[5], this naive algorithm can be improved to be $O\left(M\star N\right)$ in the worst case.

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

Algorithm discussion

The above-described pseudo-code calculates only a restricted edit distance. Damerau-Levenshtein distance plays an important role in natural language processing. It is worth noting, that 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 triangle inequality and, thus, cannot be used with metric trees.

References

^ F.J. Damerau. A technique for computer detection and correction of spelling errors, Communications of the ACM, 1964
^ V.I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 1966.
^ R. Lowrance, R. Wagner. An Extension of the String-to-String Correction Problem, JACM, 1975.
^ G. Navarro. A guided tour to approximate string matching. ACM Computing Surveys (CSUR) archive 33(1), pp 31-88, 2001.

External links

^ Site devoted to fuzzy searching and information retrieval

The algorithm

Algorithm discussion

See also

References

External links