在Python中编辑距离

Question

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

我知道我需要从无效单词生成一个编辑距离为1的列表开始(然后再对所有生成的单词再次运行).我有三个方法,插入(...),删除(...)和更改(...)应输出编辑距离为1的单词列表,其中插入输出所有有效单词多于一个字母的单词给定的单词,删除输出所有有效单词少一个字母,并更改输出所有有效单词和一个不同的字母.

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

Answer 1

您正在查看的内容称为编辑距离,这是对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]

此处还有几个实现.

Answer 2

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

从文档

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

Answer 3

这是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"))

Answer 4

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

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

Answer 6

使用SequenceMatcherPython 内置函数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