Le présent tutoriel présente une méthode de compression de dictionnaire par sa représentation sous forme de DAWG.
Trois grands avantages peuvent être cités pour la compression de 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.
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.
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 :
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.
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 :
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 ».
Les grandes étapes de cette méthode sont les suivantes :
Les grandes étapes de cette méthode sont les suivantes :
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.
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 :
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.
ATTENTION : la valeur 14 en ligne 9 colonne 14 de la lettre N est en vérité en ligne 9 colonne 15 pour la lettre O ( la cellule L9-C14 pour la lettre N est vide )
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.
ATTENTION : : la valeur 8 en ligne 7 colonne 14 de la lettre N est en vérité en ligne 7 colonne 15 pour la lettre O ( la cellule L7-C14 pour la lettre N est vide )
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 :
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.
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.
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.
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.
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.