Top 20

1 0x00h 702 pts
2 boris39 702 pts
3 neoxquick 683 pts
4 maf-ia 664 pts
5 thefinder 645 pts
6 benito255 609 pts
7 mego 592 pts
8 madbat2 582 pts
9 Mart 555 pts
10 Stupefy 534 pts
11 nikokks 514 pts
12 tehron 505 pts
13 Kithyane 503 pts
14 plucth 481 pts
15 egosum 474 pts
16 CoYoTe99 417 pts
17 Undr 416 pts
18 Zeta 416 pts
19 loonies2 412 pts
20 Armavica 411 pts

Classement complet

Shoutbox

12 May - 11:47 am

Working again now.

10 May - 4:05 pm

Hello, sorry for the late answer, in fact yes there is an issue with the mail, we will try to fix it quickly. Thanks for reporting

7 May - 6:07 pm

Hi there is a issue for the challenfe Email (number 21). I don't receive a mail on any of them: gmail, hotmail, yahoo. do i fail or is it the challenge ?

28 Feb - 10:35 am

Yes we fixed it

27 Feb - 10:00 pm

Thank you, just validated contest22. The solution checker seems to have been fixed.

27 Feb - 8:40 am

Yes several solutions are accepted of course. I will check one of your answers

26 Feb - 7:51 pm

No 500 error, but the solutions I'm submitting can be verified to be correct. It can't be that only one configuration is accepted, right? - as there are multiple correct configurations for each problem.

26 Feb - 5:54 pm

contest 22 is not concerned by the issue I found, and seems to be working (I suppose you don't have 500 error on this one ?). Your solutions are indeed rejected, but I did not check them yet

26 Feb - 3:25 pm

The validation for contest 22 also seems to be wrong (it's not accepting solutions that are clearly correct). I submitted bug report yesterday.

26 Feb - 9:59 am

Ok I fixed the issue It is higly possible that other challenges are impacted, so don't hesitate to tell meif you encounter this again. Thank you for reporting

Connexion
Mot de passe oublié

Supportez nousx

Vous aimez µContest ?
Supportez nous en votant (fun et difficulté) pour µContest sur WeChall :)
Si vous ne l'avez pas encore fait, profitez-en pour lier votre compte
Wechall à µContest pour pouvoir voter !

Merci

Liste des épreuves :: Divers :: Data compression II (34)

Résumé

ID : 34
Points : 17
Validations :
Page de l'épreuve
Reporter un bug

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 :

A TRAVERS LES CHAMPS DE BETTERAVES DEVANT LUI IL NE VOYAIT MEME PAS LE SOL NOIR ET IL N AVAIT LA SENSATION DE L IMMENSE HORIZON PLAT QUE PAR LES SOUFFLES DU VENT DE MARS


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 :

"35NESSNTSSRETILETSSRTETLLLEENTAESAUELSVYHVPMPLS RR       DSDDUMLNMSMVTVLVLL BDUFC U   TOAAR IIO P  F   E MIA OO  EEEANSIZHSV   M IATEOEAEPEEARERNN   NEINIATA EDQOLAE AA OI"

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)ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
Indice0123456789101112131415161718192021222324252627282930313233343536


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 :

30,32,16,8,21,0,2,22,2,0,22,4,3,15,18,3,3,5,0,5,2,3,1,4,0,0,2,0,6,3,10,3,6,2,23,3,6,4,24,27,19,2,24,23,1,6,6,16,13,0,1,0,0,0,0,0,0,19,3,1,0,11,7,6,14,2,5,1,9,14,1,5,1,1,0,8,18,9,9,20,20,5,3,1,0,0,8,24,18,0,14,4,19,0,4,2,16,1,0,9,1,0,0,19,1,15,6,8,3,7,0,1,0,5,0,0,3,17,17,6,28,19,3,19,8,0,0,10,1,6,8,14,10,11,1,3,1,13,1,0,2,14,2,1,13,0,8,0,0,1,3,8,2,1,5,8,1,5,5,17,26,10,20,6,5,6,2,0,1,4,8


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 :

SymboleCode binaire associéSymboleCode binaire associéSymboleCode binaire associé
0013101100251110000
110000014101101261110001
210000115101110271110010
310001016101111281110011
410001117110000291110100
510010018110001301110101
610010119110010311110110
710011020110011321110111
81001112111010033111100
91010002211010134111101
101010012311011035111110
111010102411011136111111
12101011


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) :

11101011 11011110 11111001 11110100 01000011 10101100 00101101 01100011 10001010 11101100 01100010 10001010 01000100 10010000 11000101 00000100 01100100 00101001 01100010 10100110 00101001 01100001 11011010 00101001 01100011 11011111 10010110 01010000 11101111 10110100 00010010 11001011 01111101 10001000 00000000 11001010 00101000 00010101 01001101 00101101 10110000 11001001 00000101 00010110 11000001 00100100 00010000 00100111 11000110 10001010 00110011 11001110 01001000 10100000 00100111 11011111 00010101 10110001 11100100 10001110 00011011 11100000 01010001 00000001 10010100 00010111 01001011 00111100 01010011 00100000 01001000 01000101 10000110 00010010 11110011 11001010 00101100 10100111 00101001 10000010 01011001 11101101 10100110 10101000 00100010 10000010 11001000 00010000 11011011 00001100 00010110 00100111 00100000 10001010 01111000 01100000 10010010 01111000 00100100 10010011 00001110 00110100 11100111 00101100 10010010 11000010 10000010 00111001 11000000


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_compresserChaîne de caractèreschar*Le texte à compresser
txt_a_decompresserChaîne de caractèreschar*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_AjoutesEntierintNombre 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_compresseChaîne de caractèreschar*Résultat de la compression de txt_a_compresser, avec les contraintes indiquées dans le texte
txt_decompresseChaîne de caractèreschar*Résultat de la décompression de txt_a_decompresser