Python中的编辑距离

Question

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

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

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

- Mel

---

你可能希望查看Peter Norvig的拼写检查器（http://norvig.com/spell-correct.html），并根据你的需要进行修改。 - Richard Nienaber

本书中的图2.15展示了Levenshtein距离的伪代码。NLTK Python包提供了一个用于计算此距离的函数。 - Renel Chesak

你看过 https://www.geeksforgeeks.org/edit-distance-dp-5/ 吗？ - pedram bashiri

Answer 1

你正在查看的是编辑距离，这里有一个 维基百科上的好解释。有很多方法来定义两个单词之间的距离，你想要的是叫做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]

还有几个更多的实现在这里。

- Salvador Dali

---

DP代表动态规划。 - Nikana Reklawyks

@Salvador Dali 邻近置换不应该返回距离为1吗？上述函数给出 levenshteinDistance("abc","bac") --> 2 - alancalvitti

@alancalvitti 唯一的操作是插入、删除和替换。所以在你的例子中，你需要删除 a，然后在 b 和 c 之间重新插入它。两个操作。 - Simd

你好 :), 你是否有一个版本（或另一个算法的版本），可以在莱文斯坦距离上指定一个上限？（你可以查看我的帖子获取更多细节：https://dev59.com/87joa4cB1Zd3GeqPApDY） - Outcast

Answer 2

difflib标准库中有各种用于序列匹配的实用工具，包括您可以使用的get_close_matches方法。它使用了从Ratcliff和Obershelp改编的算法。

来自文档

>>> from difflib import get_close_matches
>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']

- ryanjdillon

---

...除了这不是编辑/Levenshtein距离。 - MERose

@MERose 我的回答旨在为其他寻求解决相同问题的人提供解决方案，而不是按照作业要求来回答它。这个问题似乎是一个作业题目。 - ryanjdillon

这太棒了！ - dantiston

Answer 3

#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]

- ishaan arora

Answer 4

这是一个关于Levenshtein距离的代码版本

def edit_distance(s1, s2):
    m=len(s1)+1
    n=len(s2)+1
tbl = {}
    for i in range(m): tbl[i,0]=i
    for j in range(n): tbl[0,j]=j
    for i in range(1, m):
        for j in range(1, n):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost)
return tbl[i,j]

print(edit_distance("Helloworld", "HalloWorld"))

该函数通过计算两个字符串之间的编辑距离来衡量它们之间的相似度。具体而言，对于两个字符串s1和s2，它返回需要将s1转换为s2所需的最少编辑次数，其中每次编辑可以是插入、删除或替换字符。

- Santosh

---

你的代码有误。逻辑不合理，应该将 return tbl[i,j] 改为 return tbl[n,m]。 - Artur Krajewski

Answer 5

我建议您不要自己创建这种代码，可以使用相关的库来实现。

例如，使用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

- firelynx

Answer 6

使用 Python 内置的 difflib 中的 SequenceMatcher 是另一种方法，但是（正如评论中正确指出的那样），结果与编辑距离的定义不完全匹配。额外加分：它支持忽略 "junk" 部分（例如空格或标点符号）。

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

- krassowski

---

对'123'和'12345'运行此程序会产生长度为1的required_edits，而编辑距离为2。 - Russ

Answer 7

类似于Santoshi上面的解决方案，但我做了三个更改：

1. 一行初始化而不是五行
2. 不需要单独定义成本（只需使用int（布尔）0或1）
3. 使用乘积而不是双重循环，（最后一个只是美观，双重循环似乎是不可避免的）

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]

- J.Michael

---

您在代码中引用了一个未定义的变量s（即s[i-1]!=s[j-1]）。 - Glenn Slayden

谢谢您进行了更正！同时请注意，在Python中True + n = n+1，False + n = n，因此无需显式转换为'type' int'。 - J.Michael

Answer 8

跟进 @krassowski 的回答

from difflib import SequenceMatcher

def sequence_matcher_edits(word_a, word_b):
  required_edits = [code for code in (
      SequenceMatcher(a=word_a, b=word_b, autojunk=False).get_opcodes()
    )
    if code[0] != 'equal'
  ]
  return len(required_edits)

print(f"sequence_matcher_edits {sequence_matcher_edits('kitten', 'sitting')}")
# -> sequence_matcher_edits 3

- Harry Moreno

Answer 9

与其使用Levenshtein距离算法，不如使用BK树或Trie树，因为这些算法的复杂度比编辑距离低。对这些主题进行深入浏览将会得到详细的描述。

这个链接将更好地帮助您进行拼写检查。

- jt26

Answer 10

根据@Santosh的版本进行了代码微调，应该解决了@Artur Krajewski提出的问题；最大的区别是替换了一个有效的二维矩阵

def edit_distance(s1, s2):
# add a blank character for both strings
    m=len(s1)+1
    n=len(s2)+1
# launch a matrix
    tbl = [[0] * n for i in range(m)] 
    for i in range(m): tbl[i][0]=i
    for j in range(n): tbl[0][j]=j

    for i in range(1, m):
        for j in range(1, n):
#if strings have same letters, set operation cost as 0 otherwise 1
            cost = 0 if s1[i-1] == s2[j-1] else 1
#find min practice
            tbl[i][j] = min(tbl[i][j-1]+1, tbl[i-1][j]+1, tbl[i-1][j-1]+cost)
    return tbl

edit_distance("birthday", "Birthdayyy")

- Zac S.Y