Python: 如何更正拼错的名字

Question

我有一个城市名称列表，其中一些拼写错误：

['bercelona', 'emstrdam', 'Praga']

还有一个包含所有可能的城市名称的列表：

['New York', 'Amsterdam', 'Barcelona', 'Berlin', 'Prague']

我正在寻找一种算法，该算法能够找到第一个和第二个列表名称之间最接近的匹配项，return第一个列表的名称拼写正确。所以它应该 return 以下列表：

['Barcelona', 'Amsterdam', 'Prague']

Answer 1

首先，你应该在字符串之间使用 Levenshtein 距离，我发现一个 link 具有以下 Levenshtein Distance Algorithm for Python:

# Define Levenshtein distance function (from the mentioned link)
def levenshtein(s1, s2):
    if len(s1) < len(s2):
        return levenshtein(s2, s1)

    if len(s2) == 0:
        return len(s1)

    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1 
            deletions = current_row[j] + 1  
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row

    return previous_row[-1]

一旦你得到这个，你应该创建一个函数来找到给定字符串和名称拼写正确的列表之间最接近的匹配项。

names_list = ['bercelona', 'emstrdam', 'Praga']
good_names = ['New York', 'Amsterdam', 'Barcelona', 'Berlin', 'Prague']

# Define a function that returns the best match
def get_closest_match(name, real_names):
    levdist = [levenshtein(name, real_name) for real_name in real_names]
    for i in range(len(levdist)):
        if levdist[i] == min(levdist):
            return real_names[i]

# Loops the first list
final_list = [ get_closest_match(name, good_names) for name in names_list ]

最后你只需要用这个函数循环第一个列表。结果如下：

>>> print final_list
['Barcelona', 'Amsterdam', 'Prague']

Answer 2

这可能是名为 fuzzywuzzy 的优秀软件包的一个很好的用例。

from fuzzywuzzy import fuzz
import numpy as np

bad = ['bercelona', 'emstrdam', 'Praga']

good = ['New York', 'Amsterdam', 'Barcelona', 'Berlin', 'Prague']

# you can even set custom threshold and only return matches if above certain
# matching threshold
def correctspell(word, spellcorrect, thresh = 70):
    mtchs = map(lambda x: fuzz.ratio(x, word) if fuzz.ratio(x, word) > thresh else None, spellcorrect)
    max = np.max(mtchs)
    if max is not None:
        return spellcorrect[mtchs.index(max)]
    else:
        return None

# get correct spelling
map(lambda x: correctspell(x, good, thresh = 70), bad) # ['Barcelona', 'Amsterdam', 'Prague']

Answer 3

您可以使用内置的 Ratcliff 和 Obershelp 算法：

def is_similar(first, second, ratio):
    return difflib.SequenceMatcher(None, first, second).ratio() > ratio


first = ['bercelona', 'emstrdam', 'Praga']
second = ['New York', 'Amsterdam', 'Barcelona', 'Berlin', 'Prague']

result = [s for f in first for s in second if is_similar(f,s, 0.7)]
print result
['Barcelona', 'Amsterdam', 'Prague']

其中 0.7 是相似系数。它可能会为您的案例做一些测试并设置这个值。它显示了两个字符串的相似程度（1 - 相同的字符串，0 - 非常不同的字符串）

Python: 如何更正拼错的名字

Python: How to correct misspelled names

python

spell-checking