Discussion :

[Giovanny Temgoua]

Une recherche sur le forum n'a pas donné grand chose, c'est pourquoi que je poste ceci.

En fait, je suis à la recherche de la meilleure idée (en terme de performance) pour construire un dictionnaire à l'aide d'arbre binaire.

Toutes les idées seront le bienvenue.

Merci

PS : le temps de finir mon code et je le poste, mais le moins qu'on puisse dire est qu'il n'est pas optimisé

[Don Quiche]

Un arbre binaire ? A part un gain mémoire (aux dépens de la vitesse) qu'est-ce que ça apporte par rapport à un 26-arbre (je ne sais pas si le terme est exact : un arbre dont chaque noeud peut contenir jusqu'à 26 enfants) ? A moins que ce ne soit ce à quoi tu songes ?

[kaisse]

Bah en fait je suis d'accord avec l'idée du 26-arbres. Si toutefois tu veux vraiment un arbre binaire, alors il suffit de transformer ton arbre 26 en arbre 2 selon la bonne vieille méthode

En fait, tous les fils de l'arbres sont à sa gauche. Son premier fils est son fils gauche, son deuxieme, le fils droit de son fils gauche, et le nieme et le fils droit du nieme-1 fils.

Par conséquent, le fils droit d'un arbre et donc son "frere"

Exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
                     1
                /    |    \
               2     3     4
               |     | \
               5     6  7

deviendra

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
                1
               /
              2
            /    \
           5       3
                 /   \
                6    4
                  \
                   7

Voili voilou, mais comme tu connais la taille de l'alphabet (26) ce serait plus judicieux de conserver un arbre 26-aire

[Don Quiche]

