deflate
)inflate
)Le codage de Huffman est un algorithme de compression de données sans perte, qui utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier). Le code est déterminé à partir d’une estimation des probabilités d’apparition des symboles dans la source. Comme dans le code morse, un code court est associé aux symboles de source les plus fréquents. Si l’on connait la distribution des symboles d’un document, alors le code de Huffman est optimal pour tout document ayant cette distribution. Il existe des méthodes de compressions plus efficaces (codage arithmétique ou par dictionnaire par exemple), si l’on relâche la contrainte d’un encodage symbole par symbole. Wikipedia
Les exercices proposés dans l’énoncé du TP ne seront pas relevés. Bien entendu, vous êtes fortement encouragés à les faire et à vous poser des questions.
Compresser chaque symbole en une chaine de bits de longueur variable
En anglais, compression/décompression peut aussi se nommer deflate, inflate (dégonfler, gonfler).
L’encodage de Huffman associe un code de longueur variable à un symbole. Cependant les primitives de manipulation de fichier ne permettent pas de manipuler autre chose que des multiples d’un octet. Comment écrire seulement quelques bits ?
Comme à chaque fois en informatique, la solution consiste à rajouter une couche
d’abstraction. A chaque flot (FILE*
), nous associons un tampon (buffer).
Au lieu d’écrire directement dans le flot, les bits à écrire seront stockés
dans ce tampon. Lorsqu’il sera plein (8 bits = 1 octet), c’est la valeur du
tampon qui sera écrite dans le flot et le tampon sera remis à zéro. Pour la
lecture, nous lirons et stockerons un octet dans le tampon, et les bits à lire
seront extraits du tampon.
Cette stratégie (aux valeurs/noms près) est la solution générale du problème. A partir de maintenant, les abstractions proposées et leur noms sont spécifiques à notre implémentation.
Nous nommerons bit_buffer
le couple qui associe à une valeur (bits
), le
nombre de bits significatifs (count
) de celle-ci. (Remarque: nous
utiliserons aussi cette même abstraction pour représenter le code associé à un
symbole dans la table de compression). Les primitives de manipulation de ce
type commencent par bitbuffer_
(full
, empty
, remaining
, transfer
).
Nous associerons à un flot (compressed_stream
) son bit_buffer
(buffer
).
Pour limiter le nombre de types, nous proposons d’utiliser un seul type
(compressed_stream
) pour la lecture et l’écriture (un peu comme un FILE*
ne
précise pas si le fichier est en lecture ou en écriture). A partir de
maintenant, pour éviter de corrompre le flot, seules les fonctions travaillant
sur un compressed_stream
auront le droit de lire/écrire dans ce flot. Nous
proposons les primitives suivantes :
compress_stream
/uncompress_stream
Associe un descripteur de fichier à son bit_buffer
. Une fois cette fonction
appelée, il ne faut plus accéder directement au contenu du fichier et ce
jusqu’à l’appel de close_compressed
. (C’est l’équivalent de fopen
.)
close_compressed
Termine l’association entre un flot compressé et son bit_buffer
.
(L’équivalent de fclose
). Il est important de noter que cette fonction aura
aussi pour tâche de ventiler (flush
) les tampons en attentes.
write_bit
Écrit un bit, dans le flot compressé. Comme expliqué dans l’introduction de
ce paragraphe, cette fonction ne peut pas l’écrire directement. Son rôle est
d’ajouter ce bit dans le tampon (buffer
) associé au flot. Lorsque celui ci
est plein, son contenu sera envoyé au flot sous-jacent, et le compteur sera
réinitialisé (write_buffer
).
flush_compressed
Cette fonction sert à ventiler le tampon dans le flot sous-jacent (un peu
comme fflush
). Malheureusement son fonctionnement peut être complexe. Nous
discuterons des problèmes qu’elle soulève dans la paragraphe le dernier
octet. Dans un premier temps, nous vous proposons de ne
rien faire ou de bourrer le tampon de 1 et de l’écrire sur le disque. Remarquez
ces deux approches sont aussi mauvaises l’une que l’autre. Exercice:
Pourquoi ?
En plus des primitives, on peut proposer une version de commodité de
write_bit
, write_bits
. Elle écrirait n
bits (grosso modo, une boucle sur
write_bit
). Bien que l’on ne soit que sur un seul octet, la question
d’endianess est donc toujours d’actualité. Dans quel ordre faut il écrire les
bits ?
Pour la lecture bit par bit, le principe sera le même que pour l’écriture, mais
les opérations seront inversées. On lira un octet du flot dans le tampon. Ce
tampon sera consommé à chaque appel de read_bit
. Une fois vide, on lira
l’octet suivant.
L’encodage de Huffman utilise un arbre pour représenter les codes associés à
chaque symbole. Le chemin de la racine à une feuille, en posant fils gauche 0
et fils droit 1
, donne le code. Le rang d’une feuille donne le nombre de bits
utilisés pour ce code. Par construction, cet arbre est un arbre binaire
localement complet (i.e., où tous les nœuds ont soit 2, soit 0 enfants).
Pourquoi, doit-il avoir ces propriétés ?
Il existe plusieurs méthodes de constructions. Les plus efficaces reposent sur l’utilisation de tas binaires pour maintenir des listes de priorités (\(n\log{n}\)). Pour simplifier le TP, nous ferons des recherches de minimum dans un tableau (\(n^2\)). Le principe de l’algorithme demeure inchangé.
On associe à chaque symbole son nombre d’occurrence dans un arbre, constitué d’une seule feuille. L’ensemble de ces arbres/feuilles forme une forêt, i.e., un ensemble d’arbres.
digraph {
A [shape=record, label="{a|3}"];
F [shape=record, label="{f|1}"];
G [shape=record, label="{g|1}"];
H [shape=record, label="{h|2}"];
}
Itérativement, on remplace les deux nœuds avec la plus faible occurrence, par un nouvel arbre. La racine (le nouveau nœud), a pour enfant les deux nœuds remplacés, et pour valeur la somme des occurrences de ses deux fils direct.
digraph {
A [shape=record, label="{a|3}"];
H [shape=record, label="{h|2}"];
F [shape=record, label="{f|1}"];
G [shape=record, label="{g|1}"];
1 [label="2"];
1 -> F; 1 -> G;
}
digraph {
A [shape=record, label="{a|3}"];
H [shape=record, label="{h|2}"];
F [shape=record, label="{f|1}"];
G [shape=record, label="{g|1}"];
1 [label="2"];
2 [label="4"];
1 -> F; 1 -> G;
2 -> 1; 2 -> H;
}
Quand il ne reste plus qu’un nœud, il est la racine de l’arbre cherché.
digraph {
A [shape=record, label="{a|3}"];
H [shape=record, label="{h|2}"];
F [shape=record, label="{f|1}"];
G [shape=record, label="{g|1}"];
1 [label="2"];
2 [label="4"];
3 [label="7"];
1 -> F; 1 -> G;
2 -> 1; 2 -> H;
3 -> 2; 3 -> A;
}
Pour visualiser (et déboguer) l’arbre que vous aurez construit, vous pouvez
vous servir de la fonction print_tree_to_dot
, fournie. Elle produit une
représentation compatible avec langage de description de graphe DOT
proposé
par librairie Graphviz. Parmi tous les visualisateurs
proposés, vous pouvez tester WebGraphviz qui est
en ligne.
Durant la construction de l’arbre, nous sommes confrontés à des choix. De deux nœuds, lequel va à gauche et lequel à droite ? Parmi plusieurs ex æquo, lequel choisir ?
Peu importent les choix, les us et coutumes, etc, il faut que l’encodeur et le décodeur utilisent le même arbre ! La section suivante discute plus longuement du problème du partage.
Il existe une forme canonique de l’arbre de Huffman. Elle peut être obtenue par construction (beaucoup plus simple avec des files de priorités/tas binaire) ou par canonisation des codes choisis pour chaque symbole (i.e., directement sur la table de compression).
Il est nécessaire de disposer du même arbre entre le compresseur et le décompresseur. En toute généralité, il existe trois manière de le partager.
On suppose que les deux parties connaissent le même arbre à priori. On peut imaginer construire un couple compresseur/décompresseur spécialisé pour une langue (ou un type de document).
Le compresseur calcule la distribution des symboles et construit un arbre dédié. On obtient une table de compression parfaitement adaptée au document, mais il faut transférer entre le compresseur et le décompresseur cet arbre. Les statistiques elles mêmes ne sont pas nécessaires, seule la forme de l’arbre est importante.
Les deux parties démarrent avec un arbre générique (par exemple équiprobable). Durant la compression, l’arbre est spécialisé (modifié) pour s’adapter aux symboles rencontrés. De son côté, le décompresseur doit appliquer les mêmes règles. En plus de ne pas nécessiter de partage d’arbre, cette méthode, s’adapte aux évolutions du flot de données. Elle est donc naturellement plus adapté à la compression d’un flux.
En cas de partage explicite de l’arbre, il devient nécessaire de le stocker
sous une forme exploitable et partageable (serialization
ou mashalling
).
Nous vous proposons quelques alternatives :
On stocke successivement toutes les valeurs de l’histogramme. Au lieu de stocker le occurrences sur un entier on peut les ramener (produit en croix) à un octet. Du côté du décompresseur on reconstruit l’arbre en utilisant le même algorithme que lors de la compression.
make_huffman_tree
).On effectue un parcours en profondeur de l’arbre. Dès que l’on arrive sur une feuille (pré-ordre), on stocke le couple (profondeur, valeur du symbole). En connaissant la profondeur maximale d’une feuille, on peut limiter le nombre de bits sur lesquels on stocke la profondeur (\(log_2{profondeur}\)). Si l’on met de côté le cas pathologique d’un document ne contenant qu’un seul symbole, on peut stocker la profondeur - 1. Sans être très compliqué, l’algorithme de reconstruction est légèrement plus délicat. On insère dans un arbre vide (ou une racine pour simplifier le code) les valeurs des symboles à leur profondeur en préférant systématiquement la branche gauche. Pour éviter de nombreux parcours inutiles (i.e., qui augmenteraient la complexité en temps d’un ordre de grandeur), il convient de marquer les nœuds saturés (i.e., qui ont déjà deux fils).
serialization
très simple à écrire ; on ne stocke
que les symboles présents.Lors d’un parcours en profondeur, pour chaque nœud interne on émet un 0 (sur 1 seul bit), et pour une feuille un 1 (sur un seul bit) suivi de la valeur de la feuille (sur 8 bits). L’algorithme de reconstruction est très simple, bien que récursif. On lit un bit : si c’est un zéro on crée un nœud interne, si c’est un 1, une feuille avec pour symbole les 8 bits suivants.
En vous servant des autres propositions, proposez une technique hybride cumulant un maximum d’avantages.
Si l’on dispose d’un code canonique, on peut se limiter à stocker la longueur du code associé à chaque lettre. Cela revient à stocker les positions absolues des feuilles (i.e., leur profondeur). Si l’on connait la profondeur max de l’arbre, on peut limiter le nombre de bits utilisés ici.
deflate
)Au bout des branches de notre arbre se situent les symboles. Le chemin depuis
la racine donne le code associé (0 si on descend vers le fils gauche, 1 pour le
droit). Cette représentation, adaptée à la décompression, n’est clairement pas
adaptée à la compression. En effet pour compresser nous connaissons le symbole
et non le chemin. Il nous faut donc l’association inverse (symbole -> chemin).
Nous appellerons cette association table de compression. Pour la construire, il
suffit de parcourir l’arbre (peu importe comment mais un parcours en profondeur
semble simple et très adapté), et de stocker dans une table, à l’indice du
symbole, le chemin. Ce chemin peut être représenté par une chaine de bits,
i.e., un nombre, de n
bits. Pour des raisons évidentes nous stockerons ce
nombre sur un octet. Dès lors, comment savoir combien de bits sont
significatifs ? Nous utiliserons à nouveau les bit_buffer
s. Pour déboguer
votre table de compression, vous pouvez utiliser la fonction fournie
print_compress_table
.
Maintenant que toutes les pièces ont été expliquées, la compression est relativement directe (straightforward). Elle se limite à :
compress_stream
).
bit_buffer
).write_bits
; notez le pluriel).Comme chaque symbole est associé à un code de longueur variable, rien ne garantit que le message à compresser, soit un multiple d’un octet (8 bits). Malheureusement, nous devons écrire 8 bits. Si l’on complète bêtement par des zéros ou des uns (peu importe), il n’est pas impossible, voire probable, que cela corresponde à un code valide, donc un symbole. Avec cet encodage toute valeur de bourrage (padding), est voué à l’échec.
En fonction des utilisations, on peut proposer diverses solutions.
EOF
dans
un fichier)Exercice : Pour chaque situation, lister les avantages et les inconvénients. Remarque : ils en ont tous un !
inflate
)Supposons que nous disposions de l’arbre qui a servi à compresser et d’un moyen
de lire bit par bit (cf. Lectures et écritures
tamponnées). Décompresser un symbole en
fonction d’une chaine de bits, correspond à descendre dans l’arbre en suivant,
soit le fils gauche (0
), soit le fils droit (1
). Dès que l’on arrive sur une
feuille, on retourne le symbole. On peut remarquer que les probabilités n’ont
plus aucune importance à ce niveau, seule la forme de l’arbre compte.
Exemple 1110 010 10 10 110
avec :
digraph {
graph [ranksep=0];
"0x7ff570402db0" [label="Racine"];
"0x7ff570402d70" [label="1"];
"0x7ff570402cf0" [label="3"];
"0x7ff570402c90" [shape=record, label="{r|1}"];
"0x7ff570402bd0" [shape=record, label="{space|1}"];
"0x7ff570402d30" [label="4"];
"0x7ff570402c30" [shape=record, label="{e|1}"];
"0x7ff570402cd0" [label="6"];
"0x7ff570400640" [shape=record, label="{0xa|1}"];
"0x7ff570402cb0" [shape=record, label="{w|1}"];
"0x7ff570402d90" [label="2"];
"0x7ff570402c50" [shape=record, label="{l|3}"];
"0x7ff570402d50" [label="5"];
"0x7ff570402c70" [shape=record, label="{o|2}"];
"0x7ff570402d10" [label="7"];
"0x7ff570402bf0" [shape=record, label="{H|1}"];
"0x7ff570402c10" [shape=record, label="{d|1}"];
"0x7ff570402db0" -> "0x7ff570402d70" [label=0];
"0x7ff570402db0" -> "0x7ff570402d90" [label=1];
"0x7ff570402d70" -> "0x7ff570402cf0" [label=0];
"0x7ff570402d70" -> "0x7ff570402d30" [label=1];
"0x7ff570402cf0" -> "0x7ff570402c90" [label=0];
"0x7ff570402cf0" -> "0x7ff570402bd0" [label=1];
"0x7ff570402d30" -> "0x7ff570402c30" [label=0];
"0x7ff570402d30" -> "0x7ff570402cd0" [label=1];
"0x7ff570402cd0" -> "0x7ff570400640" [label=0];
"0x7ff570402cd0" -> "0x7ff570402cb0" [label=1];
"0x7ff570402d90" -> "0x7ff570402c50" [label=0];
"0x7ff570402d90" -> "0x7ff570402d50" [label=1];
"0x7ff570402d50" -> "0x7ff570402c70" [label=0];
"0x7ff570402d50" -> "0x7ff570402d10" [label=1];
"0x7ff570402d10" -> "0x7ff570402bf0" [label=0];
"0x7ff570402d10" -> "0x7ff570402c10" [label=1];
}
1
–> 2 –1
–> 5 –1
–> 7 –0
–> H
0
–> 1 –1
–> 4 –0
–> e
1
–> 2 –0
–> l
1
–> 2 –0
–> l
1
–> 2 –1
–> 5 –0
–> o