levenshtein.py

def distance(a, b):
    if len(b) < len(a):
        a, b = b, a
    r0 = list(range(len(b) + 1))
    r1 = [0] * (len(b) + 1)
    for i in range(len(a)):
        for j in range(len(b)):
            r1[j + 1] = min(r0[j + 1] + 1, r1[j] + 1, r0[j] + (a[i] != b[j]))
        r0, r1 = r1, r0
    return r0[-1]


def pdist(x, func):
    n = len(x)
    out = [0] * ((n * (n - 1)) // 2)
    k = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            out[k] = func(x[i], x[j])
            k += 1
    return out