1
$\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$

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)]
| improve this answer | |
$\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]
| improve this answer | |
$\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 '19 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.

| improve this answer | |
$\endgroup$
-1
$\begingroup$

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

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.