Distância de Levenshtein
A distância de Levenshtein é uma métrica de string para medir a diferença entre duas sequências. Normalmente, a distância Levenshtein entre duas palavras é o número mínimo de edições de um caractere (inserção, exclusão, substituição) necessárias para transformar uma palavra na outra.
Definição
def levenshtein(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 ratio, ldistEncontrar uma palavra em uma string:
def levenshteinPartial(str1, str2):
if len(str2) < len(str1):
a = str1
str1 = str2
str2 = a
diff = len(str2) - len(str1)
if diff == 0:
return levenshtein(str1, str2)
ret = None
for i in range(0,diff+1):
v = levenshtein(str1, str2[i:len(str1)+i])
if ret == None:
ret = v
elif v[0] > ret[0]:
ret = v
return ret