Algorithme de comparaison des mots (non par ordre alphabétique)

Question

Je dois coder une solution pour une certaine exigence, et je voulais savoir si quelqu'un est soit familier avec une bibliothèque impromptu qui peut le réaliser, ou peut me diriger à la meilleure pratique. Description:

L'utilisateur saisit un mot qui est censé être l'une des options fixes (je détiens les options dans une liste). Je sais que l'entrée doit être un membre dans la liste, mais puisqu'il est entrée utilisateur, il / elle peut avoir fait une erreur. Je suis à la recherche d'un algorithme qui va me dire quel est le mot le plus probable que l'utilisateur voulait dire. Je n'ai pas tout contexte et je ne peux pas forcer l'utilisateur à choisir parmi une liste (à savoir qu'il doit être en mesure d'entrer le mot librement et manuellement).

Par exemple, supposons que la liste contient les mots « eau », « quartier », « bière », « la betterave », « l'enfer », « bonjour » et « Aardvark ».

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

• les fautes de frappe de vitesse (par exemple des caractères de doublement, passant caractères, etc.)
• Clavier fautes de frappe adjacente caractères (par exemple "Qater" pour « eau »)
• fautes de frappe qu'anglophone non natif (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 autre lettre, lettre supplémentaire et lettre manquante. Mais cette solution ne tient pas compte des milliers d'erreurs « standard » Je suis sûr sont répertoriés quelque part. Je suis sûr qu'il ya heuristiques là-bas qui traitent tous les cas, à la fois base de données spécifiques et générales, en utilisant probablement un grand nombre de discordances standards (je suis ouvert à des solutions de données lourdes).

Je codage en Python mais je considère que cette langue agnostique question.

Toutes les 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 est cependant pas une solution complète au problème, car on aurait aussi besoin d'une structure de données pour effectuer efficacement une recherche le plus proche voisin non-euclidienne. Cela peut être fait par exemple avec l'arbre de couverture: http://hunch.net/~jl/projects/cover_tree /cover_tree.html

Answer 2

Une solution commune est de calculer le Levenshtein entre l'entrée et vos textes fixes. La distance Levenshtein de deux chaînes est que le nombre d'opérations simples - insertions, suppressions et substitutions d'un seul caractère -. Nécessaire pour transformer une de la chaîne dans l'autre

Answer 3

Avez-vous envisagé des algorithmes qui 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 obtenir un soundex de l'entrée d'utilisateur et trouver la meilleure correspondance il.

Answer 4

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

Answer 5

Si votre ensemble de données est vraiment petit, la simple comparaison de la distance Levenshtein sur tous les articles devraient suffire indépendamment. Si elle est plus grande, cependant, vous aurez besoin d'utiliser un BK-Tree ou d'un système d'indexation similaire. L'article I lié à décrit comment trouver les matchs à une distance Levenshtein donnée, mais il est assez facile d'adapter à faire des recherches plus proche voisin (et à gauche comme un exercice au lecteur;).

Answer 6

Bien qu'il ne peut pas résoudre l'ensemble du problème, vous pouvez envisager d'utiliser l'algorithme soundex dans le cadre de la solution. Une recherche rapide Google de « soundex » et « python » a montré quelques implémentations de python de l'algorithme.

Answer 7

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