Discussion :

[BatuBou]

Bonjour a vous,
Je ne savais pas trop ou poster...

J'essaye de coder Huffman en C, mais des le début je ne sais plus quoi faire
ma structure étant la suivante

Code :

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

1
2
3
4
5
6
typedef struct code
{
 unsigned int frequence;
 unsigned int indice;
 short Fils0, Fils1;
}Code;

J'ai donc crée ma table d'occurrence avec les fréquences que j'ai trié par ordre croissant, j'obtiens donc une table de la forme

1: a _ 2
2: e _ 3
3: t _ 5

Mais maintenant la question qui se pose c'est comment créer l'arbre de Huffman?

Dois-je poursuivre ma première table qui contient 256 caractères avec des symboles possédant une fréquence a zéro ( qui va nuire a mon codage)
Je devrais donc avoir ma table a 512 éléments, je prends les deux min j'en fais un nouveau noeud et je le remet dans ma table, mais a quelle position? Dois je l'insérer en respectant l'ordre de ma table (pour préserver le fait qu'elle est triée).
Que dois je mettre dans mes fils0 et fils1?
La position dans ma table?
c'est a dire ici je construit un nouveau noeud en position 4 avec Fils0 = 1 et Fils1 = 2 et je le réinsère en position 1, je dois donc supprimer les deux noeuds que je viens de prendre?

Voila je m'excuse de la confusion de mon post mais ca reflète assez bien ma compréhension pour la création de l'arbre

Merci pour votre aide

[pseudocode]

Tout est expliqué sur le site de developpez.com (site que je vous recommande chaudement):

http://tcharles.developpez.com/Huffman

[BatuBou]

Merci pour votre reponse,
j'avais deja preté attention a ce tuto, mais le probleme c'est qu'il code avec des listes chainées et arbre... d'apres ce que j'ai compris...

Et moi mon probleme reside dans le fait que je ne sais pas comment passer de ma table trié a mon arbre avec ma structure de tableau...

[pseudocode]

Merci pour votre reponse,
j'avais deja preté attention a ce tuto, mais le probleme c'est qu'il code avec des listes chainées et arbre... d'apres ce que j'ai compris...

?

"IV-A. Etape 1" -> tu as le tableau des occurrences
"IV-B. Etape 2" -> tu as la construction de l'arbre

Je n'ai pas vu la mention "liste chaînée" dans tout l'article...

[BatuBou]

Bonjour, voila j'ai reussi a faire mon arbre de Huffman mais maintenant j'aimerais coder l'arbre et le message...

Mais comment faire pour savoir a la decompression qu'on est arrivé a la fin de notre arbre, et qu'on commence a lire notre message? et on doit aussi lire octet par octet pour le message, comment fait-on pour completer notre message a coder(pour la fin du message)?

Merci pour votre aide

[Pacorabanix]

Résumons : tu as un message codé de la forme d'une chaine de caractere :

"Message code pour huffman"

Tu comptes le nombre de caractères et construit donc une table caractere-frequence

Tu crées l'arbre de Huffman à partir de cette table.

Tu recrées ensuite une table pour faire correspondre un caractere avec son code huffman correspondant, en parcourant l'arbre dans tous les sens possibles. Ou alors tu "recherches" (avec une fonction récursive) chaque caractere (tu as la liste complète depuis la première étape) dans l'arbre et tu recrées le code selon si tu es passé "à droite" ou "à gauche" dans les 2 cas.

De meme pour l'algorithme de décodage, tu partiras directement de cette table "code-caractere".

Une fois que tu as une table de correspondance "caractere - code", tu lis simplement caractere par caractere ton texte et le "traduit" en codé. Ou inversément.

Le message est donc devenu une "suite de bits" .

Si tu as la suite de bits, aucun souci, tu lis le code jusqu'au bout et une fois à la fin de ton code le message sera décodé.

Après le problème des octets se passe si tu as par exemple sauvé ton code dans un fichier.

Tu peux toujours connaitre le nombre d'octet pris par un fichier, par contre en effet il te faudra savoir juste le nombre de bits pris par "le petit bout de fin". Et bien il suffit de diviser le nombre de bits par 8, et de voir le reste : ce sera le nombre de bits à lire dans le dernier caractere (les restants ne sont la que pour remplir). Et il te faut sauver cette valeur dans le fichier, en premier par exemple.

[BatuBou]

Merci pour votre reponse
J'ai maintenant du mal a comprendre quel algo appliqué pour reconstruire mon arbre de Huffman et ensuite lire mon message code

j'ai donc par exemple 0125518 ou 255 et 8 sont mes lettres mais comment faire pour reconstruire mon arbre? 0 indique le noeud (ici la racine) et 1 une feuille
Voici mon algo, mais il ne fonctionne pas du tout

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Arbre LitArbre(char c, char *Donnees)
 Arbre new=malloc(sizeof(Noeud_A));
 si new est NULL
  return new;
 si c =0
   | new->Lettre = '\0';
   | return new->FilsGauche = LitArbre(car suivant, Donnees)
   | return new->FilsDroit = LitArbre(car suivant, Donnees)
 
 si c = 1
   | new->Lettre = on lit notre lettre
   | return new;

Et quand j'aurais mon arbre, pour lire le message comment dois je proceder?

Merci pour votre aide