Discussion :

[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)

[femtosa]

Le code ascii des caractère et leur code huffma

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

[kuja2053]

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 me dire quelcodage ila utilisé?

[Sylvain Togni]

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.

[kuja2053]

Merci!

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

[Sylvain Togni]

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

Code :

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

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.

[Jean-Marc.Bourguet]

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

[kuja2053]

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

[Sylvain Togni]

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.

[kuja2053]

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

Merci !!