Levenshtein distance

edit_distance.py

def memo(f):
    """Basic memoizer for positional parameters."""
    table = {}

    def _f(*args):
        if (args) not in table:
            table[(args)] = f(*args)
        return table[(args)]

    return _f


def edit_distance(s, t):
    """Compute the Levenshtein distance between two sequences."""
    def diff(i, j):
        return 1 if s[i - 1] != t[j - 1] else 0

    @memo
    def aux(i, j):
        if i == 0:
            return j

        if j == 0:
            return i

        insert = aux(i - 1, j) + 1
        delete = aux(i, j - 1) + 1
        replace = aux(i - 1, j - 1) + diff(i, j)

        return min(insert, delete, replace)

    return aux(len(s), len(t))