Ce tutoriel est une partie de :
celui-ci.
Prérequis
Un dictionnaire « brut » disposant d'un mot par ligne.
Cf tutoriels :
Lecture Modification Enregistrement txt
Création d'un dictionnaire au format texte
But
Créer un dictionnaire « compilé » sous la forme d' un arbre afin de faciliter et accélérer la recherche de mots « possibles » à partir d'une grille de lettres.
Structure d'un arbre
Un schéma valant mieux que de longs discours, voici la structure d'un arbre composé des mots :
ARA, ARBRE, ARBUSTE, ARBUSTES, ARBUSTIVE, ARBUSTIVES, BALEINE, BALI, BARMAN, BIRMAN, OLIVE, OLIVIER.
Légende :
- Les lettres représentent les noeuds
- Les « _ » représentent les fins de « chemin » composants les différents mots
Pour faire comprendre à notre code que l'on descend ou remonte d'un niveau, que l'on passe au noeud suivant ou que le chemin qui compose le mot est terminé, il va falloir insérer d'autres caractères. Cependant, nous verrons en fin de tutoriel une méthode permettant d'en réduire le nombre afin de ne pas trop gonfler notre fichier.
Méthode
Nous voulons que l'arbre dessiné plus haut soit stocké, selon cette structure, dans un fichier texte. Nous pourrons alors lire, écrire dans ce fichier. Pour cela, il nous faut créer un fichier texte comprenant un noeud (donc un caractère) par ligne, avec, en sus, certains caractères nous permettant de « naviguer » de noeuds en noeuds pour reproduire les chemins des mots.
Dans la notation retenue :
- "[" indique qu'on descend d'un niveau pour parcourir un noeud fils,
- "(" indique qu'on passe au noeud suivant le noeud actuel,
- "]" indique qu'on remonte d'un niveau vers le noeud parent,
- "." indique la fin d'un chemin, et donc d'un mot.
Ce que l'on veut obtenir, dans le fichier texte compilé :
[ => descente d'un niveau à partir du début
A
[ => descente d'un niveau du noeud "A" pour arriver à son premier "noeud fils" ( = R )
R
[
A
[
. => fin du chemin "ARA"
] => remontée d'un niveau pour revenir au noeud parent de A ( = R )
( => passage au noeud suivant (toujours dans les noeuds fils de R) ( = B )
B
[
R
[
E
[
.
]
]
(
U
[
S
[
T
[
E
[
.
(
S
[
.
]
]
]
(
I
[
V
[
E
[
.
(
Etc...
Structure du code
Voici donc les étapes que nous devons réaliser pour créer notre fichier compilé :
- Créer le noeud « racine » de l'arbre,
- Ouvrir le fichier source,
- Lire ce fichier ligne par ligne (donc mot par mot puisque notre fichier .txt initial est composé d'un mot par ligne)
- Découper le mot lettre par lettre,
- Parcourir l'arbre pour vérifier si la lettre est déjà créée dans un « embranchement »
- Si oui => on passe à la lettre suivante
- Si non => on crée un nouveau noeud de valeur = lettre
- A chaque fin de ligne (donc de mot), on va créer un nouveau noeud de valeur "."
- Fermer le fichier texte source
- Générer le fichier texte
- Création de son entête (« NBMOTS » + nombre de mots)
- Parcourir l'arbre de manière récursive
- Enregistrement de chaque noeud et caractères indicatifs pour mémoire :
- "[" indique qu'on descend d'un niveau pour parcourir un noeud fils
- "(" indique qu'on passe au noeud suivant le noeud actuel
- "]" indique qu'on remonte d'un niveau vers le noeud parent
- Les "." ont déjà été placés dans une étape précédente (cf ** ci-dessus)
- Fermer le dictionnaire compilé
Une procédure unique regroupant toutes ces actions serait difficilement compréhensible et pas très aisée à la maintenance. Nous allons, par conséquent, créer plusieurs fonctions.
Dans un module standard, il nous faudra :
- Une fonction parcourant l'arbre pour vérifier si la lettre est déjà créée dans un « embranchement »,
- Une fonction qui ajoute un noeud fils à un noeud,
- Une fonction récursive qui parcourt l'arbre et inscrit les caractères nécessaires à la création de notre fichier compilé.
La gestion des collections extensibles est ardue sous VBA. Pour d'autres langages, la filiation est gérée implicitement. Mais, sous VBA,, comme nous allons instancier un objet Noeud « parent », et lui créer des Noeuds « fils », il va nous falloir créer un module de classe. En effet, ce type de module permet d'instancier un (des) objet(s).
Les Codes
Le module de classe
Nommé Classe_Noeud,
Code :
'Dans un module de classe, l'objet parent est l'objet instancié à partir de la classe.
'Cette classe représente un noeud dans le dictionnaire constitué sous forme d'un arbre.
'Nous aurons donc besoin de 3 membres de la classe Classe_Noeud (membres qui définiront les caractéristiques de notre noeud) :
Public Parent As Classe_Noeud
Public Fils As Classe_Noeud
Public Suivant As Classe_Noeud
'et forcément nous aurons également besoin d'une propriété :
Public Valeur As String
Le Module
Nommé : Module1 (ou par le nom que vous souhaitez, exemple : Module_Traitement)
Code :
Option Explicit
Dim Debut As Classe_Noeud, Noeud As Classe_Noeud, Noeud_Actuel As Classe_Noeud
Sub Compiler_Dictionnaire()
'Cette procédure ouvre une liste de mots dans un fichier texte "normal"
'puis crée le dictionnaire sous forme d'un arbre
'et enfin, enregistre l'arbre sous un format pour en accélérer le chargement
Dim i As Integer, j As Integer
Dim Nombre_Mots As Long
Dim FF As Integer: FF = FreeFile
Dim test As String, MonDicoBrut As String, MonDicoCompile As String
Dim Mot As String, Partie As String
MonDicoBrut = ThisWorkbook.Path & "\dicoexemple.txt"
MonDicoCompile = ThisWorkbook.Path & "\dicocompile.txt"
'On crée un noeud dénommé Debut à la racine de l'arbre
Set Debut = New Classe_Noeud
Set Noeud_Actuel = Debut
'Ouverture du fichier source et lecture des mots ligne par ligne
Open MonDicoBrut For Input As #FF
While Not EOF(FF) 'On boucle tant qu'il y a des mots dans le fichier source
Line Input #1, Mot 'lecture de la ligne
'On débute à la racine de l'arbre
Set Noeud_Actuel = Debut
'On compte le nombre de mots (utile pour la création d'une entête à notre fichier compilé)
Nombre_Mots = Nombre_Mots + 1
'On prend un mot et on le découpe lettre par lettre
j = Len(Mot)
For i = 1 To j
Partie = Mid(Mot, i, 1)
'Si une lettre n'est pas retrouvée parmi les fils d'un noeud on crée un nouveau noeud
If Not trouve(Noeud_Actuel, Partie) Then Set Noeud_Actuel = Ajouter_Fils(Noeud_Actuel, Partie)
Next i
'En arrivant à la fin d'un mot, on crée un noeud final
If Not trouve(Noeud_Actuel, ".") Then Set Noeud_Actuel = Ajouter_Fils(Noeud_Actuel, ".")
Wend 'mot suivant
Close #FF
'Génération du dictionnaire compilé
Open MonDicoCompile For Output As #FF
'Création de l'entête du fichier avec le nombre de mots
Print #1, "NBMOTS" & Nombre_Mots
'On parcourt l'arbre de manière récursive
Parcourir_Noeud Debut
Close #FF
Set Noeud_Actuel = Nothing
End Sub
Private Function trouve(ByVal Noeud As Classe_Noeud, Lettre As String) As Boolean
'On parcourt l'arbre
'Cette fonction vérifie si une lettre est déjà créée au niveau d'un embranchement de l'arbre
'Si la lettre est déjà présente, la fonction retourne vrai et la variable Noeud_Actuel pointe sur le noeud où la lettre a été trouvée
If Not Noeud.Fils Is Nothing Then
Set Noeud = Noeud.Fils
If Noeud.Valeur = Lettre Then
trouve = True
Set Noeud_Actuel = Noeud
Exit Function
Else
While Not Noeud.Suivant Is Nothing
Set Noeud = Noeud.Suivant
If Noeud.Valeur = Lettre Then
trouve = True
Set Noeud_Actuel = Noeud
Exit Function
End If
Wend
End If
End If
End Function
Private Function Ajouter_Fils(ByVal Noeud As Classe_Noeud, Lettre As String) As Classe_Noeud
'Cette fonction ajoute un fils à un noeud
'Un noeud parent pointe sur le premier noeud fils
'Le noeud fils ainsi désigné pointe sur le prochain noeud fils et ainsi de suite
Set Ajouter_Fils = New Classe_Noeud
Set Ajouter_Fils.Parent = Noeud
Ajouter_Fils.Valeur = Lettre
If Noeud.Fils Is Nothing Then
Set Noeud.Fils = Ajouter_Fils
Else
Set Noeud = Noeud.Fils
While Not Noeud.Suivant Is Nothing
Set Noeud = Noeud.Suivant
Wend
Set Noeud.Suivant = Ajouter_Fils
End If
End Function
Private Sub Parcourir_Noeud(ByVal Noeud As Classe_Noeud)
'Cette procédure parcourt l'arbre de manière récursive et enregistre ligne par ligne le parcours effectué
'Dans la notation retenue :
'"[" indique qu'on descend d'un niveau pour parcourir un noeud fils
'"(" indique qu'on passe au noeud suivant le noeud actuel
'"]" indique qu'on remonte d'un niveau vers le noeud parent
Print #1, Noeud.Valeur
If Not Noeud.Fils Is Nothing Then
Print #1, "["
Parcourir_Noeud Noeud.Fils
Print #1, "]"
End If
If Not Noeud.Suivant Is Nothing Then
Print #1, "("
Parcourir_Noeud Noeud.Suivant
End If
End Sub
Voyons plus loin
Comme promis plus haut, nous allons maintenant tenter de réduire encore le poids de notre fichier, tout en conservant cette structure.
Descentes de niveau
Pourquoi indiquer, par un caractère, que l'on descend d'un niveau pour parcourir un noeud fils ? Intuitivement, on sait qu'un niveau est composé d'un et un seul caractère. Intuitivement, on peut le faire comprendre à la machine.
Remontées de niveau
Pour remonter, nous avons opté pour le caractère "]". Or, en cas de remontée de plusieurs niveaux, il nous faut placer, dans le fichier compilé, autant de "]" que de niveaux à remonter. La solution, pour réduire le nombre de caractères, est d'utiliser des chiffres à la place de "]". En effet, une remontée de cinq niveaux, peut simplement s'écrire 5 (dans ce cas, le gain en caractère est de 4).
NOTA : Comme nous avons prévu une lecture de ce fichier caractère par caractère, il convient de construire le dictionnaire compilé avec un unique caractère par ligne. Or, si la remontée de niveaux est supérieure à 9, nous allons obtenir une ligne avec deux caractères. Pour cela, il faut veiller à ce que le dictionnaire brut initial, contenant les mots, soit trié alphabétiquement.
Mise en oeuvre
La procédure Parcourir_Noeud devient :
Private Sub Parcourir_Noeud(ByVal Noeud As Classe_Noeud)
'Cette procédure parcourt l'arbre de manière récursive et enregistre ligne par ligne le parcours effectué
'Dans la notation retenue :
'"[" indique qu'on descend d'un niveau pour parcourir un noeud fils
'"(" indique qu'on passe au noeud suivant le noeud actuel
'"]" indique qu'on remonte d'un niveau vers le noeud parent
Nb = 0
Print #1, Noeud.Valeur
If Not Noeud.Fils Is Nothing Then
'Print #1, "["
Parcourir_Noeud Noeud.Fils
'Print #1, "]"
Nb = Nb + 1
End If
If Not Noeud.Suivant Is Nothing Then
If Nb > 0 Then Print #1, CStr(Nb)
Print #1, "("
Parcourir_Noeud Noeud.Suivant
End If
End Sub
Elargissement
On pourrait également se passer du caractère "." dans le dico compilé car il est suivi soit par un "(" soit par un nombre.
A vous de voir...
Aller encore plus loin
Pour cela, rendez-vous chez
Carlvb, pour sa description du DAWG :
http://codes-sources.commentcamarche.net/faq/10903-compression-d-un-dictionnaire-sous-forme-de-dawg
Téléchargement
Vous pouvez télécharger le zip de ce projet ici :
http://cjoint.com/?DHflonGj5Qv
Ce tutoriel est un complément de :
celui-ci. Vous pourrez y trouver un exemple d'utilisation.