gistfile1.py

def distance(a,b):
    c = {}
    n = len(a); m = len(b)
    for i in range(0, n+1):
        c[i, 0] = i
    for j in range(0, m+1):
        c[0, j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            x = c[i-1, j]+1
            y = c[i, j-1]+1
            if a[i-1] == b[j-1]:
                z = c[i-1, j-1]
            else:
                z = c[i-1, j-1]+1
            c[i,j] = min(x, y, z)
    return c[n,m]

def relative(a, b):
    d = distance(a,b)
    longer = float(max(len(a), len(b)))
    shorter = float(min(len(a), len(b)))
    r = ((longer-d) / longer) * (shorter / longer)
    return r