Re: [Eliot-general] GADDAG Impl

[Olivier Teuliere]

Bonjour,

Je mets la liste eliot-dev en copie.

2012/10/31 Reda Lyazidi <address@hidden>:
> J'ai déjà fait un scrabble avec IA en projet en Java, c'était moi qui était
> chargé de faire l'implémentation
> d'un GADDAG, le faire en c++ ne me dérangerait pas, j'aurai besoin de
> quelques infos,

Le support du GADDAG dans Eliot serait vraiment très utile !

> avec quoi vous versionné (svn, git, mercurial ...)

On utilise git, c.f. http://savannah.nongnu.org/git/?group=eliot

> et votre algo pour
> factoriser les suffixes pour les DAWG
> il marche ? comme ça je le reprends tel quel.

Je ne pense pas que l'algo du DAWG puisse être utilisé tel quel pour
le GADDAG, mais ça pourrait être une bonne base de départ.

Quelques indications :
 - la compression d'un DAWG (à partir d'une liste de mots et d'un
fichier de lettres) se fait dans la méthode CompDic::generateDawg()
(dic/compdic.cpp).
 - la méthode récursive CompDic::makeNode() fait l'essentiel de la
compression. Attention, elle suppose que la liste de mots est triée
(plus exactement, elle suppose que tous les mots ayant un même préfixe
se trouvent à la suite, et ce pour tout préfixe)
 - la compression des suffixes se fait à l'aide d'une hashmap
(m_hashMap), qui associe à un ensemble de suffixes le nœud du graphe
correspondant
 - le header du dictionnaire a déjà un champ pour différencier le dawg
du gaddag (c.f. compdic.cpp:341)
 - le fichier dic/compdicmain.cpp est un petit programme montrant
comment utiliser CompDic

Il y aura aussi des changements à faire pour supporter le GADDAD :
 - la recherche dans le dictionnaire (cf. dic/dic_search.cpp, et
peut-être aussi les méthodes lookup() et char_lookup() dans dic.cpp)
 - la recherche dans le contexte d'une partie de Scrabble (cf.
game/board_search.cpp)
Pour différencier un DAWG d'un GADDAG dans le code, il suffit de faire :
if (myDic.getHeader().getType() == Header::kGADDAG) ...

N'hésitez pas à me solliciter pour des questions ou de l'aide !

Cordialement,
--
Olivier