3
\$\begingroup\$

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()
\$\endgroup\$
2
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ Thank you very much :-) It is really cleaner but I need backtracking :'( \$\endgroup\$ – AmirHossein Apr 20 '16 at 7:20
  • \$\begingroup\$ @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. \$\endgroup\$ – coderodde Apr 20 '16 at 7:24
  • \$\begingroup\$ I need to know which word is aligned with which word \$\endgroup\$ – AmirHossein Apr 20 '16 at 7:30
  • \$\begingroup\$ Done. See the extension. \$\endgroup\$ – coderodde Apr 20 '16 at 11:06
  • \$\begingroup\$ @KevinBrown Too much Java. \$\endgroup\$ – coderodde Apr 20 '16 at 12:36

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.