Ce tutoriel est une partie de : celui-ci.
Un dictionnaire « brut » disposant d'un mot par ligne.
Cf tutoriels :
Lecture Modification Enregistrement txt
Création d'un dictionnaire au format texte
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.
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 :
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.
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 :
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...
Voici donc les étapes que nous devons réaliser pour créer notre fichier 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 :
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).
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
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
Comme promis plus haut, nous allons maintenant tenter de réduire encore le poids de notre fichier, tout en conservant cette structure.
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.
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.
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
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...
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
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.