Sujet
On se propose de réaliser, par étapes successives, un logiciel de (dé)compression basé sur la technique RLE et le code de Golomb.
Le RLE
Le principe du codage RLE (Run Length Encoding) est d’obtenir à partir d’une suite de nombre supposée contenir des répétitions consécutives de mêmes valeurs, une suite contenant:
- pour toute répétition suffisamment longue, la longueur de la suite et la valeur répétée,
- pour toute répétition trop courte, la suite de valeurs sans modification.
Un tel codage nécessite en pratique d’insérer dans la suite construite des marqueurs permettant de réaliser le décodage.
Il est facile d’observer que, par une telle méthode, certaines suites sont «compressées»; la longueur de la suite après codage est plus petite que la longueur de la suite originale.
La suite aaaaabcbaaaaaabbbbbb (de longueur 20) pourraît être encodée de façon à produire la suite [RLE]5abcb[RLE]6a[RLE]6b (de longueur 12).
1. Il est demandé de réaliser dans un langage de programmation de votre choix un programme d’encodage et de décodage RLE (basé sur le principe précédent). Ce programme devra permettre d’encoder tout fichier donné en entrée et produire en sortie un fichier dont le nom sera étendu en .rl1. Ce programme devra en outre produire en sortie le taux de compression obtenu.
Ce programme pourra être paramétré de façon à permettre à l’utilisateur de choisir ce qu’il considère comme étant un caractère de la suite.
On testera ce programme sur une variété de fichiers communs: texte français, binaire, bitmap d’image, etc.
De nombreuses variantes de ce principe sont utilisées. Par exemple, si la suite considérée est une suite de bits, on peut s’intéresser aux suites de 0 consécutifs situés entre deux 1.
La suite 00000100110000000101011 peut être représentée par la suite 52071100.
2. Écrire un programme (dans le langage de votre choix) permettant de coder et décoder tout fichier considéré comme une suite de bits. Le fichier résultat sera nommé en utilisant l’extension .rl2.
3. On étudiera les relations entre cet encodage et le précédent. Du point de vue de l’encodage lui-même, de leurs performances relatives, etc.
4. On recherchera la spécification de formats courants utilisant le codage RLE. On comparera les techniques employées dans ces divers formats avec celles réalisées dans ce TP.
Le code de Golomb
En ce qui concerne le RLE du second type et précédemment décrit le problème principal est de trouver un codage adéquat pour la suite des nombres produits; i.e. comment coder la suite 52071100 ? Le code de Golomb permet de construire un codage de longueur variable permettant d’obtenir une compression raisonnablement efficace.
Code de Golombd
Pour l’entier n, Golombd(n) est construit par concaténation du codage unaire du quotient de n/d et du codage binaire tronqué du reste de n/d.
Le codage unaire d’un entier i est une suite de i 1 suivie d’un 0. Le nombre 5 se code donc 111110.
Le codage binaire tronqué de l’entier i, CBTd(i) est obtenu de la façon suivante:
- On appelle c la partie entière supérieure du logarithme en base 2 de d, i.e. le nombre de bits utiles pour écrire d en binaire (par exemple pour 5, c=3).
- si i<2c-d, i sera codé en employant c-1 bits.
- sinon i sera codé par les c derniers bits de 2c-(d-i).
Ainsi pour d=5, le codage du nombre 23 sera 11110110, car 11110 est le codage unaire de 4 (23/5=4) et 110 le codage sur 3 bits de 6 (on cherche CBT5(3), on sait que 23-(5-3)=6).
Comment déterminer une valeur adéquate pour d ? Il suffit de prendre la médiane de la suite à coder.
5 (difficile). Écrire un programme permettant de coder et décoder tout fichier considéré comme une suite de bits en utilisant le code de Golomb.
Le TP devra être rédigé (sous la forme de documents HTML) et rendu avec les codes sources des programmes; ce au plus une semaine après la séance.
