Discussion :

[WhiteCrow]

Juste pour l'algo d'insertion (avec tri) :

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
insertion(arbre, mot)
début
    résultat = arbre
    si arbre est NULL alors
        résultat = créer_arbre(mot)
    sinon si arbre.lettre = mot[0] alors
        si mot[0] != fin_de_mot
            arbre.fg = insertion(arbre.fg, mot[1..])
        fin si
    sinon si arbre.lettre > mot[0] alors
        résultat = créer_arbre(mot)
        résultat.fd=arbre.fd
    sinon
        arbre.fd=insertion(arbre.fd, mot)
    fin si
 
    renvoyer résultat
fin.

avec

Code :

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

1
2
3
4
5
6
7
8
9
créer_arbre(mot)
début
    résultat = nouvelle_feuille(mot[0])
    si mot[0] != fin_de_mot alors
        résultat.fg = créer_arbre(mot[1..])
    fin si
 
    renvoyer résultat
fin.

avec le caractère fin_de_mot de rang inférieur à n'importe quelle lettre.

[BBouille]

Super, merci WhiteCrow.
Je vais essayer de mettre ça en musique avec ma partition bien pauvre.
De prime abord ce que je pige le moins c'est mot[0] et mot[-1..] mais je vais tenter de décortiquer ça.
Merci encore.

[Guesset]

Bonjour BBouille,

Oui mais si j'ai bien compris l'avantage d'un arbre binaire c'est que tu diminues le nombre d'entrées.

Il est toujours important de bien choisir l'organisation des des données (porte ouverte enfoncée).

Pour un dictionnaire, les données élémentaires dans un arbre sont les lettres. Mais chaque lettre supplémentaire coûte un vecteur de 2 à 8 octets plus l'octet de la lettre.

Une organisation en tableau de chaînes coûtera en octets le nb de lettres du mot + 1 + 1 vecteur (2 à 8 octets).

Dans l'absolu, la représentation binaire apparaît plus économique mais les mots ne sont pas équirépartis. Le langage courant utilise des mots de longueur moyenne d'environ 5 caractères (et 10 pour un dictionnaire complet).

Donc, selon l'usage le meilleur choix devra être murement réfléchi d'autant que la place n'est qu'un élément. Les vitesses de recherche et d'insertion sont également importantes. Mais là encore cela dépend de l'usage. Si le dictionnaire n'évolue pas ou peu, la vitesse d'insertion est assez accessoire.

Bon courage

[WhiteCrow]

Super, merci WhiteCrow.
Je vais essayer de mettre ça en musique avec ma partition bien pauvre.
De prime abord ce que je pige le moins c'est mot[0] et mot[-1..] mais je vais tenter de décortiquer ça.
Merci encore.

mot est une chaîne de caractère, mot[0] est le premier caractère de cette chaîne, mot[1..] est la chaîne privée de son premier caractère. Par exemple si mot="HELLO∎", mot[0] vaudra 'H' et mot[1..] vaudra "ELLO∎" avec ∎ le caractère spécial marquant la fin d'un mot.

[BBouille]

Oui WhiteCrow en encodant je me suis rendu compte de la signification du 1.., merci.
J'ai donc encodé ton algorithme. Le programme ne se plante pas mais j'ai encore des interrogations.
Cette fois-ci j'ai créé une "class" avec les différentes procédures et variables, chose que je fais rarement car j'ai du mal avec les constructor et autres.
Donc je m'emmêle les pinceaux avec les déclarations de l'arbre et ses sous-arbres en local ou global...

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
t_ArbreWC(fg As t_ArbreWC,fd As t_ArbreWC,Lettre As String)
*******************************************************************************
LOAD_MOTS
Du premier mot au dernier faire
ArbreWC = INSERTION( ArbreWC, StrX )
*******************************************************************************
INSERTION(Arbre As t_ArbreWC, Mot As String)t_ArbreWC
  Dim Result As t_ArbreWC
 
  if Arbre is Nil Then
    Result = CREER_ARBRE( Mot )
  else
    Lettre = Mid( Mot, 1, 1 )
    if Arbre.Lettre = Lettre Then
      if Lettre <> FindeMot Then
        Arbre.fg = INSERTION( Arbre.fg, Mot )
         Mot = Right( Mot, Len(Mot)-1 )  // On efface la première lettre du mot.
      end if
    elseif Arbre.Lettre > Lettre Then
      Result = CREER_ARBRE( Mot )
      Result.fd = Arbre.fd
    else
      Arbre.fd = INSERTION( Arbre.fd, Mot )
    end if
  end if
 
  Return Result
