Python: trouver la chaîne la plus proche (d'une liste) par rapport à une autre chaîne

Question

Supposons que j'ai une chaîne "Hello" et une liste

words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo','question', 'Hallo', 'format']

Comment puis-je trouver les n mots les plus proches de "Hello" et présents dans la liste words ?

Dans ce cas, nous aurions ['hello', 'hallo', 'Hallo', 'hi', 'format'...]

Donc la stratégie est de trier la liste des mots du plus proche au plus éloigné.

J'ai pensé à quelque chose comme ceci

mot = 'Hello'
for i, item in enumerate(words):
    if lower(item) > lower(mot):
      ...

mais c'est très lent avec de grandes listes.

MISE À JOUR difflib fonctionne mais c'est aussi très lent. (La liste de mots contient plus de 630000 mots (triés et un par ligne)). Donc vérifier la liste prend 5 à 7 secondes pour chaque recherche de mot le plus proche !

Answer 1

Utilisez difflib.get_close_matches.

>>> words = ['bonjour', 'Hallo', 'salut', 'maison', 'clé', 'écran', 'hallo', 'question', 'format']
>>> difflib.get_close_matches('Hello', words)
['hello', 'Hallo', 'hallo']

Veuillez consulter la documentation, car la fonction renvoie par défaut 3 ou moins de correspondances les plus proches.

Answer 2

Il y a un article génial avec un code source complet (21 lignes) fourni par Peter Norvig sur la correction orthographique.

http://norvig.com/spell-correct.html

L'idée est de construire toutes les éditions possibles de votre mot,

hello - helo   - supprimer    
hello - helol  - transposer    
hello - hallo  - remplacer    
hello - heallo - insérer    

def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in splits if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a + c + b     for a, b in splits for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

Maintenant, recherchez chaque une de ces éditions dans votre liste.

L'article de Peter est une excellente lecture et vaut la peine d'être lu.

Answer 3

Créez une liste triée de vos mots et utilisez le module bisect pour identifier le point dans la liste triée où votre mot s'intégrerait selon l'ordre de tri. En fonction de cette position, vous pouvez donner les k voisins les plus proches au-dessus et en-dessous pour trouver les 2k mots les plus proches.

Answer 4

J'ai examiné cette réponse pour obtenir une correspondance la plus proche dans une liste d'alternatives possibles de

difflib.get_close_matches

J'ai trouvé la réponse d'Amjith basée sur le post de Peter Norwig et j'ai pensé que cela pourrait être un bon remplacement. Avant de réaliser que cela pourrait ne pas convenir tout à fait à mon cas d'utilisation, j'en avais fait une classe. Donc voici une version de spell où vous pouvez l'utiliser pour différents ensembles de mots. Le meilleur usage peut être pour la correspondance de noms de population.

import re
from collections import Counter

def words(text): return re.findall(r'\w+', text.lower())

# WORDS = Counter(words(open('big.txt').read()))

class WordMatcher:

    def __init__(self, big_text):
        self.WORDS=Counter(words(big_text))
        self.N = sum(self.WORDS.values())

    def P(self, word):
        "Probabilité du mot."
        return self.WORDS[word] / self.N

    def correction(self, word):
        "Correction d'orthographe la plus probable pour le mot."
        return max(self.candidates(word), key=self.P)

    def candidates(self, word):
        "Générer des corrections d'orthographe possibles pour le mot."
        return (self.known([word]) or self.known(self.edits1(word)) or self.known(self.edits2(word)) or [word])

    def known(self, words):
        "Le sous-ensemble de `words` qui apparaissent dans le dictionnaire de WORDS."
        return set(w for w in words if w in self.WORDS)

    def edits1(self, word):
        "Tous les édite qui sont à une édition de `word`."
        letters    = 'abcdefghijklmnopqrstuvwxyz'
        splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
        deletes    = [L + R[1:]               for L, R in splits if R]
        transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
        replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
        inserts    = [L + c + R               for L, R in splits for c in letters]
        return set(deletes + transposes + replaces + inserts)

    def edits2(self, word):
        "Tous les édite qui sont à deux éditions de `word`."
        return (e2 for e1 in self.edits1(word) for e2 in self.edits1(e1))

Answer 5

Peut-être heap peut vous aider .

vous avez un tas nommé Heap et tant que sa taille est inférieure à n , vous insérez des mots dans le Heap en utilisant la fonction close [montre si cette chaîne est plus proche d'une autre chaîne ou non] .

cette méthode peut vous aider lorsque n est petit :)

Heap = []
pour mot dans mots:
    si len(Heap)