Python : Comment corriger les noms mal orthographiés

Question

J'ai une liste de noms de villes, dont certains sont mal orthographiés :

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

Et une liste avec tous les noms de ville possibles bien orthographiés :

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

Je cherche un algorithme capable de trouver la correspondance la plus proche entre les noms de la première et de la deuxième liste, et de retourner la première liste avec ses noms bien orthographiés. Il devrait donc retourner la liste suivante :

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

Answer 1

Vous pouvez utiliser l'algorithme intégré de Ratcliff et 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']

Où 0,7 est le coefficient de similarité. Il peut faire quelques tests pour votre cas et fixer cette valeur. Il montre à quel point les deux chaînes de caractères sont similaires (1 - c'est la même chaîne, 0 - des chaînes très différentes).

Answer 2

Tout d'abord, vous devriez utiliser les distances de Levenshtein entre les chaînes de caractères, j'ai trouvé un lien avec le suivant Algorithme de distance de Levenshtein pour 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]

Une fois que vous avez compris cela, vous devriez créer une fonction capable de trouver la correspondance la plus proche entre une chaîne de caractères donnée et la liste des noms bien orthographiés.

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 ]

Enfin, il suffit de boucler la première liste avec cette fonction. Le résultat est le suivant :

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

Answer 3

Cela pourrait être un bon cas d'utilisation d'un excellent paquet appelé 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']