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.
uncompress_stream
, modifier close_compressed
et flush_compressed
read_bit
et sa version utilitaire read_bits
.write_tree
et read_tree
.EOS
(cf. précedent). Pour cela il nous faudra patcher
modifier la table de compression et l’arbre de décompression.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.
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 !
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.
find_right_most_leaf
qui retourne cette feuille.rank
qui retourne la profondeur d’un arbre (l’algorithme
est donné dans le prototype)add_eos
qui rajoute à un arbre le symbole EOS
, vous est
fournie.patch_compress_table
, qui transforme le code du symbole le
moins fréquent et rajoute le code pour EOS
, vous est fournie aussi.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.
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.
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.
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