Codage de Huffman

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

Schéma général

  • Calculer/estimer la probabilité de chaque symbole (facultatif, voir section Partage de l’arbre)
  • Construire un arbre de Huffman
  • En déduire une table de compression
  • Compresser chaque symbole en une chaine de bits de longueur variable

  • Disposer de l’arbre qui a servi à compresser
  • Lire bit par bit le flot de données et descendre l’arbre
  • Chaque fois que l’on tombe sur une feuille, on émet le symbole correspondant.

En anglais, compression/décompression peut aussi se nommer deflate, inflate (dégonfler, gonfler).

Lectures et écritures tamponnées

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.

Arbre de Huffman

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;
}

Debogage

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.

Canonisation

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).

Partage de l’arbre

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.

Partage à priori

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).

Partage explicite

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.

Construction adaptative

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.

Encodage de l’arbre

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 :

Stockage des probabilités

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.

  • Avantage : simplicité de mise en œuvre ; même code des deux côtés (make_huffman_tree).
  • Inconvénient : on stocke également toutes les valeurs non présentes ; il convient de faire particulièrement attention aux arrondis.
  • Espace nécessaire : \(8 bits*256 symboles\).
Encodage absolu des feuilles

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).

  • Avantage : Algorithme de serialization très simple à écrire ; on ne stocke que les symboles présents.
  • Inconvénient: Algorithme de reconstruction délicat. On gagne rarement de l’espace sur la méthode précédente.
  • Espace nécessaire : \(log_2{profondeur}*n + 4 bits\) (\(n\), nombre de symboles. Les 4 bits servent à stocker la nombre de bits sur lesquels sont codés les profondeurs).
  • Exercice : Reconstruire sur un papier l’arbre suivant: (2,S) (4,d) (5,c) (5,b) (5,w) (5,s) (4,o) (5,y) (5,x) (4,m) (3,t) (4,a) (5,l) (6,n) (6,h) (3,e)
Encodage relatif des feuilles

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.

  • Avantages : On ne stocke que les symboles présents ; algorithme de reconstruction récursif très simple (la récursion se marie très bien avec la numérotation relative).
  • Inconvénient : Il faut pouvoir lire et écrire un bit facilement ; on ne gagne pas toujours sur la première proposition. (note, le premier point négatif est un faux problème, pour le reste de la compression/décompression, lire et écrire un bit sont nécessaires.)
  • Espace nécessaire : \(10 bits * n\) (\(n\), nombre de symboles).
  • Exercice : A partir de quelle valeur de \(n\) vaut-il mieux utiliser la première solution ?
Hybride

En vous servant des autres propositions, proposez une technique hybride cumulant un maximum d’avantages.

Stockage des longueurs du code canonique

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.

Compression (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_buffers. 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 à :

  • Associer une table de compression et un tampon à un flot (le code est donné en commentaire de compress_stream).
    • Pour chaque symbole à compresser, regarder dans la table le code qui lui est associé (le bit_buffer).
    • Écrire ce code (un appel à write_bits ; notez le pluriel).
  • Dissocier le flot (et ventiler le tampon)

Le dernier octet

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.

  • Émettre dès le début le nombre de symboles qui vont être encodés.
  • Ajouter un symbole fictif qui représente la fin (l’équivalent de EOF dans un fichier)
  • Encoder dans le dernier octet le nombre de bit de l’avant-dernier octet à écarter (discard).

Exercice : Pour chaque situation, lister les avantages et les inconvénients. Remarque : ils en ont tous un !

Décompression (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];
}
  • Racine –1–> 2 –1–> 5 –1–> 7 –0–> H
  • Racine –0–> 1 –1–> 4 –0–> e
  • Racine –1–> 2 –0–> l
  • Racine –1–> 2 –0–> l
  • Racine –1–> 2 –1–> 5 –0–> o