Algo huffman semi adaptative et adaptative

Bonjour
débutants, nous sommes un groupe de 4 étudiants.

Notre prof nous impose un sujet de projet en algo pseudo langage:
"le projet informatique que je vous propose est l'implémentation et le test sur des fichiers texte de
l'algorithme de compression d'Huffman dans ses deux versions :
- semi adaptative
- adaptative .
La validation se fera sur des textes en vérifiant qu'après décompression, on retrouve bien le texte original."

Se sont les seules données quand au cours sur les arbres il est quasi inexistant.

Problème : ces explications ou rien c'est pareil

Nous avons trouvé des info sur le net au sujet de l'algo d'huffman, mais de là à écrire l'algo y a un monde.

Pourriez vous nous aider, au moins à démarrer, savoir ce qu'il faut faire, qu'on essaye de comprendre , expliquer un peu "en français dans le texte :D"

L'implémentation se fera en C par d'autres personnes, nous ne devons fournir que l'algo en pseudo code.

Merci de votre aide

Déjà, un bon début : Algorithme de compression de Huffman

Merci j'ai regardé , ca explique un peu mieux mais je suis toujours incapable de dire comment commencer .

Nous ne voyons plus ce profs et donc pour les explications c'est juste par mail (déjà pas terrible en direct alors par mail ...)

Déjà que veut dire adaptative et semi adaptative ?

Citation:

---

Envoyé par lili78

Déjà que veut dire adaptative et semi adaptative ?

---

Comme le dit si bien wikipedia:

semi-adaptatif : le fichier est d'abord lu entièrement, de manière à calculer les occurrences de chaque octet, puis l'arbre est construit à partir des poids de chaque octet. Cet arbre restera le même jusqu'à la fin de la compression.

adaptatif : L'arbre est construit de manière dynamique au fur et à mesure que les octets sont lus. Il n'est donc pas nécessaire de connaitre les octets à venir.

Ca peut déjà commencer par découper votre algo en tâche de base :


semi-adaptative :

Compression :

- Pour commencer il faut lire le fichier et calculer le nombre d'occurence de chaque lettre.
- Construire l'arbre binaire de chaque lettre. Les plus présentes seront représentés sur 3 ou 4 bits. Les moins présentes
sur plus.
- Ecrire en début de fichier l'arbre de compression.
- Lire à nouveau le fichier et commencer à écrire le flux de donnée en sortie au fur et à mesure.
Il vous faudra probablement gérer un buffer d'écriture , car au plus bas en C on écrit des octets et pas 3 bits.


idem pour l'adaptative, il suffit de construire l'arbre au fur et a mesure de la lecture et de commencer à écrire
le fichier en sortie quand l'arbre est complet ou que la fin de fichier est atteinte.


Décompression (identique avec les deux méthodes) :

- Lire l'arbre de compression dans l'entete du fichier.
- Décoder les bits lus avec votre arbre.
- Ecrire les octets complet en sortie. Vous aurez aussi une gestion de buffer à faire de la même manière que dans la compression.