[Exercices] Venez vous entraîner !

Exercice du mois de juin 2008

Nom : Compression RLE
Sujet : Fichiers, chaînes de caractères

Introduction

Dans le monde de l'informatique, une partie de la recherche est consacrée à la compression des données pour minimiser l'espace disque nécessaire. Vous connaissez très certainement les formats zip, rar ou autres tar.gz .
Ce que je vous propose ce mois, est de créer un algorithme de compression de fichiers textes en utilisant l'algorithme de compression RLE (Run-length-encoding). Cet algorithme est généralement utilisé pour compresser les images, par exemple les .bmp ou les .pcx utilisent parfois cet algorithme.
La gestion d'image étant souvent complexe est difficilement faisable de manière standard, je vous propose plutôt de vous attaquer au fichiers textes.

Présentation de l'algorithme

Imaginons que nous ayons la chaîne de caractère suivante :

Code : Autre

Elle prend beaucoup de places et on remarque que certains caractères se répétent, on pourrait donc gagner de la place en indiquant chaque fois le nombre de caractères qui se répétent. Cela donnerait (les espaces sont juste là pour rendre le découpage plus clair) :

Code : Autre

On a gangé de la place, mais on est face à un problème, comment savoir ou découper la chaine pour la décompresser. Le problème se pose avec la présence des chiffres. Pour cela, on va choisir un caractère spécial, le flag, généralement un caractère que l'on trouve rarement dans un texte, par exemple @. Et on va chaque fois écrire :

nombre_de_fois_que_le_char_apparait @ le_char

ce qui donne :

Code : Autre

Et on est face à un nouveau problème, comment gérer les cas ou le flag apparait quand même dans le texte à compresser. Dans ce cas particulier, on choisit la syntaxe spéciale "flag flag":

@ @

Ce qui donne :

Code : Autre

Vous remarquerez également que dans le cas où il n'y a que 1 ou 2 caractères, la compression n'apporte rien, elle agrandi même la longueur de la chaîne. Donc dans le cas où un caractère ne se répète pas ou seulement une fois, on ne le transforme pas :

Code : Autre

Et onn arrive façe au dernier problème, comment savoir que le dernier "13@y" est un bloc et pas deux blocs "1" et "3@y". Pour cela, on choisit de ne compresser que les suites de 9 caractères en une seule fois et de compresser le reste en un deuxième bloc.

Code : Autre

Code : Autre

La chaîne est ainsi beaucoup plus courte qu'au départ et on a perdu aucune information. Pour la décompression, cela se passe exactement de la même manière.

Votre programme

Le programme que vous devez réaliser devra donc permettre de compresser et décompresser un fichier texte en utilisant l'algorithme proposé ci-dessus. En utilisant, par exemple les paramètres du main.

Code : Console

et pour la décompression :

Code : Console

Vous pouvez également laisser le choix du flag à l'utilisateur.

Je vous conseille de commencer par essayer de compresser une string, celle de la présentation par exemple, puis ensuite de vous attaquer à un fichier en le compressant ligne par ligne. Pour les fichier, je vous invite à (re-)lire le tutoriel de Xavinou.

Bonus 1: Indiquez le taux de compression (ou décompression du fichier).

Code : Console

Bonus 2: Pourquoi ne pas utiliser les exceptions pour gérer le cas des fichiers qui sont mal formatés (qui contiennent des erreurs).


N'hésitez pas à poser des questions si la description de l'algorithme n'est pas suffisament claire !

Vous avez jusqu'au 30 juin pour soumettre vos réponses à Réponse_Exercices.

Bonne chance à tous !

EDIT : Modification de la syntaxe de l'encodage du flag.

ok je me lance dedans.

j'ai une question, on peut faire seulement le début de ton algorithme?
Car mettre @0 d'accord mais perso je préfère faire pour tous les caractères le flag.

C'est parti merci.
Moi j'ai une autre question combien de mot francais ont 3 lettres identiques qui se suivent ? je vois bien un taux de compression de 0 %.
Peut être que le mois prochain il faudra l'adapter aux images :0, on a pas fini de transpirer !

C'est pas pour rien que cet algorithme est utilisé pour les images. Il y a pas 50'000 algorithmes de compression simples.

ouhlala un peu compliqué pour moi j'atendrai de progresser

salut
Je viens de commencer ce programme et ca bug un peu
Je fais un programme qui doit ecrire une chaine, la compresser et ecrire la chaine compressee par dessous et voice le resultat:
Code : Console

Le plus bizzare est a venir
Je change les 2 premiers A avec des 0 et...
Code : Console
ensuite j'essaie d'ajouter des characteres et le programme bug
mon code de compression:

Voilà un exercice fort intéressant . Je ne sais pas si je pourrais le faire, car je fais beaucoup de choses en même temps en ce moment.

euh j'abandonne ce projet car trop compliqué.
Beaucoup trop compliqué.

