Nous continuons les manipulations de listes, et apprenons à utiliser des modules.

Le sujet porte sur un algorithme de compression sans perte, utilisé notamment pour les encoder les images au format GIF. Il porte le nom de ses trois inventeurs. vous trouverez toutes les informations inutiles ici.

Ce TP est un peu plus conséquent que les précédents, nous allons donc créer un projet en plusieurs fichiers. commencez par créer un répertoire dédié à vos programmes Caml, si vous n'en avez pas encore. Créez un fichier texte de nom _tags, contenant uniquement le texte suivant:

puis créez un sous-répertoire Lzw, dans lequel vous mettrez les fichiers Ocaml pour ce TP.

Ensuite, récupérez les fichiers suivants, que vous placerez dans Lzw :

• trie.ml
• trie.mli
• stream_lzw.ml
• stream_lzw.mli
• binary.mli

Les modules Trie et Stream_lzw vous sont fournis gratuitement, vous n'avez pas à modifier ces fichiers. L'interface de Binary est fournie mais vous en écrirez l'implémentation. Vous aurez aussi à écrire l'implémentation et l'interface du module principal Lzw.

Encodage en binaire

Le module Binary défini le type des bits:

et les opérations de conversion entre int, listes de bits, et code ascii. Un code ascii est un entier entre 0 et 255 . Les encodages d'entiers par des listes de bits seront de type little-endian, c'est-à-dire avec bit de poids faible en tête.

Question 1

Implémenter int_of_bit_list convertissant une liste de bits en entiers. Puis son inverse bit_list_of_int convertissant un entier en liste de bits. Remarquez que la deuxième fonction prend en argument la longueur de l'encodage : la liste retournée par bit_list_of_int doit impérativement avoir cette longueur.

Question 2

Le module List propose une fonction List.flatten très pratique, qui transforme une liste de listes en liste simple. Nous avons besoin d'une fonction inverse, qui prenant une liste, regroupe les éléments par blocs de $n$ (pour $n = 8$, ce seront nos octets), et renvoie la liste de ces blocs. Commencez par implémenter la fonction suivante, dont le comportement est illustré :

cut transvase donc un certain nombre d'éléments de la deuxième vers la première liste.

En déduire une fonction unflatten, dont le comportement est:

Question 3

Implémentez maintenant les fonctions suivantes :

Pour ascii_of_bit_list, vous commencez par ajouter 7 bits O en fin de la liste à convertir, puis utilisez unflatten et List.map.

À l'issue de cette question, vous devriez pouvoir compiler votre fichier en un fichier objet d'extension .cmo. Pour cela, placez-vous dans le répertoire où se trouve le fichier tags, et lancer la commande:

S'il ne répond pas qu'il y a une erreur, un fichier _build/Lzw/binary.cmo devrait être apparu.

Profitez-en pour compiler les deux autres modules, en lançant :

Compression

Créez maintenant un fichier lzw.ml dans le sous-répertoire Lzw. Pour pouvoir utiliser les autres modules sous le toplevel, entrez et exécutez les directives suivantes:

Le principe de compression LZW est le suivant : en tout temps on garde un dictionnaire de listes de bits, contenant au moins [O] et [I]. À chaque liste du dictionnaire est associé un entier unique, qui est en fait le code compressé de cette liste de bits.

Une itération de l'algorithme consiste à lire la plus longue séquence de bits (préfixe) dans le fichier à compresser, telle que cette liste apparaisse dans le dictionnaire. Notons cette liste $l$. On retire $l$ du fichier, et on émet le code associé à $l$. Ensuite, on modifie le dictionnaire : soit $b$ le prochain bit du fichier. On ajoute au dictionnaire la liste $l @ [b]$, en lui attribuant un nouveau code. Puis on recommence jusqu'à ce que le fichier soit entièrement converti.

Prenons un exemple, notre dictionnaire est :

et notre fichier commence par [I;O;I;O;O;I;I;I;O;O;...]. Le plus long préfixe du fichier apparaissant dans le dictionnaire est [I;O;I], de code $4$. Le bit suivant est O. On émet donc un $4$, puis on ajoute la liste [I;O;I;O] au dictionnaire avec un nouveau code, le $8$. Puis on recommence avec ce nouveau dictionnaire et le rest du fichier : [O;O;I;I;I;O;O;...]. Le prochain code émit sera donc le $6$, etc.

Question 4

Le module Trie fournit une structure de dictionnaire de listes. Prenez connaissance de son interface. C'est un module paramêtré par un type ordonné (tout comme Map et Set dans la librairie standard). Définissez un module pour les dictionnaires de listes de bits.

Question 5

Créez un type compr_context qui contiendra le dictionnaire, et le plus petit code non-encore attribué dans le dictionnaire. Créez une valeur initiale pour ce type, telle que le dictionnaire contienne les listes de longueur 1 . Puis ajouter une fonction qui ajoute une nouvelle liste dans le dictionnaire.

Question 6

Implémenter l'algorithme de compression LZW, de type :

compression est une fonction récursive. Ses arguments sont :

