Discussion :

[kael kael]

Bonjour

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

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

[GoldenEye]

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.

[kaisse]

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 :

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

1
2
3
4
5
Arbre a
carac[a]
frequence[a]
fils_gauche[a]
fils_droit[a]

Définition une fonction

Code :

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

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 :

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

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 :

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

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

[kael kael]

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

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 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à ce qui risque de prendre du temps

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

[GoldenEye]

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 !

[kaisse]

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 :

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

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

[kael kael]

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

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

Et hop encore des économies