CodeS-SourceS
Rechercher un code, un tuto, une réponse

COMPRESSION D'UN DICTIONNAIRE SOUS FORME DE DAWG

Avril 2017


COMPRESSION D'UN DICTIONNAIRE SOUS FORME DE DAWG



Description de la méthode


Le présent tutoriel présente une méthode de compression de dictionnaire par sa représentation sous forme de DAWG.

D'abord, pourquoi compresser un dictionnaire ?


Trois grands avantages peuvent être cités pour la compression de dictionnaire :
  • Réduire la taille occupée par le dictionnaire sur le support de stockage.
  • Réduire la place occupée par le dictionnaire en mémoire une fois chargée.
  • Mais surtout accélérer la recherche des mots dans le dictionnaire.

Concernant ce dernier point, la recherche dans un dictionnaire compressé est très rapide en comparaison avec une recherche dans un fichier texte brut ou même dans une base de données.

C'est ainsi qu'un dictionnaire compressé est souvent utilisé dans les applications ludiques
(Mots croisés, scrabble, anagrammeurs... sans oublier le boggle) mais également dans les applications plus sérieuses (correcteurs d'orthographe, séquençage d'ADN, etc.).

A titre d'exemple, avec la méthode présentée dans ce tutoriel un dictionnaire comptant environ 386 000 mots peut être compressé dans un fichier 640 Ko et chargé en mémoire en moins d'une seconde.

Ensuite, Le DAWG c'est quoi ?


Selon Wikipedia, Le DAWG (Directed Acyclic Word Graph) est une structure de données sous forme de graphe orienté qui ne possède pas de circuit.

Le DAWG peut également être présenté comme un Arbre dans lequel les suffixes communs sont factorisés.

Et l'Arbre, c'est quoi encore ?


Pour y voir plus clair, prenons un exemple simple qui va nous servir tout au long de ce tutoriel.

Voici le dictionnaire Exemple constitué de 12 mots :

DE
DENT
DONT
PAT
PATE
PATS
POT
POTE
POTS
VA
VENT
VONT
Encadré 1 - Liste des mots du dictionnaire Exemple

Plusieurs manières peuvent être utilisées pour représenter ce dictionnaire sous forme d'Arbre. Celle que je présente ici est basée sur les principes suivants :
  • Un noeud de l'Arbre représente un état qui peut être intermédiaire ou terminal :
    • Un état terminal correspond à la fin d'un mot et sera représenté par un cercle sur fond gris dans le graphe. En d'autres termes, en arrivant au niveau d'un noeud terminal après avoir parcouru l'Arbre depuis la racine nous pouvons conclure que le chemin parcouru constitue un mot valable.
    • Un état intermédiaire correspond soit au début soit au milieu d'un mot, dans ce cas le chemin parcouru ne constitue pas encore un mot valide. Un tel état sera représenté par un cercle sur fond blanc dans le graphe.
  • Un arc de l'Arbre représente une lettre qui permet de passer d'un état à un autre.


La figure 1 donne ainsi la représentation sous forme d'Arbre du dictionnaire Exemple.

La représentation se fait grâce à 25 noeuds, dont 12 terminaux, et 24 arcs. Nous pouvons noter qu'il y a déjà une première optimisation dans cette représentation car les préfixes communs sont factorisés.
A titre d'exemple, les mots POTE et POTS partagent le préfixe commun POT.

Mais comment passer de l'Arbre vers le DAWG ?


Pour passer d'un Arbre à un DAWG, Nous recherchons si un noeud a un équivalent dans l'arbre. Le cas échéant, nous le remplaçons par son équivalent. Cette recherche se fait par branche en commençant par les noeuds terminaux sans enfant et en remontant vers la racine de l'Arbre.

Dans notre exemple, nous pouvons noter que les noeuds 5 et 8 sont équivalents : les deux noeuds sont terminaux et sans enfant. Nous pouvons alors supprimer le noeud 8 et rediriger l'arc sortant du noeud 7 vers le noeud 5 (figure 2).

De la même manière, nous pouvons noter que les noeuds 4 et 7 sont équivalents : Les deux noeuds sont intermédiaires, un seul arc sort de ces deux noeuds (libellé par la lettre T) et pointe vers un même enfant (Noeud 5). Nous pouvons alors supprimer le noeud 7 et rediriger l'arc sortant du noeud 6 vers le noeud 4 (figure 3).

A contrario, nous ne pouvons pas remplacer le noeud 6 par le noeud 3 car ils ne sont pas équivalents : Même s'ils n'ont qu'un seul arc sortant chacun (lettre N) et pointant vers le même noeud (noeud 4), le noeud 3 est un noeud terminal alors que le noeud 6 est un noeud intermédiaire. La réduction de cette branche de l'Arbre s'arrête donc là.

Nous pouvons continuer de la même manière avec la branche suivante en commençant par le noeud 12 qui peut être remplacé par le noeud 5.

En réitérant l'opération sur l'ensemble des branches, nous finirons par avoir un graphe et non plus un Arbre et là nous allons tenir notre DAWG (figure 4).

La compression est maintenant terminée et la représentation sous forme de DAWG du dictionnaire ne nécessite plus que 10 noeuds, dont 3 terminaux, et 16 arcs.

Techniquement, deux méthodes permettent d'arriver à cette réduction :
  • La première, développée par Appel et Jacobson, consiste en une construction du DAWG en deux temps : l'Arbre est construit entièrement avant de procéder à sa réduction.
  • La seconde, développée par Jan Daciuk, consiste en une construction directe du DAWG par la réduction de l'Arbre au fur et à mesure de sa construction.

Chaque méthode présente des avantages et des inconvénients qui seront présentés dans la section « Analyse de la performance et conclusion ».

Construction du DAWG en deux temps


