Il y a un bon essai de Peter Norvig sur la façon d'implémenter un correcteur orthographique. Il s'agit essentiellement d'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 orthographique à l'aide d'un filtre Bloom et d' un hachage plus rapide des candidats .)
Les exigences pour un correcteur orthographique sont plus faibles. Vous n'avez qu'à découvrir qu'un mot n'est pas dans le dictionnaire. Vous pouvez utiliser un filtre Bloom pour créer 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-Tree 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 suppression et 1 insertion). La distance Damerau – Levenshtein est la bonne distance d'édition.
Une approche pour générer des suggestions que j'ai utilisées avec succès mais que je n'ai jamais vues décrites nulle part consiste à pré-calculer les suggestions (lors de la construction du dictionnaire) en utilisant des fonctions de hachage "mauvaises".
L'idée est d'examiner les types d'erreurs 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 consiste à utiliser la mauvaise voyelle, comme definate au lieu de définitif . Vous concevez donc une fonction de hachage qui traite toutes les voyelles comme la même lettre. Une manière simple de le faire est de «normaliser» d'abord le mot d'entrée, puis de placer le résultat normalisé via une fonction de hachage régulière. Dans cet exemple, la fonction de normalisation peut supprimer toutes les voyelles, ainsi le
definitedevientdfnt. 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) à l'aide de cette fonction de hachage spéciale. Les compartiments de ce tableau auront des listes de collisions plus longues car la fonction de hachage est «mauvaise», mais ces listes de collisions sont essentiellement des suggestions précalculées.
Désormais, lorsque vous trouvez un mot mal orthographié, vous recherchez dans les listes de collisions 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 dessus.
En pratique, vous aurez besoin de quelques index auxiliaires avec d'autres fonctions de hachage pour gérer d'autres types d'erreurs, comme des lettres transposées, une lettre simple / double et même une simple de type Soundex pour détecter les fautes d'orthographe phonétiques. Dans la pratique, j'ai trouvé que les prononciation simplistes allaient très loin et certaines d'entre elles étaient essentiellement obsolètes pour trouver des fautes de frappe triviales.
Vous recherchez maintenant les fautes d'orthographe dans chacun des index auxiliaires et concaténez les listes de collisions avant le classement.
Souvenez-vous que les listes de collisions ne contiennent que les mots du dictionnaire. Avec des approches qui tentent de générer des orthographes alternatives (comme dans l'article de Peter Norvig), vous pouvez obtenir (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, vous pouvez donc passer directement au classement.
Mise à jour : j'ai depuis trouvé une description d'algorithme similaire à celle-ci, la recherche distribuée FAROO . Il s'agit toujours d'une recherche limitée à la distance d'édition, mais elle 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é de mauvaise fonction de hachage.
la source
Algorithme
Optimisation
Vous pouvez trouver l'explication plus détaillée et le code source sur le projet github .
la source
Vous n'avez pas besoin de connaître la distance d'édition exacte pour chaque mot du dictionnaire. Vous pouvez arrêter l'algorithme après avoir atteint une valeur limite et exclure le mot. Cela vous fera gagner beaucoup de temps de calcul.
la source
Le correcteur orthographique est très facile à implémenter comme dans le programme orthographique Unix. 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 présentées à l'utilisateur.
Le système Unix utilise un programme écrit par Mc IllRoy. Une autre manière est d'utiliser un Trie qui peut être utile dans le cas de fichiers volumineux.
L'approche unix nécessite très moins d'espace pour un énorme dictionnaire car elle utilise un algorithme de hachage de dispersion.
la source