# Making the Levenshtein distance code cleaner

I was writing an implementation of Levenshtein distance in Python and I found my code really ugly. Have you any idea how to make it more elegant?

import unittest
import enum

def seq_dist(first, second):
Direction = enum.Enum('Direction', 'gap_first gap_second match finish')

def find_dist():
dist_table = [(len(second) + 1) * [0] for i in range(len(first) + 1)]
directions = [(len(second) + 1) * [None] for i in range(len(first) + 1)]
for i in range(len(first) + 1):
for j in range(len(second) + 1):
if (i, j) == (0, 0):
dist_table[i][j] = 0
directions[i][j] = Direction.finish
elif i == 0:
dist_table[i][j] = j
directions[i][j] = Direction.gap_first
elif j == 0:
dist_table[i][j] = i
directions[i][j] = Direction.gap_second
else:
gap_first = dist_table[i - 1][j] + 1
gap_second = dist_table[i][j - 1] + 1
match = dist_table[i - 1][j - 1] + (first[i-1] != second[j-1])
if gap_first <= min(gap_first, match):
dist_table[i][j] = gap_first
directions[i][j] = Direction.gap_second
elif gap_second <= min(gap_second, match):
dist_table[i][j] = gap_second
directions[i][j] = Direction.gap_first
else:
dist_table[i][j] = match
directions[i][j] = Direction.match
return dist_table, directions

def backtrack(directions):
i, j = (len(first), len(second))
seq = []
while directions[i][j] != Direction.finish:
direction = directions[i][j]
if direction == Direction.gap_first:
seq.append((None, second[j-1]))
j -= 1
elif direction == Direction.gap_second:
seq.append((first[i-1], None))
i -= 1
elif direction == Direction.match:
seq.append((first[i-1], second[j-1]))
i -= 1
j -= 1
seq.reverse()
return seq

dist_table, directions = find_dist()

dist = dist_table[-1][-1]
diff = backtrack(directions)

return (dist, diff)

class MatchSeqsTest(unittest.TestCase):
def test_seq_dist(self):
self.assertMatchDist(0, '', '')
self.assertMatchDist(2, 'something cool', '')
self.assertMatchDist(0, 'first', 'first')
self.assertMatchDist(1, 'first', 'first second')
self.assertMatchDist(1, 'fourth second', 'first second')
self.assertMatchDist(1, 'first second third', 'second third')

def assertMatchDist(self, dist, first, second):
self.assertMatchDistOneWay(dist, first, second)
self.assertMatchDistOneWay(dist, second, first)

def assertMatchDistOneWay(self, dist, first, second):
actualDist, actualDiff = seq_dist(first.split(), second.split())
self.assertEqual(dist, actualDist)
self.assertEqual(dist, self.alignment_dist(actualDiff))
self.assertEqual(self.extract_first(actualDiff), first.split())

def extract_first(self, diff):
return [f for f, s in diff if f is not None]

def alignment_dist(self, diff):
return sum(1 for f, s in diff if f != s)

if __name__ == '__main__':
unittest.main()


It would seem that you try to do more than is sufficient for computing the Levenshtein edit distance. You could try this:

def levenshtein_distance(string1, string2):
n = len(string1)
m = len(string2)
d = [[0 for x in range(n + 1)] for y in range(m + 1)]

for i in range(1, m + 1):
d[i][0] = i

for j in range(1, n + 1):
d[0][j] = j

for j in range(1, n + 1):
for i in range(1, m + 1):
if string1[j - 1] is string2[i - 1]:
delta = 0
else:
delta = 1

d[i][j] = min(d[i - 1][j] + 1,
d[i][j - 1] + 1,
d[i - 1][j - 1] + delta)

return d[m][n]

def main():
print(levenshtein_distance("code", "rodde"))

if __name__ == "__main__":
main()


Hope that helps.

Edit

The following extension will also give you the edit sequence, and the alignment of the two input words:

def levenshtein_distance(s, z):
s = "\u0000" + s
z = "\u0000" + z

n = len(s)
m = len(z)
d = [[0 for x in range(n + 1)] for y in range(m + 1)]
parent_map = dict()
parent_map[(0, 0)] = None

for i in range(1, m + 1):
d[i][0] = i

for j in range(1, n + 1):
d[0][j] = j

for j in range(1, n + 1):
for i in range(1, m + 1):
if s[j - 1] is z[i - 1]:
delta = 0
else:
delta = 1

tentative_dist = d[i - 1][j] + 1
operation = 1 # Insert

if tentative_dist > d[i][j - 1] + 1:
tentative_dist = d[i][j - 1] + 1
operation = 2 # Delete

if tentative_dist > d[i - 1][j - 1] + delta:
tentative_dist = d[i - 1][j - 1] + delta
operation = 3

if operation is 1:   # Insert
parent_map[(i, j)] = (i - 1, j)
elif operation is 2: # Delete
parent_map[(i, j)] = (i, j - 1)
else:                # Substitute
parent_map[(i, j)] = (i - 1, j - 1)

d[i][j] = tentative_dist

edit_string_top = ""
edit_string_bottom = ""
edit_sequence = ""

current = (m, n)

while True:
predecessor = parent_map[current]

if not predecessor:
break

if current[0] != predecessor[0] and current[1] != predecessor[1]:
schar = s[predecessor[1]]
zchar = z[predecessor[0]]

edit_string_top += schar
edit_string_bottom += zchar

if schar is zchar:
edit_sequence += "N"
else:
edit_sequence += "S"
elif current[0] != predecessor[0]:
edit_string_top += "-"
edit_string_bottom += z[predecessor[0]]
edit_sequence += "I"
else:
edit_string_top += s[predecessor[1]]
edit_string_bottom += "-"
edit_sequence += "D"

current = predecessor

edit_string_top = edit_string_top[:-1][::-1]
edit_string_bottom = edit_string_bottom[:-1][::-1]
edit_sequence = edit_sequence[:-1][::-1]

return d[m][n], edit_sequence, edit_string_top, edit_string_bottom

def main():
dist, edit_sequence, edit_string_top, edit_string_bottom = levenshtein_distance("handball", "aballad")
print("Distance: ", dist)
print("Edit sequence: ", edit_sequence)
print(edit_string_top)
print(edit_string_bottom)

if __name__ == "__main__":
main()

• Thank you very much :-) It is really cleaner but I need backtracking :'( Apr 20, 2016 at 7:20
• @AmirHossein I suggest you elaborate you question a bit. What exactly do you mean by "backtracking?" Why do you need it? Otherwise, so far so good. Apr 20, 2016 at 7:24
• I need to know which word is aligned with which word Apr 20, 2016 at 7:30
• Done. See the extension. Apr 20, 2016 at 11:06
• @KevinBrown Too much Java. Apr 20, 2016 at 12:36