Compression par Huffmann dynamique

Bonjour

Après une recherche qui ne m'a pas beaucoup aidée sur Google, je me tourne vers vous :D

Je voudrais savoir quelle est la différence entre une compression par Huffmann statique et par Huffmann dynamique et en quoi consiste l'algorithme de compression par Huffmann dynamique

Merci d'avance :wink:

J'espère ne pas me tromper.
La compression de Huffman statique suppose une loi de probilités a priori de la distribution des bits dans le fichier et l'arbre est évalué AVANT de lire le fichier à compresser.
Exemple : nous voulons compresser un texte en français. Après une étude statistique conséquente, on calcule les fréquences d'apparition de chaque lettre (négligeons la ponctuation)
A : 15%
B : 09.4%
...
E : 26.1%
...
Z : 1.4%
A partir de là on construit l'arbre de Huffman qui sera utilisé POUR tous les fichiers ultérieurs. Si par malheur on tombe sur un texte en anglais ou les W sont fréquents, les résultats seront moindres.
D'où l'idée de réaliser une compression "dynamique" en étudiant les fréquences non pas en général mais spécifiquement au fichier.
Première passe : on parcourt le fichier et on établit la table de fréquence (l'arbre)
Deuxième phase : on compresse à l'aide de cet arbre établi pour ce fichier seul

Bien sûr c'est plus lent, plus difficile mais cela fournit de meilleurs résultats.

L'explication de la différence est expliqué au dessus.
Pour l'algorithme dynamique:

Donc tout d'abord, parcourir le fichier à compresser, et calculer la fréquence de chaque caractère.

Ensuite on construit une Liste d'arbres, chaque arbre ayant comme information un caractère du fichier et sa fréquence, et ses deux fils étant NULL

Code:

---

1 2 3 4 5

Arbre a carac[a] frequence[a] fils_gauche[a] fils_droit[a]

---

Définition une fonction

Code:

---

extraire_min : Liste -> Arbre

---

qui retire l'arbre ayant la plus petite frequence dans la liste et le renvoie.
Le gros de l'algorithme de huffman est ceci:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Liste liste /* initialisée avec les arbres caractères-fréquences */   Tant que (Nombre d'éléments de liste) > 1 faire   Arbre gauche <- extraire_min(liste) Arbre droit <- extraire_min(liste)   Arbre nouveau <- creer_arbre   frequence[nouveau] <- frequence[gauche] + frequence[droit] fils_gauche[nouveau] <- gauche fils_droit[nouveau] <-droit   ajouter (liste, nouveau) /* ajout du nouvel arbre à la liste */   fin Tant que   retourner premier_élément[liste] /* la liste ne contient plus qu'un arbre */

---

Ensuite il faut construire les codes de chaque caractère, chacun étant à une feuille de l'arbre.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Map codage /* associera à chaque caractère son codage */ Chaîne chaîne <- 'chaîne vide' /* Contiendra le codage courant */   creer_codage : Arbre -> 'vide'   creer_codage (Arbre arbre)   si est_feuille (arbre) faire codage[caractere[arbre]] <- copie_de (chaîne)   sinon faire chaîne <- concaténer (chaîne ,"0") creer_codage (fils_gauche[arbre]) retirer_dernier_élément (chaîne)   chaîne <- concaténer (chaîne,"1") creer_codage (fils_droit[arbre]) retirer_dernier_élément (chaîne)   fin si retourner

---

Je te laisse le bonheur de trouver comment sauvegarder l'arbre dans le fichier compressé, puis comment le lire lors de la décompression :wink:

Citation:

---

Envoyé par kaisse

Je te laisse le bonheur de trouver comment sauvegarder l'arbre dans le fichier compressé, puis comment le lire lors de la décompression :wink:

---

Je pensais soit à faire un parcours préfixe de l'arbre en mettant devant chaque élément s'il sagit d'un noeud ou d'une feuille :arrow: on retrouve l'arbre mais cela prend une place relativement inportante dans le fichier

ou alors mettre la table des occurences dans le fichier et reconstruire l'arbre à partir de là :arrow: ce qui risque de prendre du temps

En tout cas merci bien à vous deux pour vos explications très claires

La seconde solution est utilisée
on crée un en tête contenant le codage de chaque caractère
D'où un taux de compression pouvant être supérieur à 1 pour de très petits fichiers !

Pas bête la table des occurences kael kael, il faudra que je compare avec ma méthode. Je vous la livre ici, si vous avez des critiques et/ou des comparaisons à faire elles seront bienvenues:

Pour "écrire" l'arbre:
soit je suis arrivé à une feuille -> j'écris le caractère correspondant à la feuille

sinon j'écris "(" + l'écriture de l'arbre gauche +","+ l'écriture de l'arbre droit + ")"

exemple:

Code:

---

1 2 3 4 5 6 7 8 9 10

/ \ / \ /\ / \ / \ / \ a b c /\ / \ d e   Donnerait ((a,b),(c,(d,e)))

---

Problème:
Et si je veux coder les caractères "," "(" ou ")".
Solution: à la place d'écrire les caractères, il suffit d'écrire leur codage en valeur entiére. Du coup, les cratères peuvent être codés sur 3 octets si leur codage est compris entre 100 et 255, mais au moins, il n'y a plus de confusions possibles

Petite optimisation:
On s'apercoit vite que pour des gros arbres, on va génerer pleins de parnthéses. Or si on écrit le décodeur, le "parser" de l'arbre, on se rend compte que les ")" sont inutiles. En effet chaque fois qu'on croise une "(" on sait qu'il ya deux arbres à parser, donc quand c'est fait, on reprend automatiquement ou on était avant. Je me contente juste d'en ajouter une à la fin pour simplifier. Pour l'arbre de tout à l'heure ca donnerait:
((a,b,(c,(d,e)
Ici, économie de trois aractères, en moyenne, sur un fichier de 5000 caractères utilisant les 3 quarts des caractères ASCII, ca fait environ 120 octets de gagnés: Y'a pas de petits profits :wink:

Ta méthode revient donc à faire un parcours préfixe de l'arbre :wink:

Si tu veux faire d'autres économies, tu peux éviter les virgules car (dans le cas de la compression par Huffmann) tu sais que tu n'auras pour chaque feuille qu'un seul caractère

:arrow: Et hop encore des économies :lol: