Discussion :

[crocodilex]

Salut à tous,
je suis à la recherche d'un algo de compression et de décompression de fichier texte. Rien de plus banal vous me direz.
Mon problème est que je suis très limité en mémoire (c'est pour un logiciel embarqué).
Donc je me suis dit, pourquoi ne pas compresser le fichier sur machine hôte et ensuite le linker avec mon appli. Il suffit ensuite d'integrer la partie décompression dans l'appli.
Le problème est que je souhaite décompresser le fichier bloc par bloc et non dans son intégralité. Ce qui me permettrais de traiter mon fichier au fur et mesure pour ne pas exploser ma mémoire.
Est-ce que ce genre de truc existe et sinon y a t-il un moyen plus judicieux.
Merci d'avance.

[Hephaistos007]

Je sais pas si ca répond à ta question mais le codage de Huffman est le plus efficace qui existe, à condition d'avoir déjà des statistiques sur les textes à transmettre. Dans la réalité, c'est le codage de LEMPEL-ZIV qui est utilisé car il ne nécessite pas de statistiques à priori.

Mais pour de l'embarqué il faut sans hésitation choisir Huffman si tu peux constituer des statistiques sur les textes que tu comptes transmettre.

[parp1]

Salut. Ba la plus banales des statistiques a faire pour Huffman c'est de compter simplement les lettres...Si ya beaucoup de E peut de bit pour le codé.
Si ya tres peu d'Y plus de bit pour le coder...

"Aparté simpa le croco de la pub AMSTRAD ... enfin si je me rapel bien."

Sinon je pense que Hufffan est ce qu'il faut.

Sinon tu pourrais pas envoyer les stats de ton texte en entete par exemple que ton decodeur sache que tel lettre ou caractere vaut tel mot binaire....

Faire une sorte de LUT ou (look up table) Utilisé en image.

on va regarde dans un tableau ce que tel mot binaire veut dire .


Je ne sais pas si j'ai été bien clair.
Bon courage.

[kael kael]

Salut

Si tu veux éviter d'avoir à calculer les statistiques de chacune des lettres dans le texte, tu peux utiliser la méthode d'Huffman adaptative (ou dynamique).

Elle consiste à construire l'arbre d'Huffman et à produire le code compressé au fur et à mesure de la lecture du texte.
Concernant la place que ça prend, si tu considères le codage ASCII, tu as, au plus, 256 feuilles (+1 feuille 'spéciale' pour le codage d'Huffman). Donc un arbre de 257 feuilles et 256 noeuds.
Un chainage parent/fils, précédent/suivant, peut-être très utile dans le codage d'Huffman dynamique : 4*4 octets pour le chainage
Les noeuds vont contenir un poids : 4 ou 8 octets (selon tes envies )
Les feuilles vont contenir un poids et une lettre : 5 ou 9 octets...
Donc au total, dans le pire des cas tu t'en sors pour un peu plus de 12 000 octets...

Bon courage

[Jean-Marc.Bourguet]

Je sais pas si ca répond à ta question mais le codage de Huffman est le plus efficace qui existe, à condition d'avoir déjà des statistiques sur les textes à transmettre. Dans la réalité, c'est le codage de LEMPEL-ZIV qui est utilisé car il ne nécessite pas de statistiques à priori.

Mais non. Huffman est le meilleur codage, sous certaines hypotheses. En gardant quasiment les memes, un codage arithmetique peut deja faire mieux. Lempel-Ziv
ne travaille pas du tout dans le meme cadre (d'ailleurs on applique souvent un codage de Huffman sur le resultat de LZ) et fait mieux.

[Jean-Marc.Bourguet]

Le problème est que je souhaite décompresser le fichier bloc par bloc et non dans son intégralité. Ce qui me permettrais de traiter mon fichier au fur et mesure pour ne pas exploser ma mémoire.

Quelle est la taille du fichier complet? Quelle est la taille des blocs a decoder?
De quel espace tu disposes pour ton implementation du decodage?

[crocodilex]

Merci à vous tous pour vos réponses.
Donc la tendance serait pour un codage/décodage Huffman.
Le fichier que je dois traiter est une suite de bloc ascii qui a
cette allure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-----------------------------------------------------------------
          :::        %        :::::::::     !!!!!!!!!!!!!
   #"####            ####          ~~~~~~~~~~      ##########
 
                 &&&&&&&          uuuuuu          mmmmmmm
    sssssss               $$$$$$$$$$$$$$$$$$$$$
  &&&&&&&
                      ;;;;;;;                      oo
      #"####     $      ####          ~~~~~~~~~~      ##########
 
 
          dddddddddddddddddddddd
 
                     "''''''               ^^^^^^^^^^^^^^
   (((((((((                    (((((((((((      [[[[[[[[[[[[[
                &&&&&                               #############
 -----------------------------------------------------------------

Evidemment chaque bloc est different.
La taille de mon fichier avoisine les 50Mo et je ne dispose que de
8Mo de RAM. Si j'arrive à un facteur de compression de l'ordre de
10, je serais content.
Au vu du contenu de mon fichier, je pense que c'est très faisable.
Qu'en pensez-vous ?

[Charlemagne]

Vu l'allure de ton fichier, je dirais qu'il faut compter le nombre de caractères identiques consécutifs et coder de cette manière:
AAAAAAAAAABBBBBCCCCCCC -> [10]A[5]B[7]C
(les nombres sont bien entendu codés sur un octet)
Si tous les fichiers à comprimer sont comme celui là, Huffman fera jamais mieux et plus facile.
Lempel Ziv (Welch) pourrait faire mieux, mais en plus difficile et ça consommerait plus de mémoire pour les calculs.

PS: Le nombre 0 pourrait être utilisé comme caractère d'échappement, par exemple pour marquer le début d'un bloc...

[Pragmateek]

Au vu du nombre d'espace il faudrait les traiter de manière particulière sans avoir à resignaler leur présence à chaque fois.

[Jean-Marc.Bourguet]

Qu'en pensez-vous ?

Un codage de Huffman d'ordre un sur des octets est limité à un facteur 8 comme gain. Mais il y a moyen de faire mieux.

Au vu de ce que tu montre, on remarque deux choses:

1. on n'utilise pas tous les caractères;
2. un caractère est généralement répété.

On peut facilement profiter de la deuxième propriété en encodant successivement le caractère et le nombre de répétitions, à chaque fois sur un octet (si on répète plus de 255 fois, il suffit de mettre une nouvelle paire). Le résultat est extrèmement simple à décoder -- plus qu'Huffman qui demande des manipulations de bits -- et devrait être efficace -- peut-être aussi plus qu'Huffman.

Pour profiter de la première remarque, tu peux agir comme suit: si tu utilises moins de 128 caractères (ou moins de 64, de 32, ...) tu peux vouloir profiter du bit (ou des 2, 3, ...) bits inutilisés dans l'octet représentant le caractère. Une possibilité pour ces bits est d'analyser les répétitions les plus fréquentes. Disons qu'il s'agit de 5, 8, 1, 12, 24 et que tu as 128 caractères. 7 bits de ton octet caractère représenterons le caractère encodé (à décoder avec une table), le 8ième représentera soit une répétition de 5, soit l'indication qu'il est suivi par un octet de répétition. Si tu as 64 caractères, 6 bits représenterons ton caractère, les 2 autres représenterons des répétitions de 5, 8 et 1 ou une indication que le caractère est suivi par un octet de répétition. De nouveau c'est très simple à décoder -- l'encodage demande un peu plus de boulot et d'analyse, mais je doute que ce soit important pour toi -- et il est facile de commencer à décoder où tu veux (il te suffit d'une table indiquant où commence tes blocs).

Je doute qu'il soit besoin d'utiliser quelque chose de plus poussé, mais si c'est le cas, tu peux suivre par un codage de Huffman ou un autre algo classique.

[Charlemagne]

Petites extensions à ce que je propose au-dessus si ça suffit pas:
-coder les nombres sur moins de 8 bits. Si par exemple des répétitions de plus de 31 caractères sont rares, coder le nombre sur 5 bits.
-coder chaque caractère entre 2 nombres avec Huffman quand même.

Inconvénients:
-pas possible de sauter tous les 2 octets pour lire le fichier compressé, pour passer d'un mini bloc à l'autre
-gestion au niveau du bit, plus difficile