Fuzzy string matching?

Moshe Zadka moshez at server.python.net
Sat Aug 28 19:00:42 CEST 1999

On 28 Aug 1999, Magnus L. Hetland wrote:

[about "diff" style algorithms]
> A new and improved version:
[snipped code]

> Could perhaps be a bit more readable, though... (Maybe I'll work on
> that...)

No need, my good man. We have a saying in Hebrew "The work of the rightous
gets done by others"

Added a comment, made a few variables more meaningful, precalculated
ranges, changed some ; to , and here is the changed, and a bit tested,

def distance(a,b):
        n, m = map(len, (a,b))
        if n>m:  # Make sure n<=m
                a,b,n,m = b,a,m,n
        range_m, range_n= map(range, (m, n))
        curr = range(0, n+1)
        for i in range_m:
                prev, curr = curr, [i+1]
                for j in range_n:
                        add, dele = prev[j+1]+1, curr[j]+1
                        change = prev[j] + (a[j]!=b[i] and 1 or 0)
                        curr.append(min(add, dele, change))
        return curr[n]

Well, in the hope I haven't gotten any bugs on the way in, use it to your
hearts satisfaction folks

More information about the Python-list mailing list