Codage de l'arbre de Huffman

Signaler
Messages postés
2
Date d'inscription
samedi 5 mars 2005
Statut
Membre
Dernière intervention
16 mars 2005
-
Messages postés
6
Date d'inscription
vendredi 23 janvier 2009
Statut
Membre
Dernière intervention
7 janvier 2013
-
Je programme actuellement la compression de fichiers par la méthode de Huffman et j'ai terriblement besoin d'aide pour le codage le l'arbre!! J'ai essayé de comprendre les codes donnés sur ce site mais j'ai beaucoup de mal car je suis débutante..Voici la déclaration de mon arbre:
typedef struct SNoeud TNoeud;
struct SNoeud{
char carac; //définit un caractère
float occ; //définit une occurence
char CodeNoeud;
TNoeud* g; // pointeur gauche
TNoeud* d; // pointeur droit
};
TNoeud *noeud;
TNoeud *Racine;
Dois je déclarer autre chose pour coder...???
Je connais le principe :lorsqu'on descend à gauche dans l'arbre on attribue 0 et à droite 1 .. mais en ce qui concerne la programmation, je n'y arrive pas.. MERCI pour votre aide..

3 réponses

Messages postés
70
Date d'inscription
jeudi 22 mai 2003
Statut
Membre
Dernière intervention
21 décembre 2005

à priori il y a tout ce qu'il faut pour construire ton arbre de Huffman.

même si je n'en aurai pas mis autant (occ ? et codeNoeud ?)



moi je ferait plutôt pour le codage :

struct Noeud{


int Indice; (0 ou 1)


Noeud *NoeudSuivant;

};

struct Code{

char caractere; // car à coder


int
NombreOcurrences; // facultatif mais pourquoi pas !


Noeud
*Racine; // son codage


};

aprés il n'y a plus qu'a parcourir la liste chainée pour
récuperer le code attribué à chaque caract : lecture de l'Indice à
chaque noeud de la liste) :

le plus dur n'est pas la programmation mais l'algo qui doit attribuer à
chaque caractère son code propre en fonction de son nombre d'occurences
dans le message(découpage).si tu l'as déja fait, l'arbre se construit
tout seul

Le découpage est fait ou non ?

En fait je pense qu'on a pas besoin de se prendre la tête avec la liste chainée pour la compression de huffman au niveau du codage.

mais bon, tentons !

dis moi déja comment se présente la liste des caractères que tu dois coder pour que je puisse mettre la main à la patte ;)



NB :

effectivement ta structure est la meilleure puisque l'arbre est utilisé
surtout pour le décodage et à ce moment là on a besoin des noeuds g et
d pour les bifurcations (bit à 0ou 1) pour savoir à quelle
caractère le code fait référence.

mais pour le codage tu peux trés bien te débrouiller sans.

De toute façon l'arbre est regénéré pour la décompression gràce à l'entête des données codées!



En fait avant tout !

que veux tu faire le codage ou le decodage ??
Messages postés
2
Date d'inscription
samedi 5 mars 2005
Statut
Membre
Dernière intervention
16 mars 2005

merci pour ton aide..
en fait je veux faire le codage..
au départ j'ai un fichier.. je lis le fichier et je range mes caractères avec les occurences dans une table. ensuite j'ai fait un arbre suivant la méthode d'huffman (en additionnant les minimums..etc) directement à partir de ma table... je n'ai pas fait de liste.. et là je suis completement coincée sur ce codage !!
Messages postés
6
Date d'inscription
vendredi 23 janvier 2009
Statut
Membre
Dernière intervention
7 janvier 2013

salut je m'essaie à la programmation et je voudrais faire la même chose que toi
pourrais tu me faire voir comment tu crée tes tables de charactères et de fréquence d'occurence et comment tu fais le tri?
merci d'avance.