• le contexte de compression, qui contient le dictionnaire,
• la liste des codes déjà émis,
• la liste des bits à compresser.

Question 7

Il faut maintenant convertir la liste d'entiers en liste de bits. La méthode que nous utilisons est peu efficace, mais facile à implémenter :

1. calculez le nombre de bits $b$ nécessaire pour coder le plus grand entier de la liste,
2. utilisez le module Binary pour encoder tous les entiers avec ce nombre de bits,
3. concaténez les bits obtenus, puis utilisez Binary pour obtenir une liste d'entiers entre 0 et 255 ,
4. écrivez sur la sortie standard le nombre total de bits encodés (utilisez output_binary_int),
5. écrivez sur la sortie standard le nombre de bits $b$ de l'encodage (utilisez output_byte),
6. écrivez sur la sortie standard la liste des entiers entre 0 et 255 , (utilisez output_byte).

En suivant cette méthode, écrire une fonction générale :

qui lit un fichier sur l'entrée standard, le compresse, et écrit son code en sortie standard.

Décompression

Il nous faut maintenant donner un algorithme pour retrouver le fichier original depuis le fichier compressé. Le principe est étrangement similaire à l'algorithme de compression. Cette fois-ci, on nous donne une liste d'entiers et on doit retrouver une liste de bits.

Nous allons encore utiliser un dictionnaire, mais cette fois il associe à chaque code une liste de bits. Initialement, le dictionnaire ne connait que les codes $0$ et $1$, auxquels sont associés [O] et [I] respectivement. Une itération va correspondre à la procédure suivante :

1. on lit le premier entier $n$ de la liste,
2. si tout se passe bien, $n$ est dans le dictionnaire, on émet les bits de la liste $l$ associée à $n$ dans le dictionnaire.
3. On efface $n$ et on lit l'entier suivant $p$.
4. On définit $b$ ainsi :
   1. si $p$ est dans le dictionnaire, $b$ est le premier bit de la liste associée à $p$ dans le dictionnaire,
   2. sinon c'est le premier bit de la liste $l$.
5. On ajoute au dictionnaire le plus petit code qui n'y apparait pas encore. On lui associe la liste $l@[b]$.
6. On recommence avec le reste de la liste, en partant de $p$.

Étudions un exemple. Supposons que le dictionnaire soit le suivant :

et les prochains entiers à décompresser sont [6;8;11;3;5;...]. La liste associée à $6$ est [I;O;I], que l'on émet. Ensuite, le premier bit du code suivant dans la liste, $8$, est I, donc on ajoute le code $10$ au dictionnaire avec la liste I;O;I;I.

On lit ensuite l'entier suivant, c'est $8$, sa liste associée est [I;O;I;O], que l'on émet. L'entier suivant est $11$ qui, à ce stade, n'est pas dans le dictionnaire. On ajoute donc le plus petit code non-attribué, qui est aussi $11$ (et ce n'est pas une coïncidence), associée à la liste [I;O;I;O;I], le dernier bit étant le premier de la liste de $8$. On émet cette liste.

Puis on recommence avec $11$, etc.

Question 8

Instanciez une structure de dictionnaire d'entiers, en utilisant le module Map de la librairie standard.

Question 9

Comme à la question 4, créez un type dec_context, contenant le dictionnaire des codes et la valeur du plus petit code non-attribué. Créez une valeur initiale définissant les codes $0$ et $1$, et une fonction qui permet d'ajouter une liste à un nouveau code.

Question 10

Codez l'algorithme de décompression :

Ses arguments sont ;

• le contexte de décompression, contenant le dictionnaire,
• la liste des listes de bits émis jusque-là,
• la liste des entiers qu'il reste à lire.

Question 11

Il reste à lire l'entrée standard et la convertir en liste d'entiers, en suivant le protocole inverse de la question 7.

1. lisez sur l'entrée standard le nombre total de bits encodés (utilisez input_binary_int),
2. lisez sur l'entrée standard le nombre de bits $b$ de l'encodage (utilisez input_byte),
3. lisez sur l'entrée standard le bon nombre d'entiers-octets, (utilisez output_byte),
4. en déduire une liste de bits, en encodant chaque entier sur 8 bits,
5. utilisez le module Binary pour retrouver la liste d'entiers sur $b$ bits,
6. utilisez decompression_lzw pour retrouver le fichier original, d'abord sous forme de liste de bits, puis en utilisant Binary sous forme d'entiers entre 0 et 255 .
7. écrire le résultat sur la sortie standard. Obtenez ainsi une fonction :

Question 12

Terminer le travail en ajoutant la fonction suivante :

Compiler ensuite votre programme en vous plaçant dans le répertoire contenant le fichier _tags (n'oubliez pas de mettre en commentaire les directives du toplevel au début du fichier) :

Si votre programme est correct, vous obtenez un exécutable _build/Lzw/lzw.native ou ./lzw.native. Testez votre programme, par exemple :

Si cela fonctionne correctement, télécharger ce texte, et tentez de le compresser. Que se passe-t-il, et pourquoi ?