Das deutsche Python-Forum

Code: Alles auswählen

def dist_lev(a, b):
    """
    Calculates the Levenshtein distance between a and b.
    Written by Magnus Lie Hetland (hetland.org)
    """
    n, m = len(a), len(b)
    if n > m:
        a,b = b,a
        n,m = m,n

    current = range(n+1)
    dummy = [n] * (n+1)
    for i in range(1,m+1):
        previous =  current
        current = dummy[:]
        current[0] = i
        for j in range(1, n+1):
            add = previous[j]+1
            delete = current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]: change += 1
            current[j] = min(add, delete, change)
            
    return current[n]

def dist_ratio(a, b):
    s = difflib.SequenceMatcher(None, a, b)
    return s.ratio()

Code: Alles auswählen

>>> a = 'Meier'
>>> b = 'Mayer'
>>> dist_lev(a,b)
2
>>> dist_ratio(a,b)
0.59999999999999998
>>> dist_lev(a,a)
0
>>> dist_ratio(a,a)
1.0