Les grandes étapes de cette méthode sont les suivantes :
  • Construire l'arbre en entier en y ajoutant tous les mots du dictionnaire.
  • Classer les noeuds par « profondeur », c'est-à-dire le nombre d'arcs qui séparent un noeud du noeud terminal sans enfant le plus éloigné sur sa branche.
  • Comparer les noeuds de même profondeur et supprimer ceux qui ont des équivalents en redirigeant l'arc pointant précédemment sur le noeud supprimé vers le noeud équivalent.
  • Réindexer les noeuds pour tenir compte des noeuds supprimés.
  • Enregistrer le DAWG ainsi obtenu dans un fichier

Construction directe du DAWG


Les grandes étapes de cette méthode sont les suivantes :
  • Ajouter chaque mot du dictionnaire à l'arbre.
  • Après l'ajout d'un mot (plus exactement l'ajout d'un suffixe), vérifier si les noeuds nouvellement ajoutés ont un noeud équivalent dans l'arbre.
  • Si un noeud a un équivalent alors le supprimer et rediriger l'arc pointant précédemment sur le noeud supprimé vers le noeud équivalent.
  • Enregistrer le DAWG ainsi obtenu dans un fichier


Note importante - Dans cette deuxième méthode, la liste des mots dans le dictionnaire doit être triée par ordre alphabétique croissant. Ainsi nous sommes sûrs que le dernier suffixe ajouté démarre toujours par le dernier arc sortant d'un noeud.

Les deux méthodes nécessitent la construction d'un registre des noeuds « inédits », c'est-à-dire des noeuds qui n'ont pas d'équivalent dans l'Arbre.

Et comment représenter un Arbre ou un DAWG en mémoire ?


Plusieurs possibilités existent quant à la structure de données à utiliser pour représenter un Arbre ou un DAWG en mémoire. Celle que je propose dans ce tutoriel est l'utilisation d'un simple tableau d'entiers à deux dimensions dans lequel :
  • Une ligne représente un noeud : le numéro de la ligne constitue la référence ou l'index du noeud.
  • Les colonnes 1 à 26 représentent les arcs libellés A à Z sortant du noeud : Un arc libellé par une lettre sort du noeud est noté par la référence du noeud qu'il atteint. Un 0 signifie l'absence d'un arc.
  • La colonne 27 sert à marquer l'état du noeud : un noeud terminal est noté 1 alors qu'un un noeud intermédiaire est noté 0.


Le Tableau 1 ci-après représente ainsi l'Arbre de la figure 1 avant réduction (25 lignes * 27 colonnes). Les entêtes de ligne et de colonne (sur fond bleu) ont été rajoutés pour faciliter la lecture mais seules les données (sur fond blanc) sont réellement chargées en mémoire. Les zéros ont également été supprimés.

La lecture du tableau se fait de la manière suivante :
Cellule (1,4) = 2 : Un arc libellé par la lettre D (colonne 4) part du noeud 1 (noeud racine) vers le noeud 2.

Le Tableau 2 ci-après donne une représentation du DAWG de la figure 4 (10 lignes * 27 colonnes). Même remarque que précédemment pour les entêtes et les zéros.

Devons-nous reconstruire le DAWG à chaque fois ?


Heureusement que non, d'autant plus que sa construction à partir d'une liste brute de mots nécessite un certain temps.

Ainsi pour ne pas avoir à refaire tout le travail de construction et de simplification à chaque fois, nous pouvons enregistrer le DAWG sous forme de fichier.
Pour ma part, je le garde sous forme de fichier txt en adoptant les principes suivants :
  • Une ligne du tableau sera représentée par une ligne dans le fichier txt
  • Pour chaque ligne du tableau, concaténer les informations sur les arcs et utiliser des séparateurs entre les arcs. Par exemple la cellule (1,4) sera représentée par D2, la cellule (1,22) par V10 et ainsi de suite.
  • Je n'enregistre que les informations utiles (il n'est pas utile par exemple de noter la cellule (1,1) A0 pour signifier qu'il n'y aucun arc libellé par la lettre A sortant du noeud 1).
  • De la même manière il n'est pas utile d'enregistrer les entêtes de ligne et de colonne dans le fichier. En effet, les lignes s'obtiennent de manière implicite lors du chargement et les colonnes seraient redondantes avec la notation des arcs.
  • Le marqueur de noeud terminal est représenté par le caractère dièse # seul.


Je crée également un entête (les deux premières lignes) pour bien identifier le type de fichier et garder les informations utiles sur le dictionnaire (nombre de mots et nombre de noeuds). Ces informations seront par la suite utiles pour le chargement du dictionnaire à partir du fichier « compilé ».

En appliquant ces principes à notre exemple, nous aboutissons aux fichiers suivants :

NBMOTS : 12
NBNOEUDS : 25
D2-P9-V18
E3-O6
N4#
T5
#
N7
T8
#
A10-O14
T11
E12-S13#
#
#
T15
E16-S17#
#
#
A19-E20-O23
#
N21
T22
#
N24
T25
#
Encadré 2 -Représentation de l'Arbre de la figure 1 sous forme d'un fichier texte