Il y a un problème avec ta méthode:
Fichier texte: Code : Autre
Qui se compresse en: Code : Autre

Comment savoir que le fichier initial n'est pas:
Code : Autre

De plus, le flag a quand même une utilité assez limité, vu que t'interdis de regrouper plus de 9 caractères à la suite, et qu'il rajoute 33% à la taille de ton fichier compressé. En modifiant un peu, il est facile de s'en passer.

shamanas > C'est pas très malin de donner une solution partiel dans ce sujet. Crée un autre sujet si tu veux de l'aide. Comme cela les gens qui veulent tenter de faire l'exercice sans aide extérieure peuvent toujours le faire. En attendant, édite ton message et supprime le code que tu as proposé.

Citation : HunLyxxod

Si @ est le flag et que 0 remplace un @ dans la chaine de caractère,alors 3@0 voudra dire que tu a 3 "0" de suite.
Sinon,on décomposerait ton "3@0" en "3@ 0" où le 0 serait un @ mais où le 3@ ne correspondrait à rien par rapport à la définition qu'on à donné au flag...

Je ne sais pas s j'ai été clair,mais je peux m'expliquer plus clairement

Pour info,je débute en C++ (je n'ai pour l'instant que des notions) et je crois que cet exercice va me plaire

@Inakoll:Code supprime...de toute facon c un exercise pas un concours

perso pour le flag ce serait plus pratique quelque chose où il y a presque aucune chance de trouver cela.

J'en avait parlé avec des secondes de mon institution sur cette histoire de flag il y a quelques mois.

La meilleure solution c'est où des combinaisons d'unicode ou alors

&&-{FLAG}-&&

Voila le flag idéal.

On est sur que l'on peut ne pas se tromper.

Mais c'est un peu long comme flag, on est pas sur de gagner de la place dedans.
Mais pour un jeu avec des niveaux pour spérare chaque niveau c'est LA solution.

Et si tu tentes de compresser le code source de ton compresseur ?

Tu rencontreras ce flag "inrencontrable" et tu es foutu .

