python - 在 Python 中编辑距离

Question

我正在用 Python 编写拼写检查程序。我有一个有效单词列表(字典)，我需要从该字典输出一个单词列表，这些单词与给定的无效单词的编辑距离为 2。

我知道我需要首先生成一个列表，该列表与无效词的编辑距离为 1(然后对所有生成的词再次运行该列表)。我有三种方法，inserts(...)、deletions(...) 和 changes(...)，它们应该输出编辑距离为 1 的单词列表，其中 inserts 输出所有有效单词，其中字母比对于给定的单词，deletions 输出所有有效单词少一个字母，changes 输出所有有效单词少一个字母。

我检查了很多地方，但似乎找不到描述此过程的算法。我提出的所有想法都涉及多次循环遍历字典列表，这将非常耗时。如果有人能提供一些见解，我将不胜感激。

Answer 1

您正在查看的东西称为编辑距离，这里是 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]

还有一个 couple of more implementations are here .