# Damerau-Levenshtein Edit Distance in Python

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:

# 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.

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.

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.

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.