Ce que l'algorithme donne des suggestions dans un correcteur orthographique?

Une approche pour générer des suggestions que j'ai utilisé avec succès mais jamais vu de figure nulle part est à pré-calculer les suggestions (lors de la construction du dictionnaire) à l'aide de "mauvais" fonctions de hachage.

L'idée est de regarder les types de fautes d'orthographe font les gens, et à la conception de fonctions de hachage qui permettrait d'attribuer une orthographe incorrecte le même compartiment que son orthographe correcte.

Par exemple, une erreur commune est d'utiliser le mauvais voyelle, comme toujours influencé au lieu de définitive. Afin de vous concevoir une fonction de hachage qui traite de toutes les voyelles que la même lettre. Un moyen facile de le faire est d'abord de "normaliser" le mot d'entrée et ensuite mettre le résultat normalisé par l'intermédiaire d'un régulier de la fonction de hachage. Dans cet exemple, la fonction de normalisation peut tomber toutes les voyelles, donc definite devient dfnt. Le "normalisé" la parole est ensuite hachée typique d'une fonction de hachage.

Insérer tous vos mots de dictionnaire un auxiliaire de l'index (table de hachage) à l'aide de cette spéciale de fonction de hachage. Les seaux dans ce tableau ont allongé la collision des listes en raison de la fonction de hachage est "mauvais", mais ceux de collision listes sont essentiellement pré-calculé suggestions.

Maintenant, lorsque vous trouvez un mot mal orthographié, vous regardez en haut de la collision des listes pour le seau que la faute d'orthographe cartes à l'auxiliaire d'index. Ta da: Vous avez une liste de suggestion! Tout ce que vous avez à faire est de classer les mots.

Dans la pratique, vous aurez besoin d'un peu d'auxiliaire d'index avec d'autres fonctions de hachage pour gérer d'autres types d'erreurs, comme la transposée de lettres, simple/double lettre, et même simpliste Soundex-comme un catch phonétique des fautes d'orthographe. Dans la pratique, j'ai trouvé simpliste de la prononciation à aller un long chemin et est essentiellement désuet certains de ceux conçus pour trouver trivial fautes de frappe.

Alors maintenant vous cherchez des fautes d'orthographe dans chacune des auxiliaires d'index et de concaténer la collision des listes avant le classement.

Souviens de la collision listes contiennent uniquement les mots sont dans le dictionnaire. Avec des approches qui tentent de générer des orthographes alternatives (comme dans le Peter Norvig l'article), vous pouvez obtenir des (dizaines de) milliers de candidats que vous devez d'abord filtre contre le dictionnaire. Avec le pré-calculé approche, vous obtenez peut-être que quelques centaines de candidats, et vous savez qu'ils sont tous correctement orthographié, de sorte que vous pouvez utiliser directement le classement.

Mise à jour: depuis, j'ai trouvé une description d'algorithme qui est semblable à cela, le FAROO de Recherche Distribuée. C'est encore un edit-distance limitée de la recherche, mais il est très rapide car le pré-étape de calcul fonctionne comme mon "mauvais fonctions de hachage" idée. FAROO utilise juste un concept limité d'une mauvaise fonction de hachage.

Vous n'avez pas besoin de connaître l'exacte distance d'édition pour chaque mot dans le dictionnaire. Vous pouvez arrêter l'algorithme après avoir atteint une valeur limite et d'exclure le mot. Cela vous permettra d'économiser beaucoup de temps de calcul.