Partie 1

fichiers nécessaires

Le but de cette première partie est d'implémenter l'algorithme de Burrows-Wheeler comme vu en cours.

Pour vous aider, la partie importante a déjà été écrite, et se trouve dans le fichier test.c. Les premières questions permettent de comprendre ce qui a été écrit.

Q1. Lancer le programme test.c. Expliquer ce que fait la fonction cmp. Complétez le code du programme pour qu'il affiche les permutations de la chaîne initiale de façon triée.

Q2. Modifier le code pour qu'il mette dans un fichier le résultat de l'algorithme de Burrows-Wheeler. Dans le cas de l'exemple il s'agit donc de mettre dans le fichier le mot mpehsoohmmroi

Q3. Modifier le programme pour qu'il prenne un nom de fichier en entrée, lise le contenu du fichier et le mette dans le tableau T DEUX FOIS, puis écrive le résultat de Burrows Wheeler dans un autre fichier.

Q4. Si vous n'avez pas fait le TP précédent (Partie 3), implémentez la méthode move to front.

Q5. Mettez tout ensemble pour obtenir un logiciel de compression qui, partant d'un fichier en entrée, renvoie un fichier en sortie obtenu en lui applicant (a) d'abord Burrows-Wheeler (b) puis move-to-front (c) puis le compresseur d'entropie (Partie 2 du TP précédent).

Q6. Félicitations, vous avez écrit votre premier compresseur performant. Vous pouvez lever les bras en signe de victoire puis passer à la suite.

Partie 2

Q0. Si ce n'est déjà fait, écrire le décodeur move to front (Q9 du TP précédent).

Q1. Implémentez l'algorithme de décodage de Burrows-Wheeler.

Q2. Félicitations, vous avez écrit un logiciel de compression/décompression complet. Vous pouvez lever les bras en signe de victoire et rentrer chez vous.