Lifesum: edit distance

edit.py

# -*- coding: utf-8 -*-
#
#  edit.py
#  code-library
#

"""
Implementation of edit distance.
"""


def distance(lhs, rhs):
    if not lhs or not rhs:
        return max(len(lhs), len(rhs))

    nrows = len(lhs)
    ncols = len(rhs)
    m = [[0 for j in range(ncols)]
         for i in range(nrows)]

    # base case
    m[0][0] = 1 - (lhs[0] == rhs[0])     # substitute

    # first non-recursive row and col
    for j in range(1, len(rhs)):
        m[0][j] = m[0][j - 1] + 1        # insert/delete

    for i in range(1, len(lhs)):
        m[i][0] = m[i - 1][0] + 1        # insert/delete

    # recursive rows
    for i in range(1, len(lhs)):
        for j in range(1, len(rhs)):
            d = 1 - (lhs[i] == rhs[j])
            m[i][j] = min(
                m[i - 1][j] + 1,         # insert/delete
                m[i][j - 1] + 1,         # insert/delete
                m[i - 1][j - 1] + d,     # substitute
            )

    return m[len(lhs) - 1][len(rhs) - 1]

test_edit.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#  test_edit.py
#  code-library
#

import unittest

import edit


class TestEditDistance(unittest.TestCase):
    def test_empty(self):
        self.assertEquals(edit.distance('', ''), 0)

    def test_single(self):
        self.assertEquals(edit.distance('a', ''), 1)
        self.assertEquals(edit.distance('', 'a'), 1)

    def test_word_same(self):
        self.assertEquals(edit.distance('sheep', 'sheep'), 0)

    def test_word_different(self):
        self.assertEquals(edit.distance('sheep', 'ship'), 2)
        self.assertEquals(edit.distance('ship', 'sheep'), 2)

    def test_word_same_prefix(self):
        self.assertEquals(edit.distance('ssslow', 'slow'), 2)
        self.assertEquals(edit.distance('slow', 'ssslow'), 2)

    def test_wikipedia(self):
        self.assertEquals(edit.distance('sitting', 'kitten'), 3)
        self.assertEquals(edit.distance('Saturday', 'Sunday'), 3)