Si vraiment tu veux gagner de la place tu peux toujours utiliser un index entier sur 32 bits, chaque bit contenant true si la lettre correspondante existe. Ca te permet de ne pas allouer 26 enfants à chaque fois, soit 4*(n+ 1 pour le tableau + 1 pour l'index) bytes par lettre où n est le nombre d'enfants. La différence en mémoire avec un arbre idéal est sans doute faible.

[Giovanny Temgoua]

Voilà, je pensais aussi à un "26-arbre" mais je me disais que ce serait trop lourd! sinon merci pour vos propositions!

Je me suis d'ailleurs rendu compte en travaillant qu'avec un arbre binaire, c'était plutôt impossible

Merci encore.

[Giovanny Temgoua]

Bon, voilà le code de mon dictionnaire...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
program ledico;
uses crt;
type Dictionnaire = ^noeud;
     noeud = record
              info : string;
              Sd : array[1..26] of dictionnaire;
             end;
     Tableau = array[1..100] of integer;
 
procedure Init(var Dico : Dictionnaire);
var i : integer;
begin
     new(Dico);
     Dico^.info := 'Le dico';
     for i:= 1 to 26 do Dico^.Sd[i] := nil;
end;
 
procedure Decompose(mot : string;var tab : Tableau);
var i : integer;
begin
     for i:=1 to Length(mot) do mot[i]:=UpCase(mot[i]);
     for i:=1 to Length(mot) do begin
         tab[i] := Ord(mot[i]) - 64;
     end;
end;
 
function VerifieMot(mot : string) : boolean;
begin
end;
 
procedure InsertMot(var Dico : Dictionnaire;mot : string;tab : Tableau;var i : integer);
var j : integer;
begin
     i := i + 1;
     if i<= Length(mot)-1 then begin
        if Dico^.Sd[tab[i]] = nil then begin
           new(Dico^.Sd[tab[i]]);
           Dico^.Sd[tab[i]]^.info := '$';
           for j:= 1 to 26 do Dico^.Sd[tab[i]]^.Sd[j] := nil;
        end;
        InsertMot(Dico^.Sd[tab[i]],mot,tab,i);
     end
     else begin
              if Dico^.Sd[tab[i]] = nil then begin
                  new(Dico^.Sd[tab[i]]);
                  for j:= 1 to 26 do Dico^.Sd[tab[i]]^.Sd[j] := nil;
              end;
              if (Dico^.Sd[tab[Length(mot)]]^.info = mot) then Writeln('Mot deja insere!')
              else Dico^.Sd[tab[Length(mot)]]^.info := mot;
          end;
 
end;
 
procedure Parcours(Dico : Dictionnaire);
var i : integer;
begin
     if (Dico<>nil) then begin
        Writeln(Dico^.info);
        for i:=1 to 26 do Parcours(Dico^.Sd[i]);
     end;
end;
 
var i,j : integer;
    mot : string;
    tab : Tableau;
    Dico : Dictionnaire;
begin
     ClrScr;
     Init(Dico);
 
     Writeln('Entrez un mot : ');
     Readln(mot);
     While (mot<>'.') do begin
           i := 0;
           Decompose(mot,tab);
           InsertMot(Dico,mot,tab,i);
           Writeln('Un autre : ');
           Readln(mot);
     end;
 
     Writeln;
     Parcours(Dico);
 
    (* for j:= 1 to 26 do dispose(Dico^.Sd[j]);*)
     Dispose(Dico);
     Readln;
end.

L'astuce à laquelle j'ai pensé est de "décomposer" le mot et d'enregistrer cette décomposition dans un tableau. C'est à dire que j'identifie chaque lettre par le chiffre qui lui correspond (ex : ane sera décomposé par 1 14 5) et j'obtient ainsi un chemin qui me permet d'insérer l'élément (dans le cas du mot ane, je chemin sera insère dans le sous arbre 5 du sous arbre 14 du sous arbre 1).

Les '$' , je les utilise pour pouvoir insérer un mot même si sa "tête" n'est pas insérée (la tête de ane est a par exemple), et comme cà j'obtiendrai toujours un dictionnaire ordonné si je le parcours en descente gauche.

Il y'a une autre méthode? Et déjà comment vous trouvez celle-ci?

[Don Quiche]

Ben vu la structure que tu as choisie, les perf sont maximales et la consommation mémoire aussi. Par contre dans un cas réel où ut initialise ton appli en lisant des milliers de mots dans un fichier tu auras intêret à ne pas utiliser InsereMot (tu peux notamment supposer que ton fichier ne contient pas d'erreurs).

A propose de l'idée que j'avais émise concernant l'utilisation d'un index, cela suppose que tu puisses allouer la mémoire dynamiquement. Ca fait dix ans que je n'ai plus fait de Pascal et à l'époque je n'utilisais même pas d'objets, alors je ne connais pas les possiblités de ce langage.

[Giovanny Temgoua]

Hum! Je n'avais pas pensé à utiliser une allocation dynamique de la mémoire, je vais voir cà

Sinon, j'ai aussi écrit une fonction LoadFromFile qui charge le Dico depuis un fichier et on peut continuer l'enregistrement sans problème (c'est une version modifiée de ce que j'ai posté tout à l'heure).

Bon et puis vu l'algo que j'ai proposé le programme peut s'écrire dans n'importe quel langage. Cependant, je ne vois pas trop comment la mémoire est gaspillée (je ne crée un objet que lorsque j'ai besoin d'insérer un mot!).

[Don Quiche]

La mémoire est gaspillée parce que si une lettre n'est pas suivie de 26 ramifications (exemple : si ton dico contient alors et allô, le premier l n'a que deux branches), tu alloues tout de même 26*4 octets (+ 2 octets pour le tableau + la taille de ton objet, 3 octets je crois). En fait, avec l'index que je t'ai proposé tu alloues 2 lettres *4 octets + 1 octet pour l'index, plus ...
Pour le seul mot anticonstitutionnellement, tu alloues actuellment 26 lettres * (26*4 + 2 + 3) octets. Avec un index, tu alloues 26 * (1*4 + 1 + 2 + 3) octets. Maintenant le parcours de l'arbre est un peu ralenti. Une solution intermédiaire consiste à remplacer l'index par un tableau de 26 bytes (1 octet) contenant chacun soit -1 si la lettre n'est pas présente, soit l'index de cette lettre dans ton tableau Sb. Dans ce cas, chaque noeud représente 26*1 + n*4 + 2*2 (2 tableaux) + 3 octets où n est le nombre de lettres.

N'oublies pas que dans un cas réel (ici il semble que ce soit un exercice de cours, non ?), tu n'as pas 26 caractères possibles mais bien plus (les accents, traits d'unions, caractères ae, oe, ...) et la gaspillage de mémoire peut être très important. On peut l'estimer à partir de la fréquence de chaque longueur de mot dans la langue française.

[Giovanny Temgoua]

Voilà, j'ai plusieurs fois relu ton post Don Quiche, mais il reste des coins un peu confus

En fait, contrairement aux constructions de dictionnaires que j'ai vu sur le Net (on insère un mot en insérant les lettres qui le composent au fur et à mesure), je crée directement le mot à une position fixe et uniquement les mémoires utilisées par les positions intermédiaires sont allouées (exemple : je veux insérer le mot merci qui se décomposera en 13 5 17 3 9, j'allouerai que l'espace aux noeuds 13, 5, 17 3 et finalement 9 qui contiendra le mot; les autres noeuds non concernés resteront à nil donc à ce moment l'arbre sera dégénére puisque chaque noeud n'aura qu'un fils, les autres valant nil).

De même, à ce niveau le parcours (à mon avis) ne sera pas trop ralenti puisque l'arbre est dégénérée (je précise qu'on a inséré que le mot 'merci').

Donc, si tu peux un peu plus m'éclairer à ce niveau...

En passant, ce n'est pas un exercice de cours mais le prof a mentionné quand même en cours qu'on pouvait créer des dictionnaires en utilisant les arbres. Depuis un moment, je cherche aussi des cours dessus avec google mais de très bon résultats donc si quelqu'un a quelques liens intéressants à propos des arbres (n-aires surtout) (je continue néanmoins de chercher).

Merci.

@+

[Don Quiche]

Même si tu n'alloues pas un noeud tu as réservé une case mémoire de 4 octets pour contenir l'adresse de ce noeud que tu pourrais éventuellement être amené à créer. Que cette cas contienne nil (0) ou une véritable addresse, tes 4 octets sont bien bouffés. Alors pour "Merci", tu as bien pris 5 noeuds * (26*4 + 2 +3) = 496 octets pour 5 lettres.
Si tu crée des noeuds avec beaucoup d'enfants, ce n'est pas une perte énorme mais si tes noeuds n'ont qu'un seul fils (comme la plupart des lettres qui composeront les terminaisons de tes mots), tu gaspilles beaucoup : Presque 100 octets par lettre n'ayant qu'un seul fils.

En ce qui concerne les performances, j'ai dû être flou : Avec la solution que tu retiens actuellement, pas de prob : Les performances sont les meilleures possibles. C'es en utilisant des solutions alternatives pour économiser la mémoire que tu peux être amené à réduire les perfs.

Voilà, j'espère que cette fois j'ai été un peu plus clair.

[Giovanny Temgoua]

Ok! C'est très clair maintenant

Merci.