Donnez votre avis

Compilation d'un fichier txt en structure d'arbre

Posez votre question


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.

A voir également

Publié par pijaku. Dernière mise à jour le 6 août 2014 à 14:34 par pijaku.

Ce document intitulé «  Compilation d'un fichier txt en structure d'arbre  » issu de CodeS-SourceS (https://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.

Ajouter un commentaire

Commentaires

Commenter la réponse de Utilisateur anonyme