Codage de Huffman

Vous pouvez répondre/faire les fonctions dans n’importe quel ordre. Il faut bien les écrire, j’ai donc choisi mon ordre préféré.

Afin d’avoir un compresseur/décompresseur fonctionnel, il nous reste quelques problèmes à régler.

  • Rajouter les fonctions relatives à l’ouverture du stream compressé, uncompress_stream, modifier close_compressed et flush_compressed
  • Terminer la couche bas niveau de lecture bit-à-bit Écrire la fonction read_bit et sa version utilitaire read_bits.
  • Décompresser un symbole. Un algorithme est expliqué dans le texte du TP précédent
  • Transférer l’arbre entre les couple compresseur/décompresseur. Nous proposons d’utiliser l’encodage relatif des feuilles. Écrire les fonctions write_tree et read_tree.
  • Gérer la fin du flot. Nous avons choisis d’ajouter un symbole de fin de flot EOS (cf. précedent). Pour cela il nous faudra patcher modifier la table de compression et l’arbre de décompression.
  • Gérer proprement les erreurs. Refaire une passe sur nos fonctions afin de les rendre robustes aux erreurs de flot corrompus

Une partie du travail est déjà faite. Une implémentation par “défaut” est proposé pour chaque fonction, afin de vous permettre de les réaliser et tester les votre dans l’ordre de votre choix.

Question de CC

Implémenter la fonction hist_stream, qui compte les occurrences de chaque caractères du flot stream.

Rajouter votre fonction write_bits, si vous l’avez faite. Sinon ne pas le faire !

Le dernier octet

Afin de rajouter artificiellement (lire, de force) le symbole EOS, une valeur hors de l’alphabet (ici nous avons choisis 257 plutôt que -1, pour simplifier un peu plus tard). Il nous faut transformer la feuille la moins fréquente en un nœud intermédiaire qui contiendra ce symbole + EOS. Par construction, nous proposons de la mettre toujours a l’extrême droite (sic). Pour que ça soit le cas, il nous faudra placer l’arbre le plus profond a droite pour chaque nouveau nœud, donc connaitre la profondeur d’un arbre.

  • Écrire la fonction find_right_most_leaf qui retourne cette feuille.
  • Écrire la fonction rank qui retourne la profondeur d’un arbre (l’algorithme est donné dans le prototype)
  • La fonction add_eos qui rajoute à un arbre le symbole EOS, vous est fournie.
  • La fonction patch_compress_table, qui transforme le code du symbole le moins fréquent et rajoute le code pour EOS, vous est fournie aussi.

La décompression

L’algorithme de décompression vous est donné par le TD précédent. Écrire la fonction decompress_byte qui étant donné une fonction read_bit et un arbre, retourne un caractère. Remarque : le EOS est présent dans l’arbre, il suffit de le retourner comme un symbole normal.

On se propose de faire la version utilitaire, read_compressed qui, a l’instar de la fonction fread, lira dans un tableau len caractères si possible.

Des versions améliorés (lire, à faire beaucoup plus tard) gèreront les erreurs.

Partage de l’arbre

Pour partager l’arbre entre l’encodeur et le décodeur, nous avons choisi d’utiliser un [encodage relatif][encodage] des feuilles de l’arbre de Huffman.

Écrire la fonction write_tree dont l’algorithme, 1 pour une feuille suivi de la valeur du symbole. Écrire 0, puis récursivement le sous-arbre gauche, puis droit.

Écrire les fonctions read_leaf, qui associe, la valeur d’un symbole à un nœud, et read_node, qui lit un nœud.

La couche bas niveau

Il nous faut rajouter les fonctions de lectures bit-à-bit, les fonctions d’écritures vous sont fournies.

Rajouter la fonction read_bit qui lit un bit depuis le tampon interne du flot et le réapprovisionne si ce n’est pas possible.

Écrire la fonction read_bits qui lit n bits (par appel successif à read_bit) en big-endian.

En résumé

Manipulation d’arbre : - find_right_most_leaf - rank - decompress_byte

Manipulation de flot : - hist_stream - read_bits - read_decompressed - read_bit (plus complexe à cause des erreurs)

Écriture de l’arbre : - write_tree - read_tree