L'encadré 2 donne une représentation de l'Arbre de la figure 1 sous forme de fichier texte. La troisième ligne D2-P9-V18 (après les deux lignes d'entête) correspond au premier noeud, la treizième ligne E12-S13# représente le onzième noeud, et ainsi de suite.

NBMOTS : 12
NBNOEUDS : 10
D2-P7-V10
E3-O6
N4#
T5
#
N4
A8-O8
T9
E5-S5#
A5-E6-O6
Encadré 3 -Représentation du DAWG de la figure 4 sous forme d'un fichier texte

L'encadré 3 donne une représentation du DAWG de la figure 4 sous forme de fichier texte. Nous retrouvons bien nos 10 noeuds, dont 3 terminaux, et nos 16 arcs.

Pour le chargement du dictionnaire, nous lisons le fichier texte ligne par ligne et nous remplissons le tableau d'entier selon les informations sur les arcs. C'est juste l'opération réciproque de l'enregistrement.

Nous voilà arrivés au terme de la description de la méthode. Si ça se trouve, vous aurez déjà tout compris et n'aurez même pas besoin de lire la partie sur l'implémentation dans Excel VBA.

Implémentation de la méthode sur Excel VBA


De prime abord, cette implémentation est loin d'être la meilleure en termes de performance. En effet, elle a été développée dans un but pédagogique. Un certain nombre de calculs intermédiaires et d'étapes non nécessaires ont été introduits pour faciliter la lecture et la compréhension du code.

Première méthode : La construction du DAWG en deux temps


Les déclarations globales :

Option Explicit 
Option Base 0

Public Const A = 1
Public Const Z = 26
Public Const Marqueur_De_Noeud_Terminal = 27
Public Const Nombre_Enfants = 28
Public Const Adresse_Dernier_Enfant = 29
Public Const Profondeur = 30
'Afin de clarifier le code nous allons utiliser ces noms de variable au lieu des chiffres 1 à 30 pour les colonnes
'Les colonnes 28 à 30 sont utilisées uniquement dans le cadre de la construction du DAWG mais ne seront pas enregistrées dans le fichier txt

Public Const Noeud_Racine = 1
'Le noeud racine est le noeud 1 par défaut

Public Const Decalage_Asc = 64
'Comme le code Ansi du caractère `A' est 65 alors qu'il est représenté par le colonne 1, il y a donc à chaque fois un décalage de 64 dans nos calculs d'index du tableau

Public Const Paquets_Noeuds = 10
Public Dictionnaire() As Long, Registre() As Long, Table_De_Correspondance() As Long
 'Comme nous ne connaissons pas à l'avance le nombre de noeuds qui seront créés, nous allons déclarer le dictionnaire et le registre en tant que tableaux dynamiques et les redimensionner par à chaque fois que leur capacité risque d'être dépassée.
'Remarque importante : Comme nous ne pouvons redimensionner un tableau dynamique tout en conservant les valeurs  (redim preserve) que sur la dernière dimension, nous allons transposer les lignes et les colonnes dans notre tableau d'entier.  
'Le redimensionnement par paquet de 10 est approprié pour le tutoriel. En revanche,  pour un dictionnaire réel, 5000 ou 10000 serait une valeur plus appropriée.
'La table de correspondance nous sera utile pour la réindexation des noeuds 
Public Dernier_Noeud As Long, Noeud_Actuel As Long, Noeud_Equivalent As Long, Nombre_Noeuds As Long
'Variables globales utilisées pour mémoriser les noeuds particuliers et le nombre de noeuds

Public Profondeur_Actuelle As Byte, Profondeur_Maximale As Byte
'Variables utilisées pour l'analyse de la profondeur des noeuds

Public Debut As Single
'Juste pour les statistiques


La procédure principale de création du DAWG :

Sub Construire_Dictionnaire()
    'Cette procédure construit un dictionnaire sous forme de DAWG en deux temps : D'abord l'arbre est construit en entier, ensuite il est réduit par factorisation des suffixes communs.
    
    Dim FF As Byte, Taille_Du_Suffixe As Byte
    Dim Nombre_Mots As Long
    Dim Mot As String, Prefixe As String, Suffixe As String
    Debut = Timer
    
    'Initialisation des variables globales
    Dernier_Noeud = Noeud_Racine
    Noeud_Actuel = Noeud_Racine
    ReDim Dictionnaire(A To Profondeur, Paquets_Noeuds)
        
    'Ouverture du fichier source et lecture des mots ligne par ligne
    FF = FreeFile
    Open "D:\Tuto\exemple.txt" For Input As #FF
    
    While Not EOF(FF)
        Line Input #FF, Mot
        Nombre_Mots = Nombre_Mots + 1
            
        'Recherche si le mot contient un préfixe existant dans le dictionnaire
        Prefixe = Extraire_Prefixe_Commun(Mot)
        Taille_Du_Suffixe = Len(Mot) - Len(Prefixe)
        Suffixe = Right (Mot, Taille_Du_Suffixe)
                
        'Ajouter le suffixe dans le dictionnaire
        Ajouter_Suffixe Noeud_Actuel, Suffixe

        'Mise à jour éventuelle de la profondeur maximale
        If Len(Mot) - 1 > Profondeur_Maximale Then Profondeur_Maximale = Len(Mot) - 1

    Wend
   
    'Fermeture du fichier source
    Close #FF

    'Redimensionnement du registre des noeuds inédits et réduction de l'Arbre vers le DAWG
    ReDim Registre(0 To Profondeur_Maximale, Paquets_Noeuds)
    
    Analyser_Et_Reduire Noeud_Racine
    
    Reindexer_Les_Noeuds

    'Enregistrement du dictionnaire sous format texte avec les informations utiles
    Enregistrer_Dictionnaire Nombre_Mots, Dernier_Noeud

End Sub


La fonction pour la recherche du préfixe commun :

Private Function Extraire_Prefixe_Commun(ByVal Mot As String) As String
    'Cette fonction renvoie le préfixe du mot qui existe déjà dans le dictionnaire
    
    Dim Taille_Prefixe As Integer
    Dim Lettre As String
    
    Noeud_Actuel = Noeud_Racine
    Taille_Prefixe = 0
    Lettre = Mid(Mot, Taille_Prefixe + 1, 1)
    
    'Tant qu'un arc sortant du noeud représentant la lettre analysée existe, nous suivons le chemin de manière itérative
    While Arc_Sortant_Existe(Noeud_Actuel, Lettre)
        Taille_Prefixe = Taille_Prefixe + 1
        Lettre = Mid(Mot, Taille_Prefixe + 1, 1)
    Wend
    
    Extraire_Prefixe_Commun = Left(Mot, Taille_Prefixe)
    
End Function


La fonction qui vérifie si une lettre peut continuer un préfixe présent dans le dictionnaire :

Public Function Arc_Sortant_Existe(ByVal Noeud As Long, ByVal Lettre As String) As Boolean
    'Cette fonction vérifie si un arc représentant une lettre sort d'un noeud
    '(Autrement dit, si une lettre permet de continuer un préfixe à partir du noeud considéré)
    'Si l'arc existe, la fonction retourne vrai comme valeur et la variable Noeud_Actuel enregistre la référence du noeud pointé par l'arc
    
    Dim Colonne As Byte
    Colonne = Asc(Lettre) - Decalage_Asc
    
    If Dictionnaire(Colonne, Noeud) = 0 Then
        Arc_Sortant_Existe = False
    Else
        Arc_Sortant_Existe = True
        Noeud_Actuel = Dictionnaire(Colonne, Noeud)
    End If
End Function


La procédure qui ajoute un suffixe à un noeud :

Private Sub Ajouter_Suffixe(ByVal Noeud As Long, ByVal Suffixe As String)
    'Cette procédure ajoute un suffixe à un noeud donné
    
    Dim Position As Byte, Colonne As Byte
    Dim Lettre As String
    Dim Taille_Dictionnaire As Long
        
    'Création d'un nouveau noeud pour chaque lettre du suffixe    
    'Redimensionnement du dictionnaire et du registre si les limites actuelles sont atteintes
    Taille_Dictionnaire = UBound(Dictionnaire, 2)
    If Taille_Dictionnaire < Dernier_Noeud + Len(Suffixe) Then Redimensionner_Dictionnaire

    For Position = 1 To Len(Suffixe)
        Lettre = Mid(Suffixe, Position, 1)
        Colonne = Asc(Lettre) - Decalage_Asc
        Dernier_Noeud = Dernier_Noeud + 1
        Dictionnaire(Adresse_Dernier_Enfant, Noeud) = Colonne
        Dictionnaire(Nombre_Enfants, Noeud) = Dictionnaire(Nombre_Enfants, Noeud) + 1
        Dictionnaire(Colonne, Noeud) = Dernier_Noeud
        Noeud = Dernier_Noeud
    Next Position
    
    'Comme un suffixe termine un mot, marquer le dernier noeud créé comme noeud terminal
    Dictionnaire(Marqueur_De_Noeud_Terminal, Dernier_Noeud) = 1
End Sub


La procédure pour le redimensionnement du dictionnaire :

Private Sub Redimensionner_Dictionnaire()
 'Comme le nombre de noeuds n'est pas connu à l'avance il faut redimensionner périodiquement le dictionnaire
  'Un redimensionnement unitaire rendrait l'algorithme trop lent d'où ce redimensionnement par paquets
    
    Dim Taille_Actuelle As Long
    
    Taille_Actuelle = UBound(Dictionnaire, 2)
    ReDim Preserve Dictionnaire(A To Profondeur, Taille_Actuelle + Paquets_Noeuds)
End Sub


La procédure d'analyse et de réduction de l'Arbre :

Private Sub Analyser_Et_Reduire(ByVal Noeud As Long)
    'Cette procédure parcourt l'arbre de manière récursive, détermine la profondeur d'un noeud,
    'recherche un noeud équivalent dans le registre et remplace le cas échéant le noeud par son équivalent
    Dim Arc As Byte, Dernier_Enfant As Long, Profondeur_Noeud As Byte
    Profondeur_Actuelle = 0
    
    If Dictionnaire(Nombre_Enfants, Noeud) > 0 Then
        Dernier_Enfant = Dictionnaire(Adresse_Dernier_Enfant, Noeud)
        For Arc = A To Dernier_Enfant
            'Pour chaque arc sortant du noeud
            If Dictionnaire(Arc, Noeud) <> 0 Then
                'Rechercher de manière récursive le noeud terminal sans enfant sur une branche
                Analyser_Et_Reduire Dictionnaire(Arc, Noeud)
                'La profondeur est incrémentée au retour de l'appel récursif
                Profondeur_Actuelle = Profondeur_Actuelle + 1
            End If
            'La profondeur est évaluée par rapport au noeud terminal sans enfant le plus éloigné
            If Profondeur_Actuelle > Profondeur_Noeud Then Profondeur_Noeud = Profondeur_Actuelle
        Next Arc
        'La profondeur du noeud est notée et la recherche d'un noeud équivalent lancé
        Dictionnaire(Profondeur, Noeud) = Profondeur_Noeud
        Remplacer_Ou_Enregistrer Noeud
    Else
        'Si on arrive ici c'est qu'on a atteint un noeud terminal sans enfant dont la profondeur est par définition 0
        Profondeur_Actuelle = 0
        Dictionnaire(Profondeur, Noeud) = 0
    End If
End Sub


La procédure d'enregistrement ou de remplacement d'un noeud dans le registre :

Private Sub Remplacer_Ou_Enregistrer(ByVal Noeud As Long)
    'Cette procédure enregistre un noeud s'il est "inédit" ou le remplace par un noeud équivalent le cas échéant
    
    Dim Arc As Byte, Profondeur_Enfant As Byte
    Dim Enfant As Long, Dernier_Enfant As Long
        
    Dernier_Enfant = Dictionnaire(Adresse_Dernier_Enfant, Noeud)
    For Arc = A To Dernier_Enfant
        Enfant = Dictionnaire(Arc, Noeud)
        If Enfant > 0 Then
            'Vérifier s'il y a déjà un noeud équivalent dans le registre
            'Si c'est le cas, remplacer l'enfant par le noeud équivalent puis l'effacer
            'Sinon l'enregistrer car c'est un noeud "inédit"
            Profondeur_Enfant = Dictionnaire(Profondeur, Enfant)
            If Un_Noeud_Equivalent_Existe_Pour(Enfant, Profondeur_Enfant) Then
                Dictionnaire(Arc, Noeud) = Noeud_Equivalent
                Effacer Enfant
            Else
                Enregistrer Enfant, Profondeur_Enfant
            End If
        End If
    Next Arc
        
End Sub


La fonction qui vérifie si un noeud a un équivalent dans le registre :

Private Function Un_Noeud_Equivalent_Existe_Pour(ByVal Noeud_Courant As Long, ByVal Profondeur_Noeud As Byte) As Boolean
    'Cette fonction compare un noeud avec tous les noeuds dans le registre de même profondeur
    'et renvoie VRAI si une équivalence est trouvée
    
    Dim Noeud As Long, Noeud_Enregistre As Long, Noeuds_De_Meme_Profondeur As Long
    
    'La première colonne du registre enregistre le nombre de noeuds d'une profondeur donnée
    Noeuds_De_Meme_Profondeur = Registre(Profondeur_Noeud, 0)
    
    If Noeuds_De_Meme_Profondeur = 0 Then 
Un_Noeud_Equivalent_Existe_Pour = False
Exit Function
    Endif

    For Noeud = 1 To Noeuds_De_Meme_Profondeur
        Noeud_Enregistre = Registre(Profondeur_Noeud, Noeud)
        
        If Les_Deux_Noeuds_Sont_Equivalents(Noeud_Courant, Noeud_Enregistre) Then
            Un_Noeud_Equivalent_Existe_Pour = True
            Noeud_Equivalent = Noeud_Enregistre
            Exit Function
        End If
        
    Next Noeud
    
End Function


La fonction qui vérifie si deux noeuds sont équivalents :

Private Function Les_Deux_Noeuds_Sont_Equivalents(ByVal Noeud1 As Long, ByVal Noeud2 As Long) As Boolean
    'Cette fonction compare un noeud donné à un noeud du registre, retourne VRAI s'ils sont équivalents
    'et la variable globale Noeud_Equivalent pointe sur le noeud équivalent dans le registre.
    
    'Deux noeuds sont équivalents si :
    '1. Ils sont de même nature (noeuds terminaux ou noeuds non terminaux)
    '2. Ils ont le même nombre d'enfants
    '3. Ils ont le même dernier enfant
    '4. Les arcs sortants des deux noeuds pointent vers les mêmes noeuds
    'Dès qu'une des conditions n'est pas remplie, on arrête la comparaison
    
    Dim Colonne As Integer
    If Dictionnaire(Marqueur_De_Noeud_Terminal, Noeud1) = Dictionnaire(Marqueur_De_Noeud_Terminal, Noeud2) Then
        If Dictionnaire(Nombre_Enfants, Noeud1) = Dictionnaire(Nombre_Enfants, Noeud2) Then
            If Dictionnaire(Adresse_Dernier_Enfant, Noeud1) = Dictionnaire(Adresse_Dernier_Enfant, Noeud2) Then
                For Colonne = A To Z
                    If Dictionnaire(Colonne, Noeud1) <> Dictionnaire(Colonne, Noeud2) Then Exit Function
                Next Colonne
                Les_Deux_Noeuds_Sont_Equivalents = True
                Noeud_Equivalent = Noeud2
            End If
        End If
    End If
    
End Function


La procédure pour enregistrer un noeud inédit :

Private Sub Enregistrer(ByVal Noeud As Long, ByVal Profondeur_Noeud As Byte)
    'Cette procédure enregistre un noeud "inédit" (sans équivalent) dans le registre
    Dim Dernier_Noeud_Enregistre As Long
    Registre(Profondeur_Noeud, 0) = Registre(Profondeur_Noeud, 0) + 1
    Dernier_Noeud_Enregistre = Registre(Profondeur_Noeud, 0)
    
    If UBound(Registre, 2) < Dernier_Noeud_Enregistre Then Redimensionner_Registre
    Registre(Profondeur_Noeud, Dernier_Noeud_Enregistre) = Noeud
End Sub


La procédure pour effacer un noeud :

Private Sub Effacer(ByVal Noeud As Long)
    'Cette procédure efface un noeud du dictionnaire
    Dim Colonne As Byte
    For Colonne = A To Profondeur
        Dictionnaire(Colonne, Noeud) = 0
    Next Colonne
End Sub


La procédure pour le redimensionnement du registre :

Private Sub Redimensionner_Registre()
    'Cette procédure redimensionne le registre en rajoutant un paquet de nouveaux noeuds
    'Comme le nombre de noeuds n'est pas connu à l'avance il faut redimensionner périodiquement le registre
    'Un redimensionnement unitaire rendrait l'algorithme trop lent d'où ce redimensionnement par paquets
    
    Dim Taille_Actuelle As Long
    
    Taille_Actuelle = UBound(Registre, 2)
    ReDim Preserve Registre(0 To Profondeur_Maximale, Taille_Actuelle + Paquets_Noeuds)

End Sub


La procédure de ré-indexation des noeuds :

Private Sub Reindexer_Les_Noeuds()
    'Cette procédure réindexe les noeuds pour tenir compte des noeuds supprimés au cours de la réduction de l'arbre par la construction d'une table de correspondance
    'En gros, les noeuds supprimés (lignes vides dans le tableau) sont ignorés lors de la réindexation
    Dim Noeud As Long, Index As Long
    ReDim Table_De_Correspondance(1 To UBound(Dictionnaire, 2))
    Index = Noeud_Racine

    For Noeud = Noeud_Racine To Dernier_Noeud
        If Dictionnaire(Nombre_Enfants, Noeud) > 0 Or Dictionnaire(Marqueur_De_Noeud_Terminal, Noeud) = 1 Then
            Table_De_Correspondance(Noeud) = Index
            Index = Index + 1
        End If
    Next Noeud
    Nombre_Noeuds = Index - 1
End Sub


La procédure pour l'enregistrement de l'Arbre sous format txt

Private Sub Enregistrer_Dictionnaire(ByVal Nombre_Mots As Long, ByVal Dernier_Noeud As Long)
    Dim Ligne As String
    Dim FF As Byte, Colonne As Byte
    Dim Noeud As Long
    
    'Enregistrement du dawg sous format texte
    FF = FreeFile
    Open "D:\Tuto\exemple_DAWG.txt" For Output As #FF
    
    'Enregistrement dans l'entête du nombre de mots et du nombre de noeuds
    Print #FF, "NBMOTS : " & Nombre_Mots
    Print #FF, "NBNOEUDS : " & Nombre_Noeuds

    'Enregistrement des informations sur chaque noeud (une noeud = une ligne dans le fichier)
    'Dans un souci d'optimisation, seules les informations utiles sont enregistrées
    'Ainsi, la référence du noeud (numéro de ligne) et les arcs vides ne sont pas enregistrés
    'Certaines informations utilisées lors de la construction ne sont pas non plus enregistrées (nombre d'enfants, dernier enfant,profondeur, etc.)
    'Le carctère # a été choisie pour noter un noeud terminal
    
    For Noeud = Noeud_Racine To Dernier_Noeud
        Ligne = ""
        'Concaténation des informations utiles sur le noeud...
            'Chaque ligne enregistre les informations sur les arcs sortants du noeud
            'un arc est noté par une lettre de A à Z
            'et par la référence du noeud atteint par l'arc
            'les arcs sont séparés par le marqueur "-"

        For Colonne = A To Z
            If Dictionnaire(Colonne, Noeud) > 0 Then
                Ligne = Ligne & IIf(Ligne = "", "", "-") & Chr(Colonne + Decalage_Asc) & Table_De_Correspondance(Dictionnaire(Colonne, Noeud))
            End If
        Next Colonne
        If Dictionnaire(Marqueur_De_Noeud_Terminal, Noeud) = 1 Then
            Ligne = Ligne & "#"
        End If
        '... et enregistrement  sur une ligne dans le fichier
        If Ligne <> "" Then Print #FF, Ligne
    Next Noeud
        
    'Fermeture du fichier et libération de la mémoire
    Close #FF
    Erase Dictionnaire
    Erase Registre
    Erase Table_De_Correspondance
    
    'Affichage des statistiques
    MsgBox "Le dictionnaire de " & Nombre_Mots & " mots, comportant " & Nombre_Noeuds & " noeuds, a été construit sous forme de DAWG en " & Int(100 * (Timer - Debut)) / 100 & " s."

