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 k ≤ bitsize. 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 :

• le module LazyIO qui permet de lire/d'écrire un flot d'octets à partir/dans un fichier dont on donne le nom, et de tester l'égalité des contenus de deux fichiers.
• le module ByteStream qui permet de transformer un flot d'entiers en flot de bits et inversement. On suppose uniquement la préservation des flots de bits c'est-à-dire que bs et to_bits (from_bits bs) sont « égaux » pour un flot de bits bs.

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

• de créer les dictionnaires de codage et de décodage liés à un texte,
• (étant donné un dictionnaire de codage) de coder un symbole sous forme d'un flots de bits,
• (étant donné un dictionnaire de décodage) de décoder (le début d')un flot de bits pour obtenir un symbole ainsi que le reste du flot,
• d'ajouter ou retirer un dictionnaire de décodage en préambule d'un flot d'octets.

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)

• Si vous travaillez sous Eclipse, enregistrez ces fichiers textuels à la racine de votre projet, ou dans le sous-répertoire novels. Si vous ne travaillez pas sous Eclipse, ils doivent être placés dans le répertoire contenant les exécutables que vous produisez (ou dans le sous-répertoire novels).
• Exécuter le fichier Test.ml. Des fichiers portant l'extension .zz sont créés en compressant les copies. Chacun d'eux est alors décompressé et le resultat stocké dans la copie initiale, le contenu de cette dernière est donc écrasé.
• Comparer les copies aux originaux. Si tout s'est bien passé, ils doivent être identiques.

• 3Mo→14Mo pour « Les Misérables »
• 1,1Mo→4,9Mo pour « Notre-Dame de Paris »
• 1,6Mo→7Mo pour « Ulysses »

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é ».

• 3Mo→1,8Mo pour « Les Misérables »
• 1,1Mo→618Ko pour « Notre-Dame de Paris »
• 1,6Mo→902Ko pour « Ulysses »

Une solution : solution.zip