Top 20

1 0x00h 705 pts
2 boris39 705 pts
3 neoxquick 686 pts
4 maf-ia 667 pts
5 thefinder 648 pts
6 benito255 612 pts
7 mego 594 pts
8 madbat2 585 pts
9 Mart 557 pts
10 tehron 507 pts
11 Kithyane 506 pts
12 plucth 483 pts
13 egosum 477 pts
14 CoYoTe99 420 pts
15 Undr 418 pts
16 Zeta 418 pts
17 loonies2 414 pts
18 Armavica 413 pts
19 vitalimarrenra 406 pts
20 b0n0n 398 pts

Classement complet

Shoutbox

20 Sep - 10:46 am

Bonjour à tous, j'ai créé un nouveau topic sur le forum concernant un problème que je rencontre sur plusieurs challenges, comme il n'est plus très actif, que j'aimerais pouvoir avancer sur ces challenges et que ce chat a une meilleure visibilité, je poste ce message ici en espérant qu'une âme charitable puisse m'aider en répondant à mon message sur le forum :)

3 Sep - 9:39 am

Ah ok je n'avais pas bien compris ton message original. Très bien, ce que tu peux faire c'est poster un message sur le forum avec le lien de téléchargement et les explications. Merci pour ta contribution !

1 Sep - 5:52 pm

Bonjour bonjour, je l'ai créé en Pharo, une implémentation récente du langage smalltalk.

31 Aug - 2:43 pm

Bonjour PharoGuy, re-bienvenue à toi ! Tu as créé cet objet en quel langage ?

30 Aug - 8:23 pm

Bonjour tout le monde ! je redécouvre ce site avec Pharo ! J'ai créé un objet qui gère la récupération et l'envoi des variables, ça pourrait intéresser ?

24 Jul - 5:30 pm

Ça devrait être à nouveau opérationnel, définitivement cette fois ci.

19 Jul - 8:42 pm

A nouveau ? On regarde ça !

16 Jul - 5:26 pm

Bonjour à tous :) Je viens d'essayer de valider le challenge "Wav ? (6)", et j'ai l'impression que la page "validation.php" est de nouveau en carafe.

15 Jul - 8:43 pm

Cool !! Merci beaucoup !!

9 Jul - 11:20 pm

Hello, je regarde ça dès que je peux, probablement demain

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