Un dictionnaire adapté aux jeux de lettres 

Introduction

Le moteur de Scrabble repose sur une structure de dictionnaire optimisée permettant de vérifier rapidement si une suite de lettres constitue un mot valide.
Une simple liste de mots serait trop lente pour les opérations nécessaires à la génération de coups. Nous avons 2 possibilités pour batir notre moteur de scrabble : le DAWG ou le GADDAG

Le GADDAG est une version étendue du DAWG. Il diffère du DAWG du fait que pour chaque mot on stocke le chemin possible sur chaque lettre de ce mot.

Le DAWG (Directed Acyclic Word Graph)

Le Directed Acyclic Word Graph (DAWG) est une structure de données utilisée pour représenter efficacement un grand ensemble de mots.

Conceptuellement, il s’agit d’un graphe orienté acyclique dans lequel :

• chaque arête correspond à une lettre,

• chaque chemin depuis la racine correspond à un préfixe de mot,

• certains nœuds sont marqués comme terminaux pour indiquer la fin d’un mot valide.

Ainsi, un mot est reconnu lorsqu’un chemin complet dans le graphe mène à un nœud terminal.

Exemple simple

Si le dictionnaire contient les mots : CHAT, CHIEN, CHOU

l’arbre initial (avant compression) ressemble à ceci :

Chaque chemin depuis la racine forme un mot :

• C → H → A → T

• C → H → I → E → N

• C → H → O → U

Cette structure correspond à un trie (arbre de préfixes).

Compression de l’arbre

Un DAWG est obtenu en compressant un trie afin de supprimer les redondances.

L’idée fondamentale est la suivante :

Deux sous-arbres identiques sont fusionnés.

Autrement dit, si plusieurs mots partagent la même fin, cette fin n’est stockée qu’une seule fois.

Exemple

Considérons les mots : CHIEN, CHILIEN, MALIEN

Le trie naïf serait :

On remarque que la séquence finale IEN apparaît trois fois, et la finale LIEN 2 fois.

Dans un DAWG, cette partie est partagée, et pourrait être réprésentée ainsi :

Chemins dans le graphe

C → H → I → E → N          = CHIEN
C → H → I → L → I → E → N  = CHILIEN
M → A → L → I → E → N      = MALIEN

La lettre I et L constitue simplement une branche alternative entre le H et le I de CHIEN.

MA rejoint la branche LIEN de CHILIEN

Le suffixe IEN est ensuite partagé par les trois mots.

Propriétés du DAWG

Cette compression apporte plusieurs avantages :

1. Réduction de la mémoire

Pour un dictionnaire de Scrabble (plusieurs centaines de milliers de mots), le DAWG réduit drastiquement la taille mémoire en partageant les suffixes communs.

2. Recherche rapide

La vérification d’un mot s’effectue en temps proportionnel à sa longueur

Chaque lettre correspond simplement à la traversée d’une arête.

3. Structure acyclique

Contrairement à d’autres graphes, un DAWG ne contient aucun cycle, ce qui garantit :

• une navigation simple,

• une absence de boucles infinies.

Construction du DAWG

La construction se déroule généralement en deux étapes :

1. Création d’un trie à partir de la liste de mots triée alphabétiquement.

2. Minimisation du graphe en fusionnant les sous-arbres équivalents.

Deux nœuds sont équivalents lorsqu’ils possèdent :

• le même statut terminal,

• les mêmes transitions vers les mêmes sous-graphes.

Ce processus produit un automate déterministe minimal représentant exactement l’ensemble des mots du dictionnaire.

💡 Dans la documentation d’un moteur de Scrabble, cette structure est particulièrement utile car elle permet :

• de tester rapidement la validité d’un mot,

• de parcourir efficacement les préfixes possibles lors de la génération des coups.

Du DAWG au GADDAG

Principe de base

Le GADDAG est construit à partir d’un DAWG, mais chaque mot est représenté dans toutes ses “préfixes inversés possibles” afin de permettre :

• la recherche rapide de mots commençant avant une ancre sur la grille,

• la génération efficace de tous les coups possibles à partir d’une ancre.

Concrètement :

• Pour un mot MOT, on ne stocke pas seulement M → O → T comme dans le DAWG.

• On stocke plusieurs versions “pivotées” du mot où chaque lettre peut devenir le point central de l’ancre.

Changement principal par rapport au DAWG

1. Insertion d’un séparateur spécial

   • Dans le GADDAG, on utilise un caractère séparateur (souvent #) pour indiquer le point pivot.

• La partie avant le # correspond au suffixe normal, qui se construit vers la droite.

• La partie après le # est inversée et permet de “construire le mot vers la gauche” sur la grille.

2. Inversion des préfixes

   • Seules les lettres après le pivot sont stockées à l’envers.

   • Cela permet de remonter rapidement vers le début du mot depuis n’importe quelle ancre.

3. Multiplication des chemins

   • Chaque mot produit plusieurs chemins dans le GADDAG, un pour chaque pivot possible.

   • Le suffixe commun (comme ANT) reste partagé, comme dans le DAWG.

Exemple avec CHINANT

Exemple avec CHINANT (lettres : C H I N A N T) :

• # indique le pivot (la lettre posée sur l’ancre).

• Les lettres avant le pivot sont inversées pour permettre la construction vers la gauche sur la grille.

• Les lettres après le pivot sont normales, pour construire vers la droite.

• Les suffixes communs (ex. ANT) restent mutualisés, comme dans le DAWG.

Résumé des modifications par rapport au DAWG

Conclusion

Le GADDAG est essentiellement un DAWG enrichi pour le Scrabble, capable de rechercher rapidement tous les mots valides autour d’une lettre déjà posée, grâce à l’inversion des préfixes et au séparateur pivot.

Avec un DAWG classique, un moteur doit effectuer une recherche sur chaque case de la grille pour identifier les mots qui peuvent se connecter à une ancre.
En revanche, avec un GADDAG, la recherche peut se limiter uniquement aux pivots possibles sur les lettres déjà présentes, ce qui réduit considérablement le nombre d’itérations nécessaires pour générer toutes les solutions valides.

Cette optimisation est ce qui rend le GADDAG particulièrement adapté aux moteurs de Scrabble performants

La prochaine page vous expliquera l'implémentation du Dawg/GadDag dans Fastidico