Расстояние Левенштейна (редакционное расстояние)

from numpy import array

def lev_dist(_s, _t):
    if _s == _t: return 0
    s,t = '',''
    if len(_s) > len(_t):
        s = str(_s)
        t = str(_t)
    else:
        s = str(_t)
        t = str(_s)
    sl = len(s)
    tl = len(t)
    if sl == 0: return tl
    if tl == 0: return sl
    v0 = array((tl+1)*[0])
    v1 = array((tl+1)*[0])
    for i in range(len(v0)):
        v0[i] = i
    for i in range(sl):
        v1[0] = i + 1
        for j in range(tl):
            cost = 0
            if s[i] != t[j]: cost = 1
            v1[j+1] = min(v1[j]+1,\
                          v0[j+1]+1,\
                          v0[j]+cost)
        for j in range(len(v0)):
            v0[j] = v1[j]
    return v1[tl]

Разукрашено на tohtml.com