End Sub


Donc voilà à se stade, nous avons créé le DAWG et l'avons enregistré sous forme d'un fichier texte. Voyons maintenant la procédure pour le charger ultérieurement :

Public Sub Charger_Dictionnaire()
    'Cette procédure charge un dictionnaire stocké sous forme de DAWG
    'en remplissant le tableau d'entier long représentant le dictionnaire
    
    On Error GoTo Erreur
    
    Dim FF As Byte, Code_Lettre As Byte, i As Byte
    Dim Nombre_Mots As Long, Nombre_Noeuds As Long, Noeud As Long, Ligne As Long
    Dim Fichier As String, Chaine As String, Arcs() As String, Arc As String
    
    Debut = Timer
        
    FF = FreeFile
    Fichier = "D:\privé\Tuto\exemple_DAWG.txt"
        
    'Ouverture du fichier en mode lecture
    Open Fichier For Input As #FF
    Line Input #FF, Chaine
    
    'Vérification de l'entête du fichier...
    If Left(Chaine, 6) <> "NBMOTS" Then
        MsgBox "Le fichier sélectionné n'est pas un dictionnaire compilé", vbCritical
        Close #FF
        Exit Sub
    End If
    
    '...et récupération du nombre de mots dans le dictionnaire
    Nombre_Mots = Val(Right(Chaine, Len(Chaine) - 9))
    
    'Poursuite de la vérification de l'entête du fichier...
    Line Input #FF, Chaine
    If Left(Chaine, 8) <> "NBNOEUDS" Then
        MsgBox "Le fichier sélectionné n'est pas un dictionnaire compilé", vbCritical
        Close #FF
        Exit Sub
    End If

    '...et récupération du nombre de noeuds dans le dictionnaire
    Nombre_Noeuds = Val(Right(Chaine, Len(Chaine) - 11))
    ReDim Dictionnaire(A To Marqueur_De_Noeud_Terminal, Noeud_Racine To Nombre_Noeuds)
    
    Ligne = 0
    
    'Chacune des lignes suivantes dans le fichier représente un noeud
    While Not EOF(FF)
        Line Input #FF, Chaine
        
        'Remplacement du marqueur de noeud terminal "#" utilisé à la place de "[1" lors de la compilation du dico
        'Ce remplacement avait deux objectifs : diminuer la taille du fichier tout en améliorant la lisibilité du DAWG
        If Chaine = "#" Then
            Chaine = "[1"
        Else
            Chaine = Replace(Chaine, "#", "-[1", 1)
        End If
        
        'Chaque ligne est décomposée pour en extraire les arcs sortants du noeud
        'un arc est noté par une lettre de A à Z
        'et par la référence du noeud atteint par l'arc
        'les arcs sont séparés par le marqueur "-"
        Ligne = Ligne + 1
        Arcs = Split(Chaine, "-")
        
        'Pour chaque arc trouvé, remplir le dictionnaire 
        For i = 0 To UBound(Arcs)
            Arc = Arcs(i)
            Code_Lettre = Asc(Arc) - Decalage_Asc
            Noeud = Val(Right(Arc, Len(Arc) - 1))
            Dictionnaire(Code_Lettre, Ligne) = Noeud
        Next i

    Wend

    'Fermeture du fichier et affichage des statistiques
    Close #FF
    MsgBox "Le dictionnaire de " & Nombre_Mots & " mots a été chargé en " & Int(100 * (Timer - Debut)) / 100 & " s."
    Exit Sub

