import zlib

def levenshtein(a,b):
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space
        a,b = b,a
        n,m = m,n
        
    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)
            
    return current[n]

def compress(x):
    c = zlib.compress(x, 9)
    # strip headers
    FLG = c[1]
    if ord(FLG) & (1 << 5):
        # DICTID
        c = c[6:]
    else:
        c = c[2:]
    return c[:-4]

def dist(a, b):
    return min(levenshtein(a, b),  levenshtein(compress(a), compress(b)))


print dist("a"*8, "a"*8)
print dist("apple", "appel")
print dist("apple", "bannana")
print dist("a"*100, "b"*100)
print dist("the quick brown fox jumped over the fence", "the quic brown fox jumped over the fence")
print dist("Robert", "Roberto")