Algorithme de Shanon-Fano / Arbre Binaire

[Arbrakan]

Bonjour,

Dernière lignes de code de l’année, et ça coince. j’aurai voulu finir l'année sans bugs, mais bon, le code

J'essaie, depuis 3 jours de crée un arbre binaire pour compressée une image grâce a l'algorithme de Shanon-Fano.

Le résultat voulu :

http://tpecompression.free.fr/?p=stat


Les arbres binaire, c'est du nouveau pour moi. J'ai trouvé un topic sur le forum qu'y explique bien le principe, je remercie hzj74 pour ce tuto. ( http://www.purebasic.fr/french/viewtopic.php?t=6244 )

j'ai donc bidouillé pour essayé de mélanger les 2, et arrivé au résultat voulu, mais ca coince, ca ne part pas dans les branche "1" de arbre. ce qui donne ce résultat :

Code : Tout sélectionner

18    0
17    00
8    000
6    0000
4    00000
2    000000
0    0000000

Donc, si vous avez une direction a me montrer, c'est avec plaisir. Car là, mon cerveau tourne en rond.


Pour le bout de code :

Code : Tout sélectionner

Global Dim monArray(18)

monArray(0) = 18
monArray(1) = 2
monArray(2) = 6
monArray(3) = 2
monArray(4) = 6
monArray(5) = 4
monArray(6) = 2
monArray(7) = 4
monArray(8) = 4
monArray(9) = 6
monArray(10) = 4
monArray(11) = 17
monArray(12) = 2
monArray(13) = 8
monArray(14) = 2
monArray(15) = 2
monArray(16) = 2
monArray(17) = 4
monArray(18) = 0

SortArray(monArray(), #PB_Sort_Descending)


Structure ARB
  valeur.b
  *_0.ARB
  *_1.ARB
EndStructure


; Procédure de création des arbres ou sous-arbres
Procedure arbre(*node.ARB,n)
If *node      ; le noeud existe déjà
  If n = *node\valeur
    *node\valeur = n
   ElseIf n < *node\valeur
     *node\_0=arbre(*node\_0,n)
   Else
      *node\_1=arbre(*node\_1,n)
  EndIf
Else
  *node = AllocateMemory(SizeOf(ARB))
  If *node     ; le noeud a été créé avec succès
    *node\valeur = n
     *node\_0 = #Null
     *node\_1 = #Null
  EndIf  
EndIf
ProcedureReturn *node
EndProcedure


Global binary.s,pass

Procedure affiche(*node.ARB,startBin.s)
  If pass=0 : binary.s=startBin.s : pass=1: EndIf
  If *node\_1 <> #Null : binary.s=binary.s+"1" : affiche(*node\_1,"") :  EndIf
  Debug Str(*node\valeur)+"    "+binary.s
  If *node\_0 <> #Null : binary.s=binary.s+"0" : affiche(*node\_0,"") :  EndIf
EndProcedure

; traitement ------------------------------------------------------------------

  For i=0 To ArraySize(monArray())
   *arbre_0=arbre(*arbre_0,monArray(i))
 Next  
 
 affiche(*arbre_0,"0")

Merci d'avoir pris le temps de me lire.

Arbrakan

[Ollivier]

Bonjour,

Pas d'ordi ces jours-ci, donc juste un doute à faire remarquer dans cet extrait:

Code : Tout sélectionner

 If n = *node\valeur
*node\valeur = n
ElseIf n < *node\valeur
*node\_0=arbre(*node\_0,n)
Else
*node\_1=arbre(*node\_1,n)
EndIf

Je ne comprends pas cette partie de code.

"Si a = b alors b = a"

???
Juste
"Si a < b
creuse à gauche
sinon
creuse à droite
finsi"

Pas de "ElseIf"

[Arbrakan]

Code : Tout sélectionner

If *node      ; le noeud existe déjà
  If n = *node\valeur
    ;void
   ElseIf n < *node\valeur
     *node\_0=arbre_0(*node\_0,n)
   Else
      *node\_1=arbre_0(*node\_1,n)
  EndIf
Else

C'est peut être plus opti comme cela, en effet.

Ça sert a tester si la donnée a la même valeurs que le nœud actuel.
si oui, on creuse pas plus loin. Pour évité d'avoir des doublons.

Sans ElseIf

Code : Tout sélectionner

9    0
8    00
4    000
3    000011
3    000011
3    000011
2    0000110111
2    0000110111
2    0000110111
2    0000110111

Avec ElseIf

Code : Tout sélectionner

9    0
8    00
4    000
3    0000
2    00000

Après je sais pas si j'ai bien compris le principe de ce code justement, je sens que c'est dans cette zone que ça coince.

Merci pour ton temps en tout cas.

[comtois]

la construction de l'arbre est bonne, c'est l'affichage qui déconne.

Code : Tout sélectionner

Global Dim monArray(18)

monArray(0) = 18
monArray(1) = 2
monArray(2) = 6
monArray(3) = 2
monArray(4) = 6
monArray(5) = 4
monArray(6) = 2
monArray(7) = 4
monArray(8) = 4
monArray(9) = 6
monArray(10) = 4
monArray(11) = 17
monArray(12) = 2
monArray(13) = 8
monArray(14) = 2
monArray(15) = 2
monArray(16) = 2
monArray(17) = 4
monArray(18) = 0

;SortArray(monArray(), #PB_Sort_Descending)


Structure ARB
  valeur.b
  *_0.ARB
  *_1.ARB
EndStructure


; Procédure de création des arbres ou sous-arbres
Procedure arbre(*node.ARB,n)
  If *node      ; le noeud existe déjà
    If n < *node\valeur
      *node\_0=arbre(*node\_0,n)
    Else
      *node\_1=arbre(*node\_1,n)
    EndIf
  Else
    *node = AllocateMemory(SizeOf(ARB))
    If *node     ; le noeud a été créé avec succès
      *node\valeur = n
    EndIf 
  EndIf
  ProcedureReturn *node
EndProcedure

Procedure AfficheDecroissant(*node.ARB)
  If *Node <> #Null
    AfficheDecroissant(*Node\_1)
    Debug *Node\valeur
    AfficheDecroissant(*Node\_0)
  EndIf       
EndProcedure

Procedure AfficheCroissant(*node.ARB)
  If *Node <> #Null
    AfficheCroissant(*Node\_0)
    Debug *Node\valeur
    AfficheCroissant(*Node\_1)
  EndIf       
EndProcedure

; traitement ------------------------------------------------------------------

For i=0 To ArraySize(monArray())
  *arbre_0=arbre(*arbre_0,monArray(i))
Next 

AfficheDecroissant(*arbre_0)
Debug "******"
AfficheCroissant(*arbre_0)

[Arbrakan]

Yeah, ça part dans la bonne direction, merci comtois, et merci Ollivier pour votre science !
J'espère revenir pour vous présenté le code final dès que possible.

Merci pour l'aide !