Erreur: MsgBox "Le chemin indiqué semble incorrect ou vide, veuillez le vérifier", vbCritical
End Sub

Et maintenant comment exploiter le dictionnaire une fois chargé ? La fonction suivante sert par exemple à vérifier si un mot est présent dans le dictionnaire :

Public Function Mot_Admis(Mot As String) As Boolean
    'Cette fonction teste si un mot est présent dans le dictionnaire
    'Elle utilise le mot à tester comme un chemin dans le DAWG à partir du noeud racine
    'Si le chemin est valide et s'il aboutit à un noeud terminal c'est que le mot existe dans le dictionnaire
    Dim Position As Integer
    Dim Lettre As String
    
    Noeud_Actuel = Noeud_Racine
    
    For Position = 1 To Len(Mot)
        Lettre = Mid(Mot, Position , 1)
        If Not Arc_Sortant_Existe(Noeud_Actuel, Lettre) Then
            Mot_Admis = False
            Exit Function
        End If
    Next Position
    
    If Dictionnaire(Marqueur_De_Noeud_Terminal, Noeud_Actuel) = 1 Then
        Mot_Admis = True
    Else
        Mot_Admis = False
    End If
    
End Function


Bon voilà, nous en avons terminé avec la première méthode.

Deuxième méthode : création directe du DAWG


