Fuzzy string matching?
Moshe Zadka
moshez at server.python.net
Sat Aug 28 13:00:42 EDT 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,
version:
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