在Python中编辑距离
在Python中编辑距离
提问于 2010-03-17 14:02:08
我正在用Python编写一个拼写检查程序。我有一个有效单词的列表(字典)，我需要输出这个字典中与给定无效单词的编辑距离为2的单词列表。
我知道我需要首先生成一个与无效单词的编辑距离为1的列表(然后对所有生成的单词再次运行该距离)。我有三个方法:插入(...)、删除(...)和更改(...)这应该输出一个编辑距离为1的单词列表，其中inserts输出比给定词多一个字母的所有有效单词，deletions输出比给定单词少一个字母的所有有效单词，changes输出一个不同字母的所有有效单词。
我检查了很多地方，但似乎找不到一个描述这一过程的算法。我想出的所有想法都涉及到多次遍历字典列表，这将非常耗时。如果有人能提供一些见解，我将不胜感激。
回答 5
Stack Overflow用户
发布于 2015-09-14 14:52:27
您正在查看的内容称为编辑距离，这是一个nice explanation on wiki。有很多方法可以定义两个单词之间的距离，你想要的是Levenshtein距离，这里是一个用python实现的DP (动态编程)。
def levenshteinDistance(s1, s2):
if len(s1) > len(s2):
s1, s2 = s2, s1
distances = range(len(s1) + 1)
for i2, c2 in enumerate(s2):
distances_ = [i2+1]
for i1, c1 in enumerate(s1):
if c1 == c2:
distances_.append(distances[i1])
else:
distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
distances = distances_
return distances[-1]Stack Overflow用户
发布于 2013-11-12 20:16:50
#this calculates edit distance not levenstein edit distance
word1="rice"
word2="ice"
len_1=len(word1)
len_2=len(word2)
x =[[0]*(len_2+1) for _ in range(len_1+1)]#the matrix whose last element ->edit distance
for i in range(0,len_1+1): #initialization of base case values
x[i][0]=i
for j in range(0,len_2+1):
x[0][j]=j
for i in range (1,len_1+1):
for j in range(1,len_2+1):
if word1[i-1]==word2[j-1]:
x[i][j] = x[i-1][j-1]
else :
x[i][j]= min(x[i][j-1],x[i-1][j],x[i-1][j-1])+1
print x[i][j]Stack Overflow用户
发布于 2021-10-12 19:02:09
我建议不要自己创建这种代码。有相应的库可供使用。
例如Levenshtein库。
In [2]: Levenshtein.distance("foo", "foobar")
Out[2]: 3
In [3]: Levenshtein.distance("barfoo", "foobar")
Out[3]: 6
In [4]: Levenshtein.distance("Buroucrazy", "Bureaucracy")
Out[4]: 3
In [5]: Levenshtein.distance("Misisipi", "Mississippi")
Out[5]: 3
In [6]: Levenshtein.distance("Misisipi", "Misty Mountains")
Out[6]: 11
In [7]: Levenshtein.distance("Buroucrazy", "Born Crazy")
Out[7]: 4页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2460177
复制相关文章
相似问题
腾讯云开发者
