levenshtein.py

def levenshtein_distance(a, b):
    """
    Compute the Levenshtein distance between a and b.
    (https://en.wikipedia.org/wiki/Levenshtein_distance) Uses an
    efficient dynamic programming implementation.
    """

    m = [ [ 0 for _ in range(len(a) + 1) ] for _ in range(len(b) + 1) ]

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

    for j in range(1, len(b) + 1):
        m[j][0] = j

    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            (_, left, up, diag) = neighbors(m, i, j)
            m[j][i] = min(diag + (0 if a[i-1] == b[j-1] else 1), left + 1, up + 1)

    return m[j][i]