24 lines
699 B
Python
24 lines
699 B
Python
def levenshteinDistance(str1, str2):
|
|
m = len(str1)
|
|
n = len(str2)
|
|
lensum = float(m + n)
|
|
d = []
|
|
for i in range(m+1):
|
|
d.append([i])
|
|
del d[0][0]
|
|
for j in range(n+1):
|
|
d[0].append(j)
|
|
for j in range(1,n+1):
|
|
for i in range(1,m+1):
|
|
if str1[i-1] == str2[j-1]:
|
|
d[i].insert(j,d[i-1][j-1])
|
|
else:
|
|
minimum = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+2)
|
|
d[i].insert(j, minimum)
|
|
ldist = d[-1][-1]
|
|
ratio = (lensum - ldist)/lensum
|
|
return {'distance':ldist, 'ratio':ratio}
|
|
|
|
print(levenshteinDistance("kitten","sitting"))
|
|
print(levenshteinDistance("rosettacode","raisethysword"))
|