Recherche et parcours du dictionnaire 

ChatGPT Image 25 mai 2026, 14_56_06.png

Le Dawg/GadDag n'est pas seulement utile pour un moteur de jeu de lettres, mais est extrêmement puissant pour effectuer des recherches de tout genre. Venons aux exemples pratiques. Dans la solution on trouve plusieurs modules de recherche. Les plus complets sont Crolow.FastDico.Dawg.DawgSearch et Crolow.FastDico.GadDag.GadDagSearch. 

Introduction

Vous avez directement un aperçu des fonctions de recherches possibles : 

FindAllWordsContainingLetters

Recherche tous les mots qui contiennent les lettres en paramètre

FindAllWordsFromLetters

Recherche tous les mots formés parmi les lettres en paramètre

SearchAllWords

Liste tous les mots du dictionnaire

SearchByPattern

Permet de recherche avec des WildCards. par exemple : TURB*F?RA* devrait permettre de retrouver TURBOFORAGE 

SearchByPrefix

Recherche tous les préfixes d'un mot donné

SearchBySuffix

Recherche tous les suffixes d'un mot donné

SearchWord

Checke l'existence d'un miot

SearchDiagram.png

Exemples de parcours du dictionnaire

Voici quelques exemples de parcours du dictionnaire et de recherche de mots. Commençons par le plus simple.

Vérifier l'existence d'un mot dans le dictionnaire

    public bool SearchWord(string word)
    {
        List<byte> byteWord = tilesUtils.ConvertWordToBytes(word.ToUpper());
        return SearchWord(byteWord);
    }

    public bool SearchWord(List<byte> byteWord)
    {
        // On initialise le noeud à la racine du dictionnaire
        var currentNode = Root;
        // Pöur chaque Lettre du mot à rechercher 
        foreach (var byteVal in byteWord)
        {
            // On vérifie que la lettre se trouve dans les enfants du noeud courant
            var target = currentNode.Children
                .FirstOrDefault(p => p.Letter == byteVal);

            if (target == null)
            {
                return false;
            }
            // On passe à la prochaine lettre, et on place le noeud 
            // à la lettre correspondante
            currentNode = target;
        }
        // La séquence de lettres existe dans le dictionnaire
        // Mais est-ce que la dernière lettre indique
        // Que cette séquence forme un mot ?
        return currentNode.IsEnd; // Return true if the node is terminal
    }

Le principe est simple :

  1. Le mot est converti en une suite d’octets (byte)

  2. On parcourt l’arbre lettre par lettre

  3. À chaque étape, on cherche si la lettre existe parmi les enfants du nœud courant

  4. Si une lettre manque → le mot n’existe pas

  5. Si toutes les lettres existent, on vérifie si le dernier nœud marque réellement la fin d’un mot

Ce code révèle plusieurs bonnes idées :

  • représentation compacte des lettres

  • séparation interface/string et logique interne

  • parcours incrémental efficace

  • utilisation d’un marqueur IsEnd

  • structure adaptée aux dictionnaires volumineux

C’est une base très classique et solide pour :

  • un Trie

  • un GADDAG

  • un moteur de Scrabble

  • un correcteur orthographique

  • de l’autocomplétion

Recherche des préfixes d'un mot

Un exemple pour vous montrer la différence d'utilisation entre le Dawg et le GadDag. 

