Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def nw(a, b):
- """ Returns Levenstein distance of two strings using NW """
- a = ' ' + a
- b = ' ' + b
- class matrix(list):
- """ A cute little matrix object """
- def __init__(self, x, y):
- """ initialize """
- [ self.append([0]*x) for i in range(y) ]
- def __repr__(self):
- """ niceprint """
- return '\n'.join([' '.join([str(j) for j in i]) for i in self ])
- m = matrix(len(a), len(b))
- for f, y in zip(b, range(len(m))):
- for s, x in zip(a, range(len(m[y]))):
- if y is 0 and x is 0:
- continue
- elif y == 0:
- m[y][x] = m[y][x-1] + 1
- elif x == 0:
- m[y][x] = m[y-1][x] + 1
- elif f == s:
- m[y][x] = m[y-1][x-1]
- elif f != s:
- m[y][x] = min([m[y-1][x-1]+1, m[y-1][x]+1, m[y][x-1]+1])
- print m
- print '%s from %s = %s' % (a[1:], b[1:], m[-1][-1])
Add Comment
Please, Sign In to add comment