重み付きレーベンシュタイン距離 Weighted Levenshtein Distance

levenshtein.py

def weighted_levenshtein(a, b, insert=1, delete=1, substitute=1):
    len_a = len(a)
    len_b = len(b)
    m = [ [0] * (len_b + 1) for i in xrange(len_a + 1) ]

    for i in xrange(len_a + 1):
        m[i][0] = i * delete

    for j in xrange(len_b + 1):
        m[0][j] = j * insert

    for (i, j) in itertools.product(xrange(1, len_a + 1), xrange(1, len_b + 1)):
        x = 0 if a[i-1] == b[j-1] else substitute
        m[i][j] = min(m[i-1][j] + delete, m[i][j-1] + insert, m[i-1][j-1] + x)
    return m[-1][-1]