Nous aurions pu uniquement indiquer les changements à apporter au code pour la première méthode, mais pour éviter des allers et retours, nous allons reprendre le code en entier à chaque fois qu'une procédure ou une fonction présente des changements.
Seules les modifications notables sont commentées.

Option Explicit
Option Base 0

Public Const A = 1
Public Const Z = 26
Public Const Marqueur_De_Noeud_Terminal = 27
Public Const Nombre_Enfants = 28
Public Const Adresse_Dernier_Enfant = 29
'Nous n'avons pas besoin de la profondeur dans cette méthode, ni d'une table de correspondance

Public Const Noeud_Racine = 1
Public Const Decalage_Asc = 64
Public Const Paquets_Noeuds = 10

Public Dictionnaire() As Long, Registre() As Long
Public Dernier_Noeud As Long, Noeud_Actuel As Long, Noeud_Equivalent As Long, Dernier_Noeud_Enregistre As Long
Public Debut As Single

Sub Construire_Dictionnaire()
    'Cette procédure construit un dictionnaire sous forme de DAWG
    'Elle est basée sur l'algorithme de Daciuk
    'La minimalisation se fait au fur et à mesure de la construction mais non pas à la fin
    
    Dim FF As Byte, Taille_Du_Suffixe As Byte
    Dim Nombre_Mots As Long
    Dim Mot As String, Prefixe As String, Suffixe As String
    Debut = Timer
    
    Dernier_Noeud = Noeud_Racine
    Noeud_Actuel = Noeud_Racine
    Noeud_Equivalent = 0
    Dernier_Noeud_Enregistre = 0
    ReDim Dictionnaire(A To Adresse_Dernier_Enfant, Paquets_Noeuds)
    'Le registre devient un tableau à une seule dimension en l'absence de la notion de profondeur
    ReDim Registre(Paquets_Noeuds)
        
    FF = FreeFile
    Open "D:\Tuto\exemple.txt" For Input As #FF
    
    While Not EOF(FF)
        Line Input #FF, Mot
        Nombre_Mots = Nombre_Mots + 1
        Prefixe = Extraire_Prefixe_Commun(Mot)
        Taille_Du_Suffixe = Len(Mot) - Len(Prefixe)
        Suffixe = Right(Mot, Taille_Du_Suffixe)
        
        'La minimalisation se fait après chaque ajout de suffixe
        If Dictionnaire(Adresse_Dernier_Enfant, Noeud_Actuel) > 0 Then Remplacer_Ou_Enregistrer Noeud_Actuel
        Ajouter_Suffixe Noeud_Actuel, Suffixe
    Wend
    Close #FF
    
    'Traitement du dernier suffixe ajouté
    Remplacer_Ou_Enregistrer Noeud_Racine
    Enregistrer_Dictionnaire Nombre_Mots, Dernier_Noeud