La fonction  SearchBySuffix recherche tous les prolongements d'un mot vers l'avant. exemple : A -> CHAT,  BA -> CHAT, CRA-CHAT

    public List<string> SearchBySuffix(string prefix, int maxLength = int.MaxValue)
    {
        return SearchByPattern("*" + prefix.ToUpper());
    }

    public List<string> SearchByPattern(string pattern, int minLength = int.MinValue, int maxLength = int.MaxValue)
    {
        // On convertit le pattern en bytes
        List<byte> bytePattern = ConvertPatternToBytes(pattern.ToUpper());
        List<string> results = new List<string>();
        SearchByPatternRecursive(Root, bytePattern, 0, new List<byte>(), results, minLength, maxLength);
        return results;
    }

    private void SearchByPatternRecursive(ILetterNode currentNode, List<byte> bytePattern, int patternIndex, 
                                          List<byte> currentWord, List<string> results, int minLength, int maxLength)
    {
        // Base case: Reached the end of the pattern
        if (patternIndex == bytePattern.Count)
        {
            if (currentNode.IsEnd)
            {
                if (currentWord.Count >= minLength && currentWord.Count <= maxLength)
                {
                    // Convert the current word to string and add to results    
                    results.Add(tilesUtils.ConvertBytesToWord(currentWord));
                }
            }
            return;
        }

        if (currentWord.Count > maxLength)
            return;

        byte currentByte = bytePattern[patternIndex];

        if (currentByte == TilesUtils.WildcardByte) // '*' wildcard
        {
            // Match zero or more characters
            // First, try skipping the '*'
            SearchByPatternRecursive(currentNode, bytePattern, patternIndex + 1, 
                                    currentWord, results, minLength, maxLength);

            // Then, try matching one or more characters
            foreach (var child in currentNode.Children)
            {
                currentWord.Add(child.Letter);
                SearchByPatternRecursive(child, bytePattern, patternIndex, currentWord,
                                         results, minLength, maxLength);
                currentWord.RemoveAt(currentWord.Count - 1); // Backtrack
            }
        }
        else if (currentByte == TilesUtils.JokerByte) // '?' wildcard
        {
            // Match exactly one character
            foreach (var child in currentNode.Children)
            {
                currentWord.Add(child.Letter);
                SearchByPatternRecursive(child, bytePattern, patternIndex + 1, 
                                         currentWord, results, minLength, maxLength);
                currentWord.RemoveAt(currentWord.Count - 1); // Backtrack
            }
        }
        else
        {
            // Match the exact character
            var nextNode = currentNode.Children.Where(p => p.Letter == currentByte);
            if (nextNode.Any())
            {
                currentWord.Add(currentByte);
                SearchByPatternRecursive(nextNode.First(), bytePattern, patternIndex + 1, 
                                         currentWord, results, minLength, maxLength);
                currentWord.RemoveAt(currentWord.Count - 1); // Backtrack
            }
        }
    }

    public List<string> SearchBySuffix(string suffix, int maxLength = int.MaxValue)
    {
        var patternedSuffix = suffix.ToUpper() + "#";

        var bytes = tilesUtils.ConvertWordToBytes(patternedSuffix);
        var results = new List<string>();
        var currentNode = Root;

        // Navigate to the prefix node
        foreach (var byteVal in bytes)
        {
            currentNode = currentNode.Children.FirstOrDefault(c => c.Letter == byteVal);
            if (currentNode == null)
                return results; // Prefix not found
        }

        // Collect all words from the prefix node
        SearchSuffixesFromNode(currentNode, bytes, new List<byte>(), results, maxLength);
        return results;
    }

    private void SearchSuffixesFromNode(ILetterNode node, List<byte> currentWord, 
                                        List<byte> result, List<string> results, int length)
    {
        if (node.IsEnd && length >= 0)
        {
            var newWord = new List<byte>();
            var word = currentWord.Take(currentWord.Count - 1).ToList();
            newWord.AddRange(result);
            newWord.AddRange(word);
            results.Add(tilesUtils.ConvertBytesToWord(newWord));
        }

        foreach (var child in node.Children)
        {
            result.Insert(0, child.Letter);
            SearchSuffixesFromNode(child, currentWord, result, results, length - 1);
            result.RemoveAt(0);
        }
    }

Dans le cas du DAWG, la structure ne permet qu’une traversée naturelle de gauche à droite. Pour retrouver tous les mots contenant un suffixe donné, il est donc nécessaire de parcourir potentiellement l’ensemble de l’arbre afin d’identifier tous les nœuds terminaux compatibles avec ce suffixe, puis d’en déduire les préfixes correspondants.

La version DAWG passe ainsi par une recherche générique utilisant un wildcard : *AGE ce qui signifie que tous les mots se terminant par AGE.  Comme le DAWG est construit autour des préfixes, il ne peut pas accéder directement aux suffixes. La recherche doit donc explorer récursivement l’arbre complet pour tester toutes les branches possibles avant de valider les correspondances.

Le GADDAG fonctionne différemment. Grâce à sa représentation pivotée autour du séparateur #, il devient possible d’accéder directement à certains nœuds internes depuis la racine du dictionnaire, sans devoir traverser intégralement l’arbre.

Une recherche de suffixe peut ainsi être transformée en accès direct : AGE#

Le moteur peut alors se positionner immédiatement sur les nœuds correspondant au pivot recherché, puis reconstruire les préfixes compatibles en parcourant la partie gauche inversée du graphe.

Cette approche permet de court-circuiter une grande partie des parcours nécessaires dans un DAWG classique, ce qui explique pourquoi le GADDAG est particulièrement adapté à la génération de coups au Scrabble.

On peut également imaginer des optimisations supplémentaires pour les recherches avec wildcards multiples. Par exemple : *BOF*AGE Une implémentation optimisée pourrait ignorer le premier wildcard global, se concentrer directement sur : OF*AGE# puis effectuer un pivot vers la gauche afin d’explorer uniquement les branches compatibles avec les nœuds terminaux correspondant à : OF*AGE#

Le GADDAG permet donc non seulement des recherches bidirectionnelles efficaces, mais ouvre également la voie à des stratégies d’optimisation beaucoup plus ciblées que celles possibles avec un DAWG traditionnel.