*******************************************************************************
CREER_ARBRE(Mot As String)t_ArbreWC
  Dim Result As t_ArbreWC
 
  Lettre = Mid( Mot, 1, 1 )
 
  CREATION_CELL(  Result, Lettre )
 
  Mot = Right( Mot, Len(Mot)-1 ) 
 
  Lettre = Mid( Mot, 1, 1 )
 
  if Lettre <> FindeMot Then
    Result.fg = CREER_ARBRE( Mot )
  end if
 
  Return Result
*******************************************************************************
CREATION_CELL(ByRef p_Elemt As t_ArbreWC, Lettre As String)
  p_Elemt = New t_ArbreWC
  p_Elemt.Lettre = Lettre
*******************************************************************************

Et un truc (déjà vu dans les arbres n-aires) que j'ai du mal à me représenter c'est

Code :

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

 elseif Arbre.Lettre > Lettre Then

Je ne comprends pas le >.
Si tu pouvais me dire où je me suis planté je crois que je serai presque sorti de l'auberge.
Par exemple pour faire une recherche de mot (procédure qui fait partie de la class) comment déclarer l'arbre dans lequel la recherche doit s'effectuer?
Guesset, j'ai déjà du mal avec ce programme et à comprendre comment est gérée en interne la récursivité alors ne viens pas me demander de gérer la mémoire en plus

[WhiteCrow]

En avant propos, remarque que je n'ai jamais pratiqué RealBasic …

Il est important de savoir un minimum comment est gérée la mémoire car si tu as une variable locale créée sur la pile tu ne peux pas la renvoyer (du moins renvoyer son adresse ou un référence à elle) en sortant de ta fonction, il est aussi important de savoir si tes paramètres sont passés par référence ou par copie.

Modifier le mot en ligne 17 ne sert à rien, au retour de l'appel fait en ligne 16 il aura été inséré et tu te retrouves en fin de fonction à renvoyer le résultat. En revanche il faut l'initialiser (l3 de mon algo) … tu devrais avoir une ligne Result=Arbre en tout début de fonction.

Les lettres sont des caractères qui ont un type (que je ne connais pas en RealBasic) mais on peut les comparer. Par exemple en unicode (utf8 ou ucs2 ou …) ou en ascii (7bits) 'A' vient avant 'B' qui vient avant 'C' … etc. On les compare en général avec < ou >, comme pour les nombres. On a 'A'<'B'<'C'<…<'Y'<'Z'. L'idéal serait de choisir le caractère fin de mot tel qu'il soit plus petit que n'importe quelle lettre de ton alphabet.

L'idée si tu choisis une approche OO sera d'avoir une classe Arbre (par exemple, mais BinTrie ou Lexicon serait plus adapté comme nom je suppose) dont un des champs pointerait sur la racine de l'arbre.
Le constructeur initialise le pointeur sur la racine d'une instance avec un pointeur NULL (ou équivalent).
Ta méthode insertion insérerait le mot à partir de cette racine.
Ta méthode recherche chercherait un mot à partir de cette racine.

[BBouille]

Bonsoir WhiteCown,
Avec RealBasic on ne peut pas transmettre par exemple Arbre.fg en tant que paramètre, il faut passer par une variable intermédiaire comme Temp = Arbre.fg ce qui me semble crée la pagaille quand on a 402305 mots, ça fonctionne mais ça prend un temps fou.
Donc j'ai tout repris à zéro pour éviter ce problème et j'ai créé une classe (type) Arbre, avec pour insérer chaque lettre de chaque mot:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Fonction Insert(Car As String)
 if Car < Lettre Then  
    if fGauche = Nil Then
      fGauche = New Arbre( Car )
    else
      fGauche.Insert( Car )
    end if   
  else   
    if fDroite = Nil Then
      fDroite = New Arbre( Car )
    else
      fDroite.Insert( Car )
    end if    
  end if

Ça a l'air de fonctionner comme je peux parcourir tout l'arbre et que ça affiche bien tous les caractères des mots.
Par contre je ne suis pas fichu de faire une recherche de mot dans l'arbre.
Si tu avais une idée de départ tu m'aiderais drôlement.
Excuse-moi de poster le code en RealBasic mais ça me semblait si proche d'un algorithme contrairement à d'autres langages.

[WhiteCrow]

L'algo de recherche est relativement simple :

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
chercher(arbre, mot) → booléen
début
    initiale = mot[0]
    si arbre.lettre = initiale alors
        si initiale = FIN_DE_MOT alors
            renvoyer VRAI
        sinon
            renvoyer chercher(arbre.fg, mot[1..])
        fin si
    si arbre.lettre < initiale alors
        renvoyer checher(arbre.fd, mot)
    sinon
        renvoyer FAUX
    fin si
