en-tête codage huffman

D'aprés vous c'est quoi le mieux à mettre dans l'en-tête d'un fichier compressé par la méthode de huffman :

Le code ascii des caractère et leur code huffman
OU
Le code ascii et la fréquence des lettre correpondante (nécessité de reconstruire l'arbre)


:oops:

Citation:

---

Envoyé par kuja2053

Le code ascii des caractère et leur code huffma

---

Ca me paraît plus logique ! Qu'est-ce qui te fait hésiter ... ?

Pas forcément car c'est plus facile de parcourir un arbre que de chercher à quel lettre correspond "01001" par exemple. Et on ne peut refaire d'arbre avec juste la table de coddage de huffman !

Si quelqu'unà deja fé le codage de huffman pourrai t'il :cry: me dire quelcodage ila utilisé?

Citation:

---

Envoyé par kuja2053

D'aprés vous c'est quoi le mieux à mettre dans l'en-tête d'un fichier compressé par la méthode de huffman :

Le code ascii des caractère et leur code huffman
OU
Le code ascii et la fréquence des lettre correpondante (nécessité de reconstruire l'arbre)

---

Aucun des deux ! Le plus efficace en terme de place est de stocker l'arbre.

Merci!

Mais comment ça se stocke un arbre ?!!
car je parle de stockage dans l'entete du fichier compressé!8O

C'est assez simple. Supposons qu'on a l'arbre suivant :

Code:

---

1 2 3 4 5 6 7

/\ 0/ \1 / \ A /\ 0/ \1 / \ B C

---

Pour le stocker, on va le parcourir, disons en profondeur, fils gauche d'abord, en commençant par la racine. A chaque fois qu'on rencontre un nouveau noeud, on stocke 1 si c'est une feuille, 0 sinon.

Ce qui donne sur l'exemple 01011. C'est tout, seulement 5 bits.
Reste juste ensuite à stocker les codes des caractères A B et C.

Et à utilisé l'algo inverse pour le décodage.

Une technique alternative est de faire du Huffman adaptatif. Pas besoin de commencer par stocker des info de frequence.

Je vois pas comment tu peut reconstruir l'arbre car il y a plusiseur possibilité : les arbres peuvent également avoir cette forme

http://nicolas410.free.fr/huffman/images/huffman2.gif

On reconstruit noeud par noeud. L'arbre ci-dessus sera codé 00101011011, ce qui donne :
- on lit 0 => on construit un noeud (la racine)
- on lit 0 => on construit un noeud (le fils gauche de la racine)
- on lit 1 => on construit une feuille (le fils gauche du noeud précédent)
- on lit 0 => on construit un noeud (le fils droit du 2ème noeud, forcément, puisque le précédent est une feuille)
- ...
L'unicité est garantie par le sens du parcours, qui doit être le même à l'encodage et au décodage, et par le fait qu'une feuille stop le parcours en profondeur, et avance d'un cran en largeur.

Ah OK, j'ai pigé, en effet avec cette façon l'entête est trés court!!

Merci !!:yaisse2: :yaisse2: