Skip to content

Instantly share code, notes, and snippets.

@brwnj
Last active August 29, 2015 13:56
Show Gist options
  • Save brwnj/9194075 to your computer and use it in GitHub Desktop.
Save brwnj/9194075 to your computer and use it in GitHub Desktop.
brute force for best edit distance
import editdist
def distance(a, b):
"""
Find best edit distance between two strings of potentially uneven length.
>>> import editdist
>>> distance("abc", "abc")
0
>>> distance("abc", "abcdef")
0
>>> distance("abbb", "abcdef")
2
"""
# first position longer
ab = sorted([a, b], key=len, reverse=True)
assert all(isinstance(s, basestring) for s in ab)
length_longer, length_shorter = len(ab[0]), len(ab[1])
if length_longer == length_shorter:
d = editdist.distance(ab[0], ab[1])
else:
dists = set()
difference = length_longer - length_shorter
for i in xrange(0, difference + 1):
d = editdist.distance(ab[0][i:i + length_shorter], ab[1])
# perfectly matching substring
if d == 0:
break
dists.add(d)
if d != 0:
d = min(dists)
return d
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment