le blog du Dr. Goulu

DicoLib

DicoLib est une librairie C++/STL pour les jeux de mots, que j’ai développé initialement pour résoudre le casse-tête “word-downsizing

Complexité

L’algorithme “force brute” pour résoudre “word-downsizing” consiste à chercher les n mots de 8 lettres du dictionnaire (O(N)), puis pour chacun d’eux, enlever successivement chaque lettre et vérifier s’il est présent dans le dictionnaire (O(N.log N) pour liste triée), et recommencer s’il y est. La complexité est environ O(N+n.100.N.log N). Le facteur 100 est une estimation du nombre de recherches dans le dictionnaire pour chaque mot avant d’arriver à une impasse. Avec typiquement N=30’000 et n=5’000, on se retrouve avec ‘240 milliards de comparaisons‘ de chaînes de caractères à effectuer si l’on veut trouver toutes les solutions. Compter une petite heure…

On pourrait se satisfaire de ceci et se demander pourquoi passer des heures à programmer une solution plus futée. Et bien, si on est capable de retrouver rapidement les mots qui ne se distinguent d’un autre que par une seule lettre, ou deux ou trois, on obtient un correcteur d’orthographe rapide et efficace. Mais pour une telle application, la complexité mentionnée ci-dessus serait inacceptable.

Conception

Comment accélérer très sérieusement la recherche de mots “semblables” a un autre dans un dictionnaire ?

Quelques idées :

  • grouper les mots par tailles. Si on cherche un mot de 6 lettres, on ne le cherchera que parmi ceux-là.
  • construire une “signature” du mot sous la forme d’un ensemble de 26 bits indiquant quelles lettres sont présentes dans le mot, et grouper les mots ayant la même signature (donc composés des mêmes lettres) dans une liste. 26 bits, c’est moins que 32, donc très pratique à manipuler par le processeur pour des opérations logiques. Mais c’est trop pour être utilisé comme clé dans une table de hachage, qui aurait dans les 64 millions d’entrées.

Je me suis dont mis à réfléchir à une structure de donnée permettant de stocker un dictionnaire de mots sous une forme permettant la recherche rapide de mots similaires (avec une lettre en plus ou en moins), des anagrammes (mots obtenus par permutation des lettres) ou selon les lettres qui les composent (pour le scrabble).

J’ai alors eu une idée simple, dont je ne sais pas encore si elle est originale, mais en tout cas elle est très efficace, et j’ai écrit un ensemble de classes C++ “Dico.lib”,une librairie permettant de réaliser en quelques lignes des programmes de résolution de divers jeux de lettres.

L’idée principale de DicoLib est de stocker les mots dans une structure permettant d’y accéder rapidement sur la base de 2 informations simples :

  • la longueur du mot
  • une clé de 26 bits (letterset) codant la présence de chaque lettre de l’alphabet dans le mot. par exemple le mot “alphabet” donne
11001001000100000001000000
abcdefghijklmnopqrstuvwxyz

Structure de données

Structure de données

dico.lib définit la hiérarchie de classes suivantes :

  • class Word // mots du dictionnaire
  • class letterset : public std ::bitset<26> // clé d’accès
  • class WordList : public std ::list // liste de mots
  • class Anagrams : public WordList // liste d’anagrammes
  • class AnagramsList : public list // liste de listes d’anagrammes
  • class SameLetters : public vector // mots formés des même lettres, organiséss par longueurr
  • class Dico : public std ::map // dictionnaire utilisant les letterset comme clé primaire

Liens

Laissez un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Pas de commentaire “DicoLib”