# Damerau-Levenshtein Edit Distance in Python

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.

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)]


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]

• I tried "zx" to "xyz", the algorithm answers 3, but the correct answer is 2. So this is not working. – howardpotts Sep 13 '19 at 12:05

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.

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

# 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] +  * 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][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. – howardpotts Sep 13 '19 at 12:06