Algorithme de comparaison de mots (non alphabétique)

Question

Je dois coder une solution pour une certaine exigence, et je voulais savoir si quelqu'un connaissait une bibliothèque disponible dans le commerce ou pouvait me diriger la meilleure pratique. Description:

L'utilisateur saisit un mot qui est supposé être l'une des nombreuses options fixes (je garde les options dans une liste). Je sais que l'entrée doit être dans un membre de la liste, mais comme il s'agit d'une entrée de l'utilisateur, il/elle peut avoir fait une erreur. Je cherche un algorithme qui me dira quel est le mot le plus probable que l'utilisateur ait voulu dire. Je n'ai aucun contexte et je ne peux pas forcer l'utilisateur à choisir parmi une liste (c'est-à-dire qu'il doit être capable de saisir le mot librement et manuellement). Par exemple, disons que la liste contient les mots «eau», «quartier», «bière», «betterave», «enfer», «bonjour» et «aardvark».

La solution doit tenir compte des différents types d'erreurs « normales »:

• fautes de frappe de vitesse (par exemple caractères doubler, laissant tomber des caractères, etc.)
• clavier de fautes de frappe à côté caractères (par exemple « Qater » pour « l'eau «)
• fautes de frappe Anglais non-indigènes (par exemple "quater" pour « trimestre »)
• Et ainsi de suite ...

La solution évidente consiste à comparer lettre par lettre et à donner des «poids de pénalité» à chaque lettre différente, lettre supplémentaire et lettre manquante. Mais cette solution ignore des milliers d'erreurs «standard» dont je suis sûr qu'elles sont répertoriées quelque part. Je suis sûr qu'il existe des heuristiques qui traitent de tous les cas, à la fois spécifiques et généraux, en utilisant probablement une grande base de données de discordances standard (je suis ouvert aux solutions lourdes de données).

Je suis en train de coder en Python mais je considère cette question comme étant indépendante de la langue.

Des recommandations/pensées?

Answer 1

Vous voulez lire comment Google ceci: http://norvig.com/spell-correct.html

Edit: Certaines personnes ont mentionné des algorithmes qui définissent une mesure entre un mot donné d'utilisateur et un mot candidat (Levenshtein, soundex). Ceci n'est cependant pas une solution complète au problème, car il faudrait aussi une infrastructure de données pour effectuer efficacement une recherche non-euclidienne du plus proche voisin. Cela peut être fait par exemple. avec l'arbre Cover: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

Answer 2

Avez-vous considéré des algorithmes qui se comparent par des sons phonétiques, tels que soundex? Il ne devrait pas être trop difficile de produire des représentations soundex de votre liste de mots, de les stocker, puis d'obtenir un soundex de l'entrée de l'utilisateur et de trouver la correspondance la plus proche.

Answer 3

Une solution courante consiste à calculer le Levenshtein distance entre l'entrée et vos textes fixes. La distance Levenshtein de deux chaînes est juste le nombre d'opérations simples - insertions, suppressions et substitutions d'un seul caractère - nécessaires pour transformer l'une des chaînes en l'autre.

Answer 4

Même si cela ne résout pas tout le problème, vous pouvez envisager d'utiliser l'algorithme soundex dans le cadre de la solution. Une recherche google rapide de "soundex" et "python" a montré quelques implémentations python de l'algorithme.

Answer 5

Essayez de chercher "Levenshtein distance" ou "modifier distance".Il compte le nombre d'opérations d'édition (supprimer, insérer, modifier une lettre) dont vous avez besoin pour transformer un mot en un autre. C'est un algorithme commun, mais selon le problème, vous pourriez avoir besoin de quelque chose de spécial avec des poids différents pour les différents types de fautes de frappe.

Answer 6

Recherchez l'algorithme Bitap. Il se qualifie bien pour ce que vous voulez faire, et vient même avec un exemple de code source dans Wikipedia.

Answer 7

Si votre jeu de données est vraiment petit, il suffit de comparer indépendamment la distance de Levenshtein sur tous les éléments. Si c'est plus grand, cependant, vous devrez utiliser un BK-Tree ou un système d'indexation similaire. L'article auquel je suis lié décrit comment trouver des correspondances à l'intérieur d'une distance de Levenshtein donnée, mais il est assez simple de s'adapter aux recherches de plus proches voisins (et de les laisser au lecteur comme exercice).