Discussion :

[tnarol]

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

[Invité(e)]

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 ?

[tnarol]

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.

[Mac LAK]

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.

[tnarol]

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.

[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 ?

[pseudocode]

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.

[nirgal76]

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.