Description

Si vous utilisez la lib µContest C/C++, vous devez utiliser au minimum la version 2.1

Dans cette épreuve, nous allons mettre en place un algorithme de compression plus complexe et plus "intelligent" que celui utilisé par Data compression I.
Dans ce dernier, on comptait sur de nombreuses apparitions successives d'une même lettre. Mais dans un texte par exemple, cela arrive rarement.
L'idée est donc de réorganiser l'information, de manière à augmenter la probabilité de trouver ces successions de même lettre. C'est précisément le but de la transformée de Burrows-Wheeler.

Une fois le texte transformé, on va appliquer l'algorithme MTF (Move-To-Front), pour à nouveau le transformer et ainsi l'adapter encore mieux à l'algorithme de compression proprement dit, l'algorithme de Huffman.

Nous ne décrivons pas ici le fonctionnement de ces trois algorithmes, de nombreuses informations existent sur Internet.
Cet ensemble d'opérations est à la base de l'algorithme bzip2, qui permet d'obtenir un des meilleurs taux de compression pour les fichiers quelconques.


Mais voici un exemple complet, avec les étapes intermédiaires.
Prenons le texte à compresser suivant :



On commence par appliquer la transformée de Burrows-Wheeler. A vous de vous renseigner sur le fonctionnement de cet algorithme. On stockera la position de la chaîne initiale dans la matrice triée au début de la chaîne de sortie, en commençant par 0 pour la première position par convention (si après le tri la chaine initiale est à la position 5, on ajoutera 4 au début de la chaîne de sortie). On obtient la nouvelle chaîne :


Dans cet exemple, la chaîne initiale était donc à la 36e position.
Ensuite, on applique l'algorithme Move-To-Front. La encore, à vous de vous renseigner sur cet algorithme. Par convention, on prendra le tableau initial permettant de réaliser l'opération dans l'état suivant (voir le fonctionnement de l'algorithme pour comprendre l'utilité de ce tableau) :

Symbole	(espace)	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	0	1	2	3	4	5	6	7	8	9
Indice	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36

Une fois MTF appliqué, on obtient une nouvelle suite de symboles, représentés par des nombres. Pour les représenter, nous les écrivons ici avec des ',' pour les séparer. Voici la chaîne précédente transformée par MTF :



On voit que la séquence, contrairement à ce qu'on espérait, ne contient pas beaucoup de symboles '0'. Cela vient du fait que le texte est trop court, et que la transformée de Burrows-Wheeler ne permet pas de placer suffisamment de caractères consécutifs. Cependant, sur les textes fournis par l'épreuve, le nombre de '0' est significativement plus important. Cela va avoir pour conséquence d'obtenir un très bon taux de compression avec le codage de Huffman.

Le codage de Huffman, comme vous le savez peut-être, associe à chaque symbole du flux à compresser une suite binaire plus ou moins longue pour le représenter, en fonction de sa fréquence d'apparition. Le codage MTF présente une particularité, c'est que la fréquence d'apparition du '0' est beaucoup plus élevée que toutes les autres. Pour éviter d'obtenir des codages différents, nous avons déjà construit la table d'association en suivant l'algorithme (plusieurs codages sont possibles). Voici celui que vous devez utiliser :

Symbole	Code binaire associé	Symbole	Code binaire associé	Symbole	Code binaire associé
0	0	13	101100	25	1110000
1	100000	14	101101	26	1110001
2	100001	15	101110	27	1110010
3	100010	16	101111	28	1110011
4	100011	17	110000	29	1110100
5	100100	18	110001	30	1110101
6	100101	19	110010	31	1110110
7	100110	20	110011	32	1110111
8	100111	21	110100	33	111100
9	101000	22	110101	34	111101
10	101001	23	110110	35	111110
11	101010	24	110111	36	111111
12	101011

Après avoir appliqué le codage de Huffman à notre exemple, on doit obtenir la suite BINAIRE suivante (Les 0 en vert sont rajoutés à la fin pour compléter le dernier caractère, vous devrez également compléter votre résultat avec des 0 si le nombre de bits obtenu n'est pas un multiple de 8) :



Le résultat final est donc constitué de 109 octets, contre 169 initialement, ce qui équivaut à un taux de compression de ~36%. Ce taux sera plus élevé avec les textes fournis (~45%).



Voici les informations complémentaires/résumées pour résoudre cette épreuve. Elle se déroule en deux étapes.

une compression :

- Vous devez récupérer la chaine de caractères à compresser dans txt_a_compresser. Ce texte sera composé uniquement de lettres majuscules et d'espaces.
- Vous devez appliquer successivement les trois algorithmes décrits ci-dessus, avec les contraintes ou conventions indiquées.
- Le résultat obtenu est une suite de bits, dont le nombre n'est pas forcément (en fait assez rarement) un multiple de 8, vous devez compléter votre suite par des bits nuls.
- Vous devez renvoyer votre résultat sous forme d'une chaine de caractères dans txt_compresse, avec les 8 premiers bits de votre résultat constituant le premier caractère, les 8 suivants le deuxième, etc.

et une décompression :

- Vous devez récupérer la chaine de caractères à décompresser dans txt_a_decompresser. Ce texte sera composé de caractères représentant les bits issus du codage de Huffman.
- La variable Nb_Bits_Ajoutes vous indiquera combien de bits nuls ont été ajoutés au résultat de la compression.
- Vous devez appliquer successivement l'inverse des trois algorithmes décrits ci-dessus, avec les contraintes ou conventions indiquées.
- Le résultat obtenu est un texte. Il est composé uniquement de lettres majuscules et d'espaces.
- Vous devez renvoyer votre résultat sous forme d'une chaine de caractères dans txt_decompresse

Variables

Nom	Type		Description
Variables à récupérer
txt_a_compresser	Chaîne de caractères	char*	Le texte à compresser
txt_a_decompresser	Chaîne de caractères	char*	La suite d'octets à décompresser. Attention : Ce buffer peut contenir des '\0', utilisez la longueur fournie par la bibliothèque plutôt que la fonction strlen.
Nb_Bits_Ajoutes	Entier	int	Nombre de bits nuls ajoutés au résultat de la compression pour obtenir un nombre de bits multiple de 8, donnant txt_a_decompresser
Variables à renvoyer
txt_compresse	Chaîne de caractères	char*	Résultat de la compression de txt_a_compresser, avec les contraintes indiquées dans le texte
txt_decompresse	Chaîne de caractères	char*	Résultat de la décompression de txt_a_decompresser