0
$\begingroup$

I found some python codes on Damerau Levensthein edit distance through google, but when i look at their comments, many said that the algorithms were incorrect. I'm confused.

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

Thank you.

$\endgroup$
0
$\begingroup$

(Sorry, i don't know how to properly edit the typing with my handphone, my only online device for the time being)

"""The second code is listed below"""

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]
$\endgroup$
  • $\begingroup$ This code is not working. $\endgroup$ – howardpotts Sep 13 at 12:06
0
$\begingroup$

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)]
$\endgroup$
0
$\begingroup$

Which one is correct? (Sorry, i don't know how to properly edit the typing with my handphone, my only online device for the time being)

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]
$\endgroup$
  • $\begingroup$ I tried "zx" to "xyz", the algorithm answers 3, but the correct answer is 2. So this is not working. $\endgroup$ – howardpotts Sep 13 at 12:05
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.