Damerau-Levenshtein Edit Distance in Python

Question

I found some python code on Damerau Levensthein edit distance through Google, but when I looked at their comments, many said that the algorithms were incorrect. I am confused.

Can someone share a correct python code on Damerau Levensthein Distance?

Which one is correct?

https://www.guyrutenberg.com/2008/12/15/damerau-levenshtein-distance-in-python/

The first one:

"""Compute the Damerau-Levenshtein distance between two given strings (s1 and s2)"""


    def damerau_levenshtein_distance(s1, s2):
    
    
        d = {}
        lenstr1 = len(s1)
        lenstr2 = len(s2)
        for i in xrange(-1,lenstr1+1):
            d[(i,-1)] = i+1
        for j in xrange(-1,lenstr2+1):
            d[(-1,j)] = j+1
    
        for i in xrange(lenstr1):
            for j in xrange(lenstr2):
                if s1[i] == s2[j]:
                    cost = 0
                else:
                    cost = 1
                d[(i,j)] = min(
                               d[(i-1,j)] + 1, # deletion
                               d[(i,j-1)] + 1, # insertion
                               d[(i-1,j-1)] + cost, # substitution
                              )
                if i and j and s1[i]==s2[j-1] and s1[i-1] == s2[j]:
                    d[(i,j)] = min (d[(i,j)], d[i-2,j-2] + cost) # transposition
    
        return d[lenstr1-1,lenstr2-1]

I tried "zx" to "xyz", the algorithm answers 3, but the correct answer is 2. So this is not working.

The second one:

https://gist.github.com/pombredanne/0d83ad58f45986ddeb0917266e106be0

Damerau-Levenshtein edit distane implementation

Based on pseudocode from Wikipedia: https://en.wikipedia.org/wiki/Damerau-Levenshtein_distance

Possible improvement by treating 1 addition + 1 deletion = 1 substitution between transposed characters:

Damerau-Levenshtein distance for "abcdef" and "abcfad" = 3:

1. substitute "d" for "f"
2. substitute "e" for "a"
3. substitute "f" for "d"

Or alternatively:

1. transpose "d" and "f"
2. delete "a"
3. insert "e"

It's obvious that (2) and (3) in the second analysis are really just one substitution:

1. transpose "d" and "f"
2. substitute "e" for "a"

With this variant, the distance between "abcdef" and "abcfad" is in fact 2.

def damerau_levenshtein_distance_improved(a, b):

    # "Infinity" -- greater than maximum possible edit distance
    # Used to prevent transpositions for first characters

    INF = len(a) + len(b)

    # Matrix: (M + 2) x (N + 2)
    matrix  = [[INF for n in xrange(len(b) + 2)]]
    matrix += [[INF] + range(len(b) + 1)]
    matrix += [[INF, m] + [0] * len(b) for m in xrange(1, len(a) + 1)]

    # Holds last row each element was encountered: DA in the Wikipedia pseudocode
    last_row = {}

    # Fill in costs
    for row in xrange(1, len(a) + 1):
        # Current character in a
        ch_a = a[row-1]

        # Column of last match on this row: DB in pseudocode
        last_match_col = 0

        for col in xrange(1, len(b) + 1):
            # Current character in b
            ch_b = b[col-1]

            # Last row with matching character
            last_matching_row = last_row.get(ch_b, 0)

            # Cost of substitution
            cost = 0 if ch_a == ch_b else 1

            # Compute substring distance
            matrix[row+1][col+1] = min(
                matrix[row][col] + cost, # Substitution
                matrix[row+1][col] + 1,  # Addition
                matrix[row][col+1] + 1,  # Deletion

                # Transposition
                # Start by reverting to cost before transposition
                matrix[last_matching_row][last_match_col]
                    # Cost of letters between transposed letters
                    # 1 addition + 1 deletion = 1 substitution
                    + max((row - last_matching_row - 1),
                          (col - last_match_col - 1))
                    # Cost of the transposition itself
                    + 1)

            # If there was a match, update last_match_col
            if cost == 0:
                last_match_col = col

        # Update last row for current character
        last_row[ch_a] = row

    # Return last element
    return matrix[-1][-1]

This code is not working.

The psedo code in wikipedia below is not working too. Strings cannot taken as index for k := da[b[j]] and da[a[i]] := i

algorithm DL-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    
    da := new array of |Σ| integers
    for i := 1 to |Σ| inclusive do
        da[i] := 0
    
    let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions length(a)+2, length(b)+2
    // note that d has indices starting at −1, while a, b and da are one-indexed.
    
    maxdist := length(a) + length(b)
    d[−1, −1] := maxdist
    for i := 0 to length(a) inclusive do
        d[i, −1] := maxdist
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[−1, j] := maxdist
        d[0, j] := j
    
    for i := 1 to length(a) inclusive do
        db := 0
        for j := 1 to length(b) inclusive do
            k := da[b[j]]
            ℓ := db
            if a[i] = b[j] then
                cost := 0
                db := j
            else
                cost := 1
            d[i, j] := minimum(d[i−1, j−1] + cost,  //substitution
                               d[i,   j−1] + 1,     //insertion
                               d[i−1, j  ] + 1,     //deletion
                               d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposition
        da[a[i]] := i
    return d[length(a), length(b)]

Thank you.

Answer 1

I have been using the following code and it has served me well so far:

#Calculates the normalized Levenshtein distance of 2 strings
def levenshtein(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    matrix = [list(range(l1 + 1))] * (l2 + 1)
    for zz in list(range(l2 + 1)):
      matrix[zz] = list(range(zz,zz + l1 + 1))
    for zz in list(range(0,l2)):
      for sz in list(range(0,l1)):
        if s1[sz] == s2[zz]:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz])
        else:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1)
    distance = float(matrix[l2][l1])
    result = 1.0-distance/max(l1,l2)
    return result

If you do not need it normalized it should be easy to remove the last parts of the code.

Answer 2

With how old this question is, I hope you've found a working version in the meantime. For those coming along later:

There is a version known as the "restricted edit distance", meaning no sub string can be modified more than once, so it can't do "transpose z and x, then insert y between them", and will have a higher score as a result. Also, the pseudo code uses a negative index, making it hard to write straightforward in Python.

There are a few implementations available in existing python packages. The DamerauLevenshtein class from the textdistance package implements both the restricted and unrestricted version. In this package, the issue of negative indexes is sidestepped by using a tuple as dictionary keys instead of using a list of lists.

There is an implementation of the unrestricted version in the jellyfish package as well. In this implementation, indexes are adjusted to account for not being able to use -1 the same way the pseudo code does, so the code has a lot of offsets added to the indexes.

The version posted by Fnguyen does not have transpositions, so it is only Levenshtein edit distance, not Damerau-Levenshtein edit distance.