Projet de théorie de l'information (M1 Informatique)

Implantation de MTF / LZ78

Marie-Pierre Béal et Samuele Giraudo

Modalités

Le projet sera écrit dans le langage de votre choix et réalisé en binôme. Une archive ZIP devra être envoyée avant le 1^er décembre 2013, minuit à beal@univ-mlv.fr et giraudo@univ-mlv.fr. L'archive doit être nommée Nom1Nom2.zip où Nom1 et Nom2 sont les noms des deux membres du binôme. Celle-ci devra contenir, outre les sources, un document user.pdf au format PDF contenant une notice d'utilisation (qui explique notamment comment compiler le projet et les logiciels nécessaires à installer pour ce faire) et un document dev.pdf au format PDF décrivant l'architecture du projet ainsi que des tests éventuels. Ces documents ne seront pas nécessairement très longs.

Description

L'objectif du projet est de programmer un système de compression de fichiers en utilisant séquentiellement les algorithmes Move-To-Front (MTF) et LZ78 vus en TD.

Plus précisément, pour compresser un mot u, on commence par calculer le mot v, image par MTF de u. Ensuite, on calcule l'image de v par LZ78 pour obtenir un mot w, résultat de la compression. La décompression suit le chemin inverse.

Spécification

L'exécutable à fournir se nomme mz78. Il accepte les options suivantes :

-c : indique que l'on souhaite compresser le fichier dont le nom figure comme argument suivant. L'exécution doit produire un fichier compressé dont le nom est celui du fichier source, avec en plus l'extension .mz78. Par exemple, ./mz78 -c fichier produit la version compressée fichier.mz78 de fichier.

-d : indique que l'on souhaite décompresser le fichier dont le nom figure comme argument suivant. Le nom de ce fichier doit porter l'extension .mz78. L'exécution doit produire un fichier décompressé dont le nom est celui du fichier source, avec en moins l'extension .mz78. Par exemple, ./mz78 -d fichier.mz78 produit la version décompressée fichier de fichier.mz78.

Améliorations facultatives

On peut envisager les améliorations facultatives suivantes :

une option -v permettant de visualiser le trie produit par l'exécution de LZ78 sur le fichier dont le nom figure comme argument suivant. Le moyen de visualisation n'est pas imposé (ce peut être la sortie standard, une fenêtre graphique, ou encore un fichier image).

L'implantation d'un moyen de contrôler l'éventuelle non-compression d'un fichier (selon le procédé vu en TD).

La mise en place d'autres algorithmes de compression dans le processus de compression, en plus de MTF et de LZ78.