COMPRESSION D'UN DICTIONNAIRE SOUS FORME DE DAWG
COMPRESSION D'UN DICTIONNAIRE SOUS FORME DE DAWG
- Description de la méthode
- Implémentation de la méthode sur Excel VBA
- Analyse de la performance et conclusion
- Références
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.
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 )
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
- The World's Fastest Scrabble Program (Andrew W. Appel, Guy J. Jacobson) http://www.gtoal.com/wordgames/jacobson+appel/aj.pdf
- Compressing dictionnaries with a DAWG (Steve Hanov) http://stevehanov.ca/blog/index.php?id=115
- Incremental Construction of Minimal Acyclic Finite-State Automata (Jan Daciuk, Bruce W. Watson, Stoyan Mihov, Richard E. Watson) http://acl.ldc.upenn.edu/J/J00/J00-1002.pdf
- Ko scrabble
- Graphe scrabble - Meilleures réponses
- Len scrabble valide - Meilleures réponses
- Dictionnaire de rimes anglais - Forum Delphi / Pascal
- Dictionnaire c++ ✓ - Forum C / C++ / C++.NET
- Dictionnaire en c? - Forum C / C++ / C++.NET
- Programmation d'un dictionnaire bilingue en C - Forum C / C++ / C++.NET
- Dictionnaire python ✓ - Forum Python