fin.

Ce qui se comprends en français par :
Si tu es sur un nœud qui contient l'initiale de ton mot alors soit cette initiale est le marqueur de fin de mot et cela signifie que tu l'as trouvé donc on renvie vrai soit cette initiale n'est pas le marqueur de fin de mot et dans ce cas il faut vérifier que le reste du mot est contenu dans le sous arbre fils gauche.
Si tu es sur un nœud qui ne contient pas l'initiale mais que la lettre du nœud est plus petite que l'initiale alors le mot pourrait se trouver dans le sous arbre fils droit et du coup on lance une recherche dans ce sous arbre droit sur le mot en entier.
Et le dernier cas est que la lettre du nœud courant est plus grande que l'initiale du mot cherché, ce mot ne peut pas se trouver dans le fils gauche ni dans le fils droit : il n'est pas dans l'arbre et donc on renvoie faux.

[BBouille]

Ben oui c'est ce que je pense avoir fait.
J'ai retranscrit la fonction selon ton algorithme et j'ai le même problème.

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
Fonction Chercher(Mot As String, Rang As Integer) Boolean
 Dim Initiale As String
  Initiale = Mid( Mot, Rang, 1)
  if Car = Initiale Then
    if Car = "$" Then
      Return True
    else
      Return fgauche.Chercher( Mot, Rang+1 ) 
    end if    
  end if 
  if Car < Initiale Then
    Return fDroit.Chercher( Mot, Rang )
  else
    Return False
  end if

Tu verras sûrement pourquoi ça foire.
J'ai 2 mots :
COURS$
DANSE$
Je cherche DANSE dans l'arbre
À l'appel de la fonction : C D
Il trouve bien : C < D
Deuxième passage : O D
Et direction la sortie : O False: D
Il commence par les 2 premières lettres de COURT puis il sort.

[WhiteCrow]

tu as 2 if … il faut un else if en ligne 11 …
Si la première conditionnelle est vraie, une fois qu'il en sort il teste le second if (l11) qui sera forcément fausse et passera dans le else qui renverra false.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Fonction Chercher(Mot As String, Rang As Integer) Boolean
 Dim Initiale As String
  Initiale = Mid( Mot, Rang, 1)
  if Car = Initiale Then
    if Car = "$" Then
      Return True
    else
      Return fgauche.Chercher( Mot, Rang+1 ) 
    end if    
  elseif Car < Initiale Then
    Return fDroit.Chercher( Mot, Rang )
  else
    Return False
  end if

[BBouille]

Je suis vraiment nul WhiteCrow, je t'aurai bien embêté mais en fait la création de mon arbre est fausse.
Je veux tellement éviter de transmettre la variable Arbre en paramètre que j'ai tout trop simplifié et là en fait j'introduis toutes les lettres de chaque mot dans l'arbre.
Je vais laisser tomber et cesser de te déranger.
Merci encore.

[BBouille]

Peut-être un dernier essai.
Là au moins l'arbre se remplit, pas correctement mais il se remplit.
J'ai rajouté un appel à la fonction après avoir créé un nouveau noeud.

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
Fonction Insere(Car As String) Boolean
  if Lettre > Car Then
    if Gauche <> Nil Then
      Call Gauche.Insere( Car )
    else
      Gauche = New Arbre( Car )
      Call Gauche.Insere( Car )
    end if   
  else  // Lettre <= Car  
    if fData = Car Then
      Return True    
    else  // Lettre < Car
      if Droite <> Nil Then  
        Call Droite.Insere( Car )
      else
        Droite = New Arbre( Car )
        Call Droite.Insere( Car )
      end if      
    end if    
  end if

[wheel]

Vous utilisez deux viables différents dans le test d'abord avec Lettre > Car et après fData = Car ?? et vous ne récupérer pas le résultat des opérations dans les nodes enfants ..

Code :

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

1
2
 Return Gauche.Insere( Car ) 
..

[BBouille]

Oui pardon Wheel,
J'ai retranscris la fonction en franglais et j'ai oublié ça.
Le Call correspond dans mon langage à Trouve = Fonction Insere(Car As String)Boolean

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
Fonction Insere(Car As String) Boolean
  if Lettre > Car Then
    if Gauche <> Nil Then
      Call Gauche.Insere( Car )
    else
      Gauche = New Arbre( Car )
      Call Gauche.Insere( Car )
    end if   
  else  // Lettre <= Car  
    if Lettre = Car Then
      Return True    
    else  // Lettre < Car
      if Droite <> Nil Then  
        Call Droite.Insere( Car )
      else
        Droite = New Arbre( Car )
        Call Droite.Insere( Car )
      end if      
    end if    
  end if