INF 441 - TD 8
Flots de données (streams) et compression de fichiers

Votre opinion sur le cours de ce matin : Votre opinion sur le TD de la semaine dernière :

Le but de ce TD est d'illustrer l'utilisation des flots de données dans le cadre de la compression de fichiers en écrivant un outil qui effectue cette tâche sans charger l'intégralité du fichier en mémoire. Ce TD est réalisé en OCaml. Décompresser le fichier td8.zip à la racine de votre projet et configurez-le pour que le binaire produit soit Test.native.

Préambule

Le module Lazy de la distribution standard d'OCaml offre la syntaxe lazy (e) qui définit la suspension du calcul de l'expression e. On utilise ce trait du langage pour réaliser le module MyStream qui est fourni et implémente le type des flots c'est-à-dire 'a MyStream.t .

Les valeurs de type int sont appelées entiers OCaml. Un flot d'entiers est donc une valeur de type int MyStream.t.

On note bitsize nombre de bits utilisés pour représenter une valeur de type int sur l'architecture ambiante (31 ou 63 bits selon que l'architecture de votre machine, le « bit perdu » étant réservé à l'usage du ramasse-miettes d'OCaml).

Soit kbitsize. Un entier k-bits est un entier OCaml compris entre 0 inclus et 2^k exclus. Par exemple, un entier OCaml 8-bits est compris entre 0 et 255. Les entiers 8-bits sont appelés octets.

Les bits seront représentés par le type bool du langage OCaml. Un flot de bits est donc une valeur de type bool MyStream.t.

On fournit également :

Compression/Décompression

Un texte est ici compris comme un flot de caractères ASCII que l'on appellera aussi symboles. On donne le module Huffman qui permet

Le codage d'un flot de symboles se fait en « remplaçant » chaque symbole par une suite de bits déterminée par le le dictionnaire de codage. Le codage transforme donc un flot de symboles en un flot de bits. Par exemple si le dictionnaire de codage indique 'a'0 et 'b'1 alors la forme codée du texte ab est le flot de bits 01.
Écrire la fonction encode du module Zipper.

Le décodage est l'opération inverse. Il transforme donc un flot de bits (produit par le codage) en un flot de symboles.

Pour compresser un fichier filename et obtenir un fichier filename.zz, il faut donc:

  1. Créer un flot d'octets à partir du contenu du fichier original (cf. LazyIO)
  2. Créer les dictionnaires de codage/décodage associés au texte (cf. Huffman)
  3. Coder le texte (cf. la fonction encode à écrire dans le module Zipper)
  4. Ajouter en préambule du texte codé la longueur du texte original (cf. Pack)
  5. Convertir le flot binaire ainsi obtenu en flot d'octets (cf. ByteStream)
  6. Ajouter le dictionnaire de décodage en préambule du flot d'octets ainsi obtenu (cf. Huffman)
  7. Écrire le flot d'octets ainsi obtenu dans le fichier filename.zz (cf. LazyIO)

Chacune des opérations de la procédure précédente est « réversible » ce qui permet de décompresser, c'est-à-dire reconstruire le fichier original à partir du fichier compressé.

À l'aide de ces indications, écrire le module Zipper.

Votre compresseur travaille-t-il en espace O(1)?

Déposer les fichiers Zipper.mli et Zipper.ml .

L'heure de vérité (où l'on constate qu'il y a un problème)

Afin de tester le module Zipper, on va passer quelques œuvres littéraires « à la moulinette » : on fournit les fichiers Les Misérables, Notre-Dame de Paris, et Ulysses, qui contiennent les textes (avec quelques indications de formatage) de romans écrits par Victor Hugo et James Joyce.

On évalue maintenant les performances de notre outil en comparant alors la taille des fichiers compressés avec celle des fichier originaux.
Horreur : notre « compresseur » semble bien être un « expanseur »

Flots d'entiers et flots binaires : la source du problème

L'effet d'expansion constaté dans la section précédente vient de la naïveté de l'implémentation du module ByteStream. En effet, la fonction ByteStream.from_bits encode chaque booléen par un octet (0 ou 1). Les données compressées étant représentées en machine par un flot de bits, la taille du fichier compressé (en octets) est (asymptotiquement) égale à la longueur de ce flot

Il serait beaucoup plus efficace de considérer des « paquets » de 8 bits pour former des octets. La taille du fichier compressé (en octets) serait alors (asymptotiquement) égale au huitième de la longueur du flot de bits qui représente les données compressées.

On fournit le module Pack qui permet de convertir un k-bits en flot binaire (sorte de « push ») et inversement (sorte de « pop »). À l'aide de ce module, réécrire le module ByteStream.

Déposer les fichiers ByteStream.mli et ByteStream.ml .

L'heure de vérité (où l'on espère avoir résolu le problème)

Afin de tester notre nouvelle implémentation du module ByteStream, on refait les tests de la première « heure de vérité ».

Ouf : cette fois ça va mieux

Une solution : solution.zip