End Sub

Private Sub Remplacer_Ou_Enregistrer(ByVal Noeud As Long)
    Dim Enfant As Long, Dernier_Enfant As Long
    
    'On recherche le dernier enfant du noeud analysé
    Dernier_Enfant = Dictionnaire(Adresse_Dernier_Enfant, Noeud)
    Enfant = Dictionnaire(Dernier_Enfant, Noeud)
    
    'Si le noeud ainsi trouvé a à son tour des enfants, on recherche le dernier de manière récursive
    If Dictionnaire(Nombre_Enfants, Enfant) > 0 Then Remplacer_Ou_Enregistrer Enfant
        
    If Un_Noeud_Equivalent_Existe_Pour(Enfant) Then
        Dictionnaire(Dernier_Enfant, Noeud) = Noeud_Equivalent
        Effacer Enfant
    Else
        Enregistrer Enfant
    End If
End Sub

Private Function Un_Noeud_Equivalent_Existe_Pour(ByVal Noeud_Courant As Long) As Boolean    
    Dim Noeud As Long, Noeud_Enregistre As Long
    For Noeud = Noeud_Racine To Dernier_Noeud_Enregistre
        Noeud_Enregistre = Registre(Noeud)
        If Les_Deux_Noeuds_Sont_Equivalents(Noeud_Courant, Noeud_Enregistre) Then
            Un_Noeud_Equivalent_Existe_Pour = True
            Noeud_Equivalent = Noeud_Enregistre
            Exit Function
        End If
    Next Noeud
