我正在用 Python 编写一个拼写检查程序。我有一个有效单词列表（字典），我需要从这个字典中输出一个单词列表，这些单词与给定的无效单词的编辑距离为 2。
我知道我需要首先生成一个与无效单词的编辑距离为 1 的列表（然后在所有生成的单词上再次运行该列表）。我有三种方法，inserts(...)、deletions(...) 和 changes(...)，它们应该输出编辑距离为 1 的单词列表，其中 inserts 输出所有有效单词，其中的字母多一个给定单词，deletions 输出所有有效单词少一个字母，changes 输出所有有效单词少一个字母。
我检查了很多地方，但似乎找不到描述此过程的算法。我提出的所有想法都涉及多次遍历字典列表，这将非常耗时。如果有人能提供一些见解，我将非常感激。
您正在查看的内容称为编辑距离，这是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]
这里还有几个实现。
difflib标准库中有各种用于序列匹配的实用程序，包括get_close_matches您可以使用的方法。它使用改编自 Ratcliff 和 Obershelp 的算法。
从文档
>>> from difflib import get_close_matches
>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
这是我的 Levenshtein 距离版本
def 编辑距离（s1，s2）：
m=len(s1)+1
n=len(s2)+1
tbl = {}
对于范围内的 i (m)：tbl[i,0]=i
对于范围（n）中的 j：tbl[0,j]=j
对于范围内的 i (1, m)：
对于范围内的 j (1, n)：
成本 = 0 如果 s1[i-1] == s2[j-1] 否则 1
tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost)
返回 tbl[i,j]
打印（编辑距离（“你好世界”，“你好世界”））
#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]
我建议不要自己创建这种代码。有图书馆。
例如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
使用SequenceMatcherfrom Python 内置difflib是另一种方法，但是（正如评论中正确指出的那样），结果与编辑距离的定义不完全匹配。奖励：它支持忽略“垃圾”部分（例如空格或标点符号）。
from difflib import SequenceMatcher
a = 'kitten'
b = 'sitting'
required_edits = [
code
for code in (
SequenceMatcher(a=a, b=b, autojunk=False)
.get_opcodes()
)
if code[0] != 'equal'
]
required_edits
# [
# # (tag, i1, i2, j1, j2)
# ('replace', 0, 1, 0, 1), # replace a[0:1]="k" with b[0:1]="s"
# ('replace', 4, 5, 4, 5), # replace a[4:5]="e" with b[4:5]="i"
# ('insert', 6, 6, 6, 7), # insert b[6:7]="g" after a[6:6]="n"
# ]
# the edit distance:
len(required_edits) # == 3
与上面 Santoshi 的解决方案类似，但我做了三处更改：
from itertools import product
def edit_distance(s1,s2):
d={ **{(i,0):i for i in range(len(s1)+1)},**{(0,j):j for j in range(len(s2)+1)}}
for i, j in product(range(1,len(s1)+1), range(1,len(s2)+1)):
d[i,j]=min((s1[i-1]!=s2[j-1]) + d[i-1,j-1], d[i-1,j]+1, d[i,j-1]+1)
return d[i,j]
而不是使用 Levenshtein 距离算法使用BK 树或TRIE，因为这些算法比编辑距离更复杂。对这些主题的良好浏览将给出详细的描述。
此链接将帮助您更多地了解拼写检查。
您需要此任务的最小编辑距离。
以下是我的 MED 版本，即 Levenshtein Distance。
def MED_character(str1,str2):
cost=0
len1=len(str1)
len2=len(str2)
#output the length of other string in case the length of any of the string is zero
if len1==0:
return len2
if len2==0:
return len1
accumulator = [[0 for x in range(len2)] for y in range(len1)] #initializing a zero matrix
# initializing the base cases
for i in range(0,len1):
accumulator[i][0] = i;
for i in range(0,len2):
accumulator[0][i] = i;
# we take the accumulator and iterate through it row by row.
for i in range(1,len1):
char1=str1[i]
for j in range(1,len2):
char2=str2[j]
cost1=0
if char1!=char2:
cost1=2 #cost for substitution
accumulator[i][j]=min(accumulator[i-1][j]+1, accumulator[i][j-1]+1, accumulator[i-1][j-1] + cost1 )
cost=accumulator[len1-1][len2-1]
return cost