Introduction

Ce TP, et le TP suivant, sont sur le même format que le TP noté.

Les fichiers nécessaires à la résolution des questions se trouvent ici.

Voici le rendu attendu pour chacune des questions:

Q1	Un fichier .c
Q2		Le résultat de la décompression des 4 fichiers
Q3	Un fichier .c	Le résultat de la compression du fichier image.xpm
Q4	Un fichier .c	Le résultat de la compression du fichier image.xpm
Q5	Un fichier .c	Le résultat de la décompression du fichier gros.lzj
Q6	Un fichier .c	Le résultat de la compression du fichier ann
Q7		Un fichier .txt répondant à la question

Pour avoir une note correcte, il est attendu a minima une réponse aux question 1,2,3 et 7.

Le travail doit être effectué seul. Il est possible de récupérer des fichiers venant des TPs précédents. L'usage d'internet est restreint à l'accès aux pages concernant le cours.

Tout non-respect des consignes sera sanctionné. En particulier, si le travail n'a pas été effectué seul, une pénalité d'un minimum de 20 points sera appliquée.

TP

Le but du TP est d'écrire un décompresseur (puis un compresseur rudimentaire) pour un format de compression inspiré de LZSS. Il est très simplifié, et perd un peu en compression par rapport à une variante un peu plus intelligente.

Le résultat du compresseur est constitué de deux types d'entités différentes:

• des caractères, qu'il faut recopier littéralement
• des paires (i, j) qui signifient qu'il faut recopier ce qui se situe i caractères auparavant pendant j caractères
  Par exemple, la chaine de caractères ababdaba peut être compressée en

  ab(2,2)daba
  

  ou encore

  ab(2,2)d(3,2)a
  

  ou encore

  ab(2,2)d(5,3)
  

  ou encore

  ababd(5,3)
  

  etc.

Le résultat de l'algorithme est codé dans un fichier de la façon suivante:

• Un caractère est codé sur 9 bits: On écrit d'abord le bit 1, puis le caractère (sur 8 bits)
• Une paire (i,j) est codée sur 14 bits: On écrit d'abord le bit 0, puis la position i sur 8 bits, puis le nombre de caractères à recopier j sur 5 bits.
• La fin de fichier est représentée comme une paire spéciale pour laquelle i = 0 (puisque sinon la valeur de i est toujours au moins égale à 1)

Par exemple, ab(2,2)d(5,3) sera représenté par la suite de bits:

1 01100001 1 01100010 0 00000010 00010 1 01100100 0 00000101 00011  0 00000000 00000
       a        b           2      2        d           5      3       FIN

Q1. Ecrire l'algorithme de décompression. On supposera pour simplifier que la taille du résultat est plus petite que 15000 octets, de sorte qu'on pourra la mettre dans un tableau char text[15000];

Q2. Tester le résultat du programme sur les fichiers exemple.lzj, ann.lzj (un texte), balzac.lzj (un texte), et image.xpm.lzj (une image)

Q3. Ecrire un compresseur rudimentaire, qui n'écrit jamais de paires (i,j) en sortie. Testez le sur image.xpm

Q4. Ecrire un compresseur rudimentaire, capable de remplacer une répétition de plusieurs caractères identiques par un littéral suivi d'une paire. Testez le sur image.xpm

Q5. Améliorer le décompresseur pour qu'il soit capable de décompresser des fichiers de taille arbitraire, mais en n'utilisant qu'un tableau de 2000 caractères au maximum. Tester le résultat sur le fichier gros.lzj

Q6. Ecrire un bon compresseur. Tester le résultat sur le fichier ann.

Q7. Pour faciliter l'écriture du compresseur et du décompresseur, le format de compression a été simplifié. Expliquez ce qu'il faudrait changer pour obtenir un meilleur compresseur.