Quel algorithme donne des suggestions dans un correcteur orthographique?
Quel algorithme est généralement utilisé lors de l'implémentation d'un correcteur orthographique accompagné de suggestions de mots?
Au début, j'ai pensé qu'il pourrait être logique de vérifier chaque nouveau mot tapé (s'il n'est pas trouvé dans le dictionnaire) par rapport à la distance Levenshtein de tous les autres mots du dictionnaire et de renvoyer les meilleurs résultats. Cependant, cela semble être très inefficace, avoir à évaluer l'ensemble du dictionnaire à plusieurs reprises.
Comment est-ce typiquement fait?
5 réponses
Il est bon essai de Peter Norvig comment mettre en œuvre un correcteur orthographique. C'est fondamentalement une approche de force brute essayant des chaînes candidates avec une distance d'édition donnée. ( Voici quelques conseils pour améliorer les performances du correcteur d'orthographe en utilisant un filtre Bloom et un hachage candidat plus rapide.)
Les exigences pour un correcteur orthographique sont plus faibles. Vous avez seulement pour découvrir qu'un mot n'est pas dans le dictionnaire. Vous pouvez utiliser un filtre Bloom pour construire un correcteur orthographique qui consomme moins de mémoire. Une version ancienne est décrite dans Programming Pearls par Jon Bentley en utilisant 64kb pour un dictionnaire anglais.
UN BK-Arbre est une approche alternative. Un bel article est ici.
La distance de Levenshstein n'est pas exactement la bonne distance d'édition pour un correcteur orthographique. Il ne connaît que l'insertion, la suppression et la substitution. La Transposition est manquante et produit 2 pour une transposition de 1 caractère (c'est 1 supprimer et 1 insertion). Damerau–Levenshtein distance est la bonne distance d'édition.
Une approche pour générer des suggestions que j'ai utilisées avec succès mais jamais vue décrite est de pré-calculer les suggestions (lors de la construction du dictionnaire) en utilisant des fonctions de hachage "mauvaises".
L'idée est de regarder les types de fautes d'orthographe que les gens font, et de concevoir des fonctions de hachage qui attribueraient une orthographe incorrecte au même compartiment que son orthographe correcte.
Par exemple, une erreur courante est d'utiliser la mauvaise voyelle, comme definate au lieu de défini . Donc, vous concevez une fonction de hachage qui traite toutes les voyelles comme la même lettre. Un moyen facile de le faire est d'abord de "normaliser" le mot d'entrée, puis de mettre le résultat normalisé à travers une fonction de hachage régulière. Dans cet exemple, la fonction de normalisation peut tomber toutes les voyelles, donc definite devient dfnt. Le mot "normalisé" est ensuite haché avec une fonction de hachage typique.
Insérez tous les mots de votre dictionnaire dans un index auxiliaire (table de hachage) en utilisant ce hachage spécial fonction. Les compartiments de cette table auront des listes de collisions longues car la fonction de hachage est "mauvaise", mais ces listes de collisions sont essentiellement des suggestions pré-calculées.
Maintenant, lorsque vous trouvez un mot mal orthographié, vous recherchez dans les listes de collision le compartiment auquel la faute d'orthographe correspond dans les index auxiliaires. Ta da: Vous avez une liste de suggestions! Tout ce que vous avez à faire est de classer les mots.
En pratique, vous aurez besoin de quelques index auxiliaires avec d'autres fonctions de hachage pour gérer d'autres types d'erreurs, comme les lettres transposées, lettre simple/double, et même un Soundex simpliste comme un pour attraper les fautes d'orthographe phonétique. En pratique, j'ai trouvé les prononciations simplistes pour aller un long chemin et essentiellement obsolètes certains de ceux conçus pour trouver des fautes de frappe triviales.
Alors maintenant, vous recherchez des fautes d'orthographe dans chacun des index auxiliaires et concaténez les listes de collision avant le classement.
Rappelez-vous que les listes de collision ne contiennent que des mots dictionnaire. Avec des approches qui tentent de générer des orthographes alternatives (comme dans L'article Peter Norvig), vous pouvez obtenir (des dizaines de) milliers de candidats que vous devez d'abord filtrer par rapport au dictionnaire. Avec l'approche pré-calculée, vous obtenez peut-être quelques centaines de candidats, et vous savez qu'ils sont tous correctement orthographiés, de sorte que vous pouvez passer directement au classement.
Update : j'ai depuis trouvé une description d'algorithme similaire à celle-ci, le FAROO distribué Rechercher . C'est toujours une recherche limitée à distance d'édition, mais c'est très rapide car l'étape de pré-calcul fonctionne comme mon idée de "mauvaises fonctions de hachage". FAROO utilise simplement un concept limité d'une mauvaise fonction de hachage.
Algorithme
- Prenez un mot mal orthographié en entrée.
- stockez la liste des mots anglais ainsi que leurs fréquences dans un fichier texte.
- Insérez tous les mots anglais disponibles (stockés dans le fichier texte) ainsi que leurs fréquences (mesure de la fréquence à laquelle un mot est utilisé en langue anglaise) dans un arbre de recherche ternaire.
- maintenant, traversez le long de l'Arbre de recherche ternaire -
- pour chaque mot rencontré dans l'arborescence de recherche ternaire, calculez Levensthein Distance du mot mal orthographié.
- Si Levensthein Distance
- si deux mots ont la même distance d'édition, celui avec une fréquence plus élevée est râpe. Imprimez les 10 premiers éléments de la file D'attente prioritaire.
Optimisation
- vous pouvez éléminer les mots dans le sous-arbre du nœud courant si la distance d'édition de la sous-chaîne du mot d'entrée du mot courant est plus grande que la 3.
Vous pouvez trouver le plus explication détaillée et code source sur projet github .
Vous n'avez pas besoin de connaître la distance d'édition exacte pour chaque mot dans le dictionnaire. Vous pouvez arrêter l'algorithme après avoir atteint une valeur limite et exclure le mot. Cela vous permettra d'économiser beaucoup de temps de calcul.
Correcteur orthographique est très facile à mettre en œuvre comme dans le programme Unix spell. Le code source est disponible en public. La correction peut être impliquée, une technique consiste à faire des modifications et à vérifier à nouveau si ce nouveau mot est dans le dictionnaire. Ces nouvelles modifications peuvent être regroupées et affichées à l'utilisateur.
Le système Unix utilise un programme écrit par Mc IllRoy. Une autre façon est d'utiliser un Trie qui peut être utile dans le cas de fichiers énormes.
L'approche unix nécessite beaucoup moins d'espace pour un énorme dictionnaire car elle utilise un algorithme de hachage scatter.