include "../head.html";
?>
Compression -- Projet Facultatif 2018
Compresseur "à la gzip"
Langages recommandés : Java ou Python. Demandez-moi avant si vous souhaitez
utiliser un autre langage de programmation.
Objectifs : le but du projet est d'écrire un compresseur / décompresseur inspiré du
mode de fonctionnement de gzip et avec des fonctionalités pour être efficace sur des textes écrits
en français.
Date et mode de rendu : Par mail à cyril.nicaud@u-pem.fr, avec comme titre [M1] Projet Compression. Le mail doit contenir un seul attachement compressé au format .zip ou .gz, qui correspond à un dossier portant votre nom et contenant vos sources ainsi qu'un fichier pdf expliquant comment utiliser le programme. Le document pdf doit également expliciter en au plus 2 page le travail réalisé. La date butoire est le ?? février 2018 à minuit.
Notation : j'ajoute entre 0 et 3 points à la note de l'examen, selon la qualité du projet.
Format utilisé :
- Le texte à compresser est découpés en blocs. Chaque bloc est compressé indépendamment. Il n'y a pas
de contraintes de format sur comment sont choisis les blocs, à vous d'en décider (ils servent à ce que
les calculs tiennent en mémoire, que le temps ne soit pas trop long, ...)
- Chaque bloc est constitué d'une en-tête de 3 bits : 1 bit qui vaut 1 si c'est le dernier bloc et 0 sinon.
Deux bits pour coder :
- 00 pour dire que le texte du bloc n'est pas compressé
- 01 pour dire que le texte du bloc est compressé avec l'algorithme standard (cf ci-dessous)
- 10 et 11 laissés libres pour vos optimisations sur les textes en français
- Si le bloc est de type 00 (non compressé), les deux octets suivants indiquent la longueur du bloc, puis le
message est mis en clair. L'entête utilise donc 1+2+2*8 = 19 bits.
- Si le bloc est de type 01 (standard), on commence par y ajouter le codage des deux arbres de Huffman, puis
le texte compressé. Il y a un symbole virtuel spécial ajouté pour savoir quand le bloc se termine.
- Si le bloc est de type 10 ou 11, c'est à vous de décider du format qui suit. Assurez-vous qu'on sache quand le
bloc se termine.
Bloc standard 01
- Un bloc standard est compressé avec l'algorithme de type LZSS, avec une longueur max de 258 (la longueur est donc entre 3 et 258) et un buffer de taille 32k. La taille
minimale pour émettre un couple est fixée à s=3.
- Les symboles émis sont donc soit un des 256 caractères ASCII, soit un couple (longueur,position).
- Contrairement à LZSS standard, on n'utilise pas un bit pour distinguer les caractères des couples, ce sera fait automatiquement
via l'utilisation d'arbres de Huffman : on regroupe dans un premier arbres les symboles, les longueurs, et un nouveau caractère de fin
de bloc. Dans un autre arbre de Huffman, on regroupe les positions utilisées.
- Pour le premier arbre de Huffman, on a donc un alphabet qui peut contenir jusqu'à 513 symboles :
- les symboles 0-255 pour les caractères ASCII,
- le symbole 256 qui encode la fin du bloc,
- les symboles 257-512 pour les longueurs l (l=3 => 257, l=4 => 258, ... l=258 => 512)
Bien entendu, on n'utilise que les symboles utiles dans la compression du bloc.
- Le deuxième arbre de Huffman encode les positions. Il y en a 32k différentes, mais a priori elles ne seront pas toutes utilisées.
Remarque : en TP je vous montrerai l'algorithme utilisé dans gzip pour trouver le plus long préfixe du buffer présent dans la fenêtre.
Vous n'êtes pas obligés d'utiliser cette méthode, mais c'est conseillé.
Blocs spécifiques 10 et 11 :
Là vous êtes libres. Vous n'êtes pas obligés d'utiliser les deux codes 10 et 11. Vous pouvez implanter le(s) méthode(s) de votre choix pour
compresser plus efficacement des textes en français.
gzip : gzip implémente le format DEFLATE, qui ressemble à celui du projet, mais en un peu plus compliqué/technique. Si vous voulez voir
à quoi cela ressemble, c'est ICI. Notamment, les arbres de Huffman sont encodés différemment.