Une approche pour générer des suggestions que j'ai utilisée avec succès mais que je n'ai jamais vue décrite nulle part consiste à pré-calculer les suggestions (lors de la construction du dictionnaire) en utilisant de "mauvaises" fonctions de hachage.
L'idée est d'examiner les types de fautes d'orthographe que font les gens et de concevoir des fonctions de hachage qui attribueraient une orthographe incorrecte au même godet que son orthographe correcte.
Par exemple, une erreur courante est d'utiliser la mauvaise voyelle, comme définitif au lieu de définitif . Il faut donc concevoir une fonction de hachage qui traite toutes les voyelles comme la même lettre. Un moyen simple d'y parvenir consiste à "normaliser" le mot d'entrée, puis à soumettre le résultat normalisé à une fonction de hachage ordinaire. Dans cet exemple, la fonction de normalisation peut supprimer toutes les voyelles, de sorte que 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 cette fonction de hachage spéciale. Les buckets de cette table auront des listes de collisions assez longues parce que 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 consultez les listes de collisions pour le seau auquel l'orthographe erronée correspond dans les index auxiliaires. Et voilà : Vous avez une liste de suggestions ! Tout ce que vous avez à faire est de classer les mots qui s'y trouvent.
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, les lettres simples/doubles, et même un index simpliste de type Soundex pour attraper les fautes d'orthographe phonétique. En pratique, j'ai trouvé que les index simplistes de prononciation allaient loin et rendaient essentiellement obsolètes certains des index conçus pour trouver des fautes de frappe triviales.
Il faut donc maintenant rechercher les fautes d'orthographe dans chacun des index auxiliaires et concaténer les listes de collision avant de procéder au classement.
N'oubliez pas que les listes de collisions ne contiennent que des mots qui figurent dans le dictionnaire. Avec les approches qui essaient de générer des orthographes alternatives (comme dans l'article de 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, vous pouvez donc passer directement au classement.
