a0000.blogspot.com: Damerau-Levenshtein distance - Wikipedia, the free encyclopedia

Damerau-Levenshtein distance - Wikipedia, the free encyclopedia

Damerau-Levenshtein distance is a string metric for measuring edit distance in information theory and computer science. Like Levenshtein distance, it finds the difference between two strings by giving the minimum number of operations needed to transform one string into the other where an operation is an insertion, deletion, or substitution of a single character. Unlike Levenshtein distance, it counts transposition as a single edit operation, rather than two. Damerau-Levenshtein distance is therefore equal 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. 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.

1 The algorithm

2 Algorithm discussion

3 See also

4 References

5 External links

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.