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 &lt;= min(gap_first, match):
                        dist_table[i][j] = gap_first
                        directions[i][j] = Direction.gap_second
                    elif gap_second &lt;= 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 &gt; d[i][j - 1] + 1:
                tentative_dist = d[i][j - 1] + 1
                operation = 2 # Delete

            if tentative_dist &gt; 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()