Algo de compression simple

Salut,

Je souhaite résoudre un problème qui probablement est ultra-classique mais personnellement c'est la première fois que je le rencontre. J'ai un tableau de données de taille fixe (mettons 1000 octets) et je dois trouver une manière relativement efficace de compresser ces données en conservant la possibilité de les restituer octet par octet. Bien sûr je ne peux pas utiliser de programme de décompression trop complexe, je pense donc que la seule solution consiste à identifier des séquences fréquentes pour factoriser la séquence complète.

Merci

Bonjour,

Avant de choisir un algo, il faut savoir quel est le type de données à compresser. On ne compresse pas une image comme on compresse du texte.

Que contient ton tableau ?

Citation:

---

Envoyé par mabu

Bonjour,

Avant de choisir un algo, il faut savoir quel est le type de données à compresser. On ne compresse pas une image comme on compresse du texte.

Que contient ton tableau ?

---

C'est a priori une image pour un afficheur numérique monochrome (48 lignes x 84 colonnes), chaque bit est un pixel allumé ou éteint.

S'il y a de grands aplats de couleurs, la compression RLE est ultra simple et très rapide à faire comme à exécuter. Si par contre l'image est fortement tramée, RLE ne sera pas efficace, il faudra envisager soit du Huffman (moyennement difficile à implémenter), soit du LZ* (un peu plus chaud déjà)...

Toutefois, pour une image de 504 octets, est-ce bien raisonnable de vouloir compresser ? Quel est le but final ?

Si tu cherches juste à utiliser un algo et non pas à l'implémenter toi-même, je te conseille l'excellente librairie "LZO", qui permet des compressions quasiment en temps réel avec une très faible consommation mémoire, et qui est très bien adaptée à des compressions uniquement en RAM et sur d'assez faibles quantités de données.

Citation:

---

Envoyé par tnarol

C'est a priori une image pour un afficheur numérique monochrome (48 lignes x 84 colonnes), chaque bit est un pixel allumé ou éteint.

---

Tu peux utiliser le "Modified Huffman Coding" qui est l'algo utilisé par les Fax pour envoyer des images binaires.

Si c'est du monochrome, une bonne compression sans perte sera du CCITT groupe 3 ou mieux du CCITT groupe 4. C'est pas très difficile à développer, je l'ai fais à une époque où je n'étais pas loin d'être débutant.

Citation:

---

Envoyé par Mac LAK

Toutefois, pour une image de 504 octets, est-ce bien raisonnable de vouloir compresser ? Quel est le but final ?

---

Oui c'est un point important. Le but est de faire tenir les instructions assembleur pour charger l'image dans une mémoire programme de 1Ko, sachant qu'évidemment il n'y a pas 504 octets de libre (impossible de hardcoder bêtement).

Sachant cela j'ai l'impression que les algos cités ne conviennent pas car le codage de l'algo de décompression nécessite déjà trop d'instructions. Il faut donc impérativement (je pense) utiliser des sous-routines qui sont appelées plusieurs fois chacunes pour diminuer la taille du programme. Toute l'intelligence de l'algo que je recherche consisterait à reconnaître dans l'image des séquences d'octets répétables pour minimiser la taille de code.

Je ne comprend pas bien la démarche alors.
Un code de taille minimal correspondra à des données non compressées.
Ta limitation porte sur le code ou sur les données ? Ou sur les 2 en même temps ?

Dans ce genre de cas aussi limité, tu n'as guère d'autre choix qu'utiliser un codage RLE, c'est à peu près le seul et unique qui permettra une compression (légère, pas de miracles) avec un code de décompactage quasi-nul.

Toutefois, si ton image est mal foutue vis-à-vis du codage RLE, tu risques d'augmenter la taille de ton image au lieu de la réduire, c'est le risque... Mais bon, sur le PC, tu peux tester à peu près tous les cas de figure possible et rajouter un octet d'entête pour indiquer la "méthode" utilisée.

Tu pourrais éventuellement poster quelques-une de ces images, mises au format PNG/GIF, afin qu'on se rende compte du type d'image à compresser ?

Citation:

---

Envoyé par Ulmo

Je ne comprend pas bien la démarche alors.
Un code de taille minimal correspondra à des données non compressées.
Ta limitation porte sur le code ou sur les données ? Ou sur les 2 en même temps ?