End Function

Private Sub Enregistrer(ByVal Noeud As Long)
    'Cette procédure enregistre un noeud "inédit" (sans équivalent) dans le registre
    Dernier_Noeud_Enregistre = Dernier_Noeud_Enregistre + 1
    Registre(Dernier_Noeud_Enregistre) = Noeud
End Sub

Private Sub Effacer(ByVal Noeud As Long)
    Dim Colonne As Byte
    For Colonne = A To Adresse_Dernier_Enfant
        Dictionnaire(Colonne, Noeud) = 0
    Next Colonne
    Dernier_Noeud = Dernier_Noeud - 1
End Sub

Private Sub Redimensionner_Dictionnaire()   
    Dim Taille_Actuelle As Long
    Taille_Actuelle = UBound(Dictionnaire, 2)
    ReDim Preserve Dictionnaire(A To Adresse_Dernier_Enfant, Taille_Actuelle + Paquets_Noeuds)
    ReDim Preserve Registre(Taille_Actuelle + Paquets_Noeuds)
End Sub

Private Sub Redimensionner_Registre()
    Dim Taille_Actuelle As Long
    Taille_Actuelle = UBound(Registre, 2)
    ReDim Preserve Registre(Taille_Actuelle + Paquets_Noeuds)
End Sub

Private Sub Enregistrer_Dictionnaire(ByVal Nombre_Mots As Long, ByVal Dernier_Noeud As Long)
    Dim Ligne As String
    Dim FF As Byte, Colonne As Byte
    Dim Noeud As Long
    
    FF = FreeFile
    Open "D:\Tuto\exemple_DAWG.txt" For Output As #FF
    
    Print #FF, "NBMOTS : " & Nombre_Mots
    Print #FF, "NBNOEUDS : " & Dernier_Noeud
   
    For Noeud = Noeud_Racine To Dernier_Noeud
        Ligne = ""
        For Colonne = A To Z
            If Dictionnaire(Colonne, Noeud) > 0 Then
                Ligne = Ligne & IIf(Ligne = "", "", "-") & Chr(Colonne + Decalage_Asc) & Dictionnaire(Colonne, Noeud)
            End If
        Next Colonne
        If Dictionnaire(Marqueur_De_Noeud_Terminal, Noeud) = 1 Then
            Ligne = Ligne & "#"
        End If
        Print #FF, Ligne
    Next Noeud
        
    'Fermeture du fichier et libération de la mémoire
    Close #FF
    Erase Dictionnaire
    Erase Registre
    
    'Affichage des statistiques
    MsgBox "Le dictionnaire de " & Nombre_Mots & " mots, comportant " & Dernier_Noeud & " noeuds, a été construit sous forme de DAWG en " & Int(100 * (Timer - Debut)) / 100 & " s."

End Sub


Les autres procédures et fonctions restent inchangées. Les procédures Analyser_Et_Reduire et Reindexer_Les_Noeuds ne sont plus utiles.

Analyse de la performance et conclusion


Le tableau 3 ci-après présente un comparatif entre les deux méthodes de construction du DAWG pour un dictionnaire d'environ 386 000 mots. La taille du dictionnaire brut est de 4 532 Ko et la taille du DAWG généré est de 641 Ko. Le taux de compression obtenu est ainsi est de l'ordre de 85%.
Le temps de chargement du DAWG est d'environ 0,5 s.

La construction en deux temps est rapide car la recherche d'un noeud équivalent est limitée aux noeuds de même profondeur. En revanche, elle est gourmande en ressource. En effet, la construction de l'Arbre en entier nécessite une place importante en mémoire. Un article de Steve Hanov présente une expérience de compression d'un dictionnaire de plus de 7 millions d'entrées. Le programme plantait avant que l'Arbre, constitué de plus 13 millions de noeuds, ne soit construit par manque de ressources (plus de 1 Go d'occupation mémoire).

La construction directe est plus lente (nécessite cinq fois plus de temps en comparaison avec la première méthode) car il n'y a pas de notion de profondeur et nous devons balayer l'ensemble du registre avant de conclure qu'un noeud est inédit ou non. En revanche, elle est économe en ressource car nous sommes sûrs d'avoir à chaque étape le graphe minimal représentant le dictionnaire.

Le choix de la méthode dépendra donc en grande partie du nombre de mots dans le dictionnaire à compresser et des ressources dont nous disposons.

Ces temps de construction peuvent être réduits en optimisant le code et en le rendant moins pédagogique (suppression des calculs et variables intermédiaires, dimensionnement du Dictionnaire en une seule fois au début, en prévoyant large pour éviter les tests et les redimensionnements en cours de route, etc.).

Pour avoir un aperçu sur l'utilisation d'un DAWG dans une application, j'ai fait un petit solveur de scrabble disponible ici http://codes-sources.commentcamarche.net/source/100473-excel-vba-jouer-au-scramble-duplicate

Un grand merci à Whismeril qui m'a donné l'idée d'écrire ce tutoriel, qui m'a aidé dans sa conception et qui a bien voulu relire et corriger le document avant sa publication.

Sur ce, je vous remercie d'avoir lu ce document jusqu'au bout. Vos commentaires, suggestions et critiques sont les bienvenus pour améliorer ce tutoriel.

Références

A voir également

Publié par carlvb.
Ce document intitulé «  COMPRESSION D'UN DICTIONNAIRE SOUS FORME DE DAWG  » issu de CodeS-SourceS (codes-sources.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Comm WinSock VB6 <-> VB.Net (Encoding, UTF-8, Unicode)
VBA Excel : Lecture, Modification et Enregistrement d'un fichier txt