edit_distance.py

# http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK2/NODE46.HTM#SECTION02313000000000000000

def edit_distance(pattern, text):
    """Returns the __edit distance__ value between ``pattern`` and ``text``."""
    # n = |P|, m = |T|
    n, m = len(pattern), len(text)
    matrix = [[0] * (m + 1) for i in xrange(n + 1)]

    for i in xrange(n + 1):
        matrix[i][0] = i
    for i in xrange(m + 1):
        matrix[0][i] = i

    for i in xrange(1, n + 1):
        for j in xrange(1, m + 1):
            d = matrix[i - 1][j - 1]
            if not (pattern[i - 1] == text[j - 1]):
                d += 1
            matrix[i][j] = min(d, matrix[i - 1][j] + 1, matrix[i][j - 1] + 1)

    print "\t".join("  " + text)
    pattern2 = " " + pattern
    for i, lst in enumerate(matrix):
        print pattern2[i] + "\t",
        print "\t".join(str(i) for i in lst)

    return matrix[n][m]

d = edit_distance("abcdefghijkl", "bcdeffghixkl")
print "Edit Distance =", d