---

Ben oui les deux en même temps : si j'ai envie d'écrire un octet de données dans l'afficheur il faut obligatoirement que je l'écrive dans le code assembleur. Par contre je peux faire des optimisations : à partir du moment où je remarque qu'un octet ou une série d'octets se répète à plusieurs endroits ça peut être plus rentable de brancher sur une sous-routine qui affiche cela.

Citation:

---

Envoyé par Mac LAK

Dans ce genre de cas aussi limité, tu n'as guère d'autre choix qu'utiliser un codage RLE, c'est à peu près le seul et unique qui permettra une compression (légère, pas de miracles) avec un code de décompactage quasi-nul.

---

Je suis d'accord avec cette remarque. Le principe du RLE est assez souple pour inventer des variantes qui repoussent la complexité à la phase de compactage et qui laissent le décompactage assez simple.


Par exemple, l'utilisation d'un bloc de contrôle entre chaque bloc de données:

[ctrl][data][ctrl][data][ctrl][data]...

Le bloc [ctrl] permettant de définir et contrôler l'utilisation du bloc de donnée suivant.

Exemple:
Ctrl (taille fixe 8 bits) : XX YYY ZZZ
X = 00, recopier les YYYZZZ bits suivants
X = 01, recopier YYYZZZ fois le bit suivant
X = 10, recopier YYY fois les ZZZ bits suivants
X = 11, recopier 2^YYY fois les ZZZ bits suivants

Citation:

---

Envoyé par pseudocode

Je suis d'accord avec cette remarque. Le principe du RLE est assez souple pour inventer des variantes qui repoussent la complexité à la phase de compactage et qui laissent le décompactage assez simple.

---

En fait dans mon cas particulier, je n'ai pas besoin d'avoir une eprésentation des données compressées, je passe directement au code qui traduirait une forme de compression. La difficulté est donc exclusivement au niveau du choix de sous routines primitives d'affichage qui économisent du volume de code. Eventuellement elles peuvent dépendre des données de l'image, mais dans un premier temps je vais m'inspirer du codage RLE en utilisant exclusivement une sous routine du type "affficher n fois le même octet". Si vous voyez d'autres types de sous routine utiles je prends !

Citation:

---

Envoyé par tnarol

Si vous voyez d'autres types de sous routine utiles je prends !

---

Oh, c'est assez facile en fait, les axes de recherche sont :

• Le parcours de l'image dans d'autres sens que le classique "gauche->droite / haut->bas".
  Par exemple, imagine une série de lignes noires verticales réparties aléatoirement... En parcours "normal", elle serait presque incompressible. En parcours "vertical", elle va être monstrueusement réduite.
• L'analyse par blocs 2D, repérant les répétitions 2D et non plus uniquement 1D.
• Les copies : indiquer qu'à un endroit, on utilise les N octets d'un autre bloc, à l'identique.
  Variante triviale : deux lignes consécutive identique.
  Variante moins évidente : motifs répétés et décalés dans l'image.
  Variante encore moins triviale : repérer les copies "à l'envers", type miroir.
• Repérer un maximum de symétries dans l'image.
• etc.

Mais comme je te l'ai dit, il faudrait que tu nous montres de "vraies" images de ton truc, de préférence significatives, afin que l'on puisse trouver d'autres idées.
Si en plus tu génères un code assembleur en lieu et place de l'image elle-même, il est évident par contre qu'il faut repousser la complexité au maximum vers la phase de "compression".

Si tu as une couleur qui domine beaucoup plus que l'autre (et uniquement dans ce cas) tu peux stocker la bitmap dans une matrice creuse.

Citation:

---

Envoyé par nirgal76

Si tu as une couleur qui domine beaucoup plus que l'autre (et uniquement dans ce cas) tu peux stocker la bitmap dans une matrice creuse.

---

Ce qui revient peu ou prou à un codage RLE, car l'image est monochrome : chaque pixel est déjà codé sur un seul bit... ;)

La matrice creuse ne va préciser que les éléments d'un certaines couleurs (enfin je crois, je connais pas top non plus)
Le RLE va donner des successions de blancs et des successions de noirs
Faudrait mixer les 2 ;)

Ou mieux, tu ne mémorise que les positions ou la couleurs change.