我正在用 Python 编写一个拼写检查程序。我有一个有效单词列表(字典),我需要从这个字典中输出一个单词列表,这些单词与给定的无效单词的编辑距离为 2。
我知道我需要首先生成一个与无效单词的编辑距离为 1 的列表(然后在所有生成的单词上再次运行该列表)。我有三种方法,inserts(...)、deletions(...) 和 changes(...),它们应该输出编辑距离为 1 的单词列表,其中 inserts 输出所有有效单词,其中的字母多一个给定的单词,deletes 输出所有有效词少一个字母,changes 输出所有有效词少一个字母。
我检查了很多地方,但似乎找不到描述此过程的算法。我提出的所有想法都涉及多次遍历字典列表,这将非常耗时。如果有人能提供一些见解,我将非常感激。
最佳答案
您正在查看的内容称为编辑距离,这里是 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]
关于python - 在 Python 中编辑距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2460177/