"Never trust the user input" (je crois que c'est un truc comme ça )

Trop dur encore ce moi-ci pour moi...

ah oui en effet cyprien, je ne l'avais pas remarqué, ben dans ce cas la, on le remplace par \&&-{FLAG}-&&

Comme ca, on saura que c'est pas un flag, c'est comme pour le C.
Quand on veut faire \ il faut en mettre 2

Je suis un peu étonné de voir autant de "c'est trop dur!". Faut pas abandonner si vite. Une feuille, un papier et c'est parti pour une simulation. Étape par étape. La réponse ne va pas tomber du ciel, mais c'est pas pour autant qu'on peut pas y arriver!

@shamanas:

Merci de pas poster trop de code dans ce sujet. Ca permet aux personnes qui veulent essayer de lire les potentiels compléments sans avoir du code sous les yeux.

@Jaloyan1 (1er poste):
On s'enfout de comment tu préfères faire.

@HunLyxxod :
3@ -> 3@0 -> 000 En effet. C'est pour cela, qu'on utilise un flag qui n'apparait jamais dans le texte. Il n'y a pas de solution à ce problème si on utilise un flag. Il y aura toujours une séquence de caractère qui coince. Une solution est souvent de remplace la séquence "flag" par "flagflag", ce qui ne résoud pas entièrement le problème.
Ne pas utiliser de flags pose lui un autre problème, celui que j'ai soulevé dans la première partie. Comment savoir si "33" est 3 suivi de 3 ou 3 fois 3 ?

@Jaloyan 1: Si on utilise un flag de plus de 1 caractère, le problème reste le même et en plus, ça diminue gravement le taux de compression.

Hum, es tu sur que le flag soit vraiment nécessaire ?

Si par exemple on note nombre_de_caractere(rien)caractère(rien)nombre_de_caractere(rien)caractère etc..., en limitant à neuf on aurait par exemple :

CCCCCCBBBCCU333ZZZZ@YYYYYYYYYYYYY

Sans flag :
6C3B2C1U334Z1@9Y4Y

Avec un flag :
6@C3@BCCU3@34@Z@09@Y4@Y

Là c'est plus court sans flag.

Mais avec un autre exemple comme :

AAABCCDEFGHHH@JJKLLLLMNOOOOPPPQSS

Sans flag :
3A1B2C1D1E1F1G3H1@2J1K4L1M1N4O3P1Q2S

Avec :
3@ABCCDEFG3@H@0JJK4@LMN4@O3@PQSS

La méthode avec flag est plus courte, mais ne fait qu'un caractère de moins que l'original ; quant à la méthode sans flag, elle est plus longue que l'original...
Toutefois on évite les problèmes d'arobase.

Donc le flag est il vraiment indispensable ? (bon ça peut être une consigne compliquant la tâche, mais comme on est programmeur on est fainéant et on n'aime pas l'inutile )

Perso j'aurait faire encore plus condensé : chaque caractère est sur deux octets.
Le premier octet c'est le nombre de fois et le second c'est le caractère concerné
Ca permet d'écrire genre "255 fois A" sur deux octets (0xFF (255) 0x41 ('A'))
Par contre, encore là il faut se méfier, ça peut faire des fichiers plus lourds que les originaux (remarque je suis sur que la première méthode compresse pas grand chose sur un texte lambda, c'est très rare de voir des AAAA)

Après si on compresse un fichier texte écrit en langue française.. bas le taux de compression va être quasi nul non? (très peu de lettres doublé et aucune triplé et plus :/)

On va pas débattre sur la meilleure façon de compresser non ? L'énoncé a été donné par Nanoc, on respecte cet énoncé. Ce n'est qu'un entrainement, donc cette algorithme là me parait déjà bien, on ne va pas chercher la perfection. M'enfin libre à vous.

Sinon:
-Tu demandes de la POO pour cet exo ?
-On ouvre le fichier "fichier.txt" qu'on doit compresser, mais l'énoncé ne dit pas si on réecrire le contenu compressé dans ce fichier là ou créer un nouveau fichier "fichierCompressé.txt" ?
-Et donc si le fichier à compresser contient "@@@", pourquoi on ne peut pas compresser en "3@@", j'ai pas compris ?

ben je pense plutot que taux compressé : -5000%

Car essaie de faire cette phrase

Salut ca va?

Code : Autre


Ou alors Code : Autre


ou alors ...


Code : Autre


Vachement utile la compression dans ce cas la.
Perso pour les images ce serait plus pratique comme tu l'a dis nanoc.

Mais bon c'est juste un exo.

Et perso le cas du 1@@ double flag serait plus pratique dans ce cas la.

j'ai deja presque fini

@genius:
Si tu dois décompresser 23, comment savoir si c'est :
23 ou 33 qui était à l'origine. Le flag est indispensable. C'est pas moi qui ai inventé la méthode

@devy:
Encore mieux: Le système de compression tar.bz2 ! Sauf que c'est beaucoup trop compliqué. Le but ici est de faire du RLE. Si il faut commencer à s'attquer aux octets, alors effectivement on peut faire beaucoup mieux.

@Goten:
Tout à fait, c'est pour cela que ce truc est en général utilisé pour les images (voir le lien Wikipédia). Mais comme c'est un exercice de programmation pour débutants, on travaille avec des fichiers textes et pas des images.

@Kurlze:
La POO ne me semble pas nécessaire ici. Disons que si je dois coder cela, je ne vois pas l'intéret de faire une classe. Pour le fichier final, libre à toi de faire ça comme tu veux.
Pour les "@@@", essaie de décompresser ton truc et tu verras ce qui se passe...

J'ai une question.
Si l'utilisateur utilise un flag perso pour compresser faut il entrer ce nouveau flag pour la decompression ou bien lors de la compression par exemple le premier caractère doit etre le flag et alors la décompression se fait sans avoir besoin d'entrer le flag comme paramètre. Le probleme de cette technique c'est que ca rajoute encore un caractère et donc le taux de compression est encore réduit.

@Nanoc :
23 => 1213
33 => 23

Avec "ta" méthode, pour une suite d'un à trois nombres, la compression est nulle, sinon on gagne n-3 caractères sur une suite de n nombres.

Avec "ma" méthode, sur un nombre seul on perd un caractère, sur deux aucune différence, et à partir de trois on gagne n-2 caractères.

Je pense donc que les deux manières se valent plus ou moins, mais je trouve "la mienne" plus simple.


Autre idée sinon : on pourrait compter avec des lettres (comme en hexa, mais jusqu'à z (voire même 0-9 a-z (=> 10>36 (vive les parenthèses)) A-Z (=> 37>63))) une fois les 9 caractères identiques dépassés)

Ce qui donnerait :
YYYY => 4Y ou 4@Y => au lieu de 4@Y
YYYYYYYYYYYY => cY ou c@Y => au lieu de 9@Y 3@Y
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY (53) => PY ou P@Y => au lieu de 9@Y 9@Y 9@Y 9@Y 9@Y 8@Y

On voit qu'on gagne pas mal de place

comment on fait pour qvoir un multimap non ordonné?

@genius : avec ta méthode on pourrait meme augmenter cela sur un octet, avec tous les caracteres ANSI compris entre 0x0 et 0xFF
Comme ca on travaile sur une base 256 et donc jusqu'a 255 caracteres possibles.
Ca étend la marche.

@zero_ptt: http://cpp.developpez.com/faq/cpp/?pag [...] oix_conteneur

Petite question, est-ce qu'on doit obligatoirement garder l'odre ? Car quand je decompresse, j'écris en ordre alphabétique.

Exemple :

not compressed : JJJIIIII
compressed : 5@I3@J
decompressed : IIIIIJJJ

Grave ou pas ?