Python: Как исправить орфографические ошибки имена

Question

У меня есть список с названиями городов, которые некоторые из них с орфографической ошибкой:

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

и список всех возможных названий городов хорошо прописано:

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

Я ищу алгоритм, способный найти самое близкое совпадение между именами первого и второго списков и возвращает первый список с его хорошо записанными именами. Таким образом, он должен вернуть следующий список:

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

Answer 1

Вы можете использовать встроенный алгоритм Ратклифа и 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 - очень разные строки)

Answer 2

Во-первых, вы должны использовать расстояния Левенштейна между строк, я нашел ссылку со следующей 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 3

Это может быть хорошо использовать случай большой пакет под названием 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']