Méthodes de compression - Page 1

Dans l'objectif d'un TPE je dois réaliser un programme s'occupant de compresser des fichiers sur PC de taille variable et de données variable.

Le programme doit possèder au moins 3 méthodes de compression mais je pense en faire plus:

-RLE
-Huffman
-Méthode perso.
-LZW

Pour l'instant j'ai réalisé 2 méthodes soit RLE et méthode perso, mais je voudrais trouver un moyen d'améliorer ma méthode qui donne d'assez bon résultats. Et je voudrais avoir votre avis sur différents foirmat qui pourrais l'améliorer ou s'adapter sur certains fichier.

Ma méthode ce base un peu sur le RLE mais niveau binaire, une variable de 1 octet environ indique les occurences et le comportement du décompresseur...
Le but est de trouver le nombre de fois des octets qui ce succède avec le même bit de poids fort, et de copier dans le fichier de destination tout ce qui ce situe après le bit de poids fort...

5 Bits = Occurence (Nombre d'octet qui ce suivent avec le même bit de poids fort)
1 bit = Type d'octets (0=Octets différent de 0, 1=Octets vide).
3 bits = Bit de poids fort.

Variable=Occurence*(8-bit de poids fort) Les données binaire ce situant après le bit de poids fort.

Dans le cas où des octets nuls ce suivent, les 3 bits indiquant le bit de poids fort sont inexistant.

Je pense vraiment que ce format peut être amélioré, mon but et de trouver un moyen de décompression rapide mais avec la possibilité de décompresser les données en temps réel car mon objectif et de trouver une méthode capable d'envoyer des données compressés via le link des TI et de décompresser ça en même temps.

Le gros point noir de ma méthode c'est que le temps de compression est assez lent et demande un fichier temporaire. Mais la décompression est très rapide.

Vous verrez quoi comme améliorations ou format?

J'ai rien compris

²
Qu'est-ce que tu veux dire quand tu parles de coder sur 3 bits le bit de poids fort il ne peut prendre que 2 valeurs que je sache...
Ensuite en quoi ça compresse ? il te reste 7 bits par octet, tu veux les mettre à la suite les uns des autres, donc en décalant à chaque fois ?? c'est complètement tordu et en plus comment tu fais si ton nombre d'octets ayant le même bit de poids fort n'est pas un multiple de 8 ? et en plus dans le meilleur cas tu ne gagnes qu'un bit par octet, et dans le pire cas tu doubles la taille du fichier, c'est ta méthode de compression dis-moi...

(Non sérieusement j'ai absolument rien compris)

Ok j'en était sur.

En bref ma méthode compresse 50% mieux que le RLE mais ça dépend les fichiers, voici comment je procéde, bien sûr il peux y avoir des pertes et augmenter la taille du fichier...

Voici comment les fichiers compressé sont construit:

4 bits = Occurences (de 0 à 31) soit de 1 à 32 lors de la décompression car 0 est impossible!
1 bit = Octet nul ou autre, si ce bit est à 1 on est sur un octet nul sinon autre.

Dans le cas ou le bit d'avant est à 0:
3 bits = Numéro du bit de poids fort soit de 0 à 7
variable= Reste de l'octet.

Un exemple:

0001 0000 0001 1010 0001 0011 0000 0000 0000 0000 0101 0000 1000 0000

Les octets 0,1,2 possède le même bit de poids fort soit à la position 4 et donc d'occurence 3 mais codé en 2.
Les octets 3,4 sont nul donc il faut mettre l'occurence et le bit à 1.
Les octets 5,6 sont different donc il y a une perte.

Ce qui donne une fois compressé

Les 3 premiers octets:
Occurence, bit à 0, Bit de poids fort
0010 0 100 0000 1010 0011

Les octets 3,4:
Occurence, Bit à 1
01 1

Les octets 5 et 6
Occurence, bit à 0, Bit de poids fort
0000 0 110 010000
0000 0 111 0000000

Au final non compressé=56
Compressé=52

On voit que le gain est vraiment faible surtout à cause des octets 5 et 6, ce format possède de nombreux inconvénients que je voudrais résoudre mais donne des avantages dans beaucoups de fichiers à compresser.

En tout cas le principe y est.

A mon avis dans un grand nombre de cas ton format de compression doublera presque la taille du fichier (exemple : même en compressant un texte, qui est le type de données qui devrait le mieux convenir à ton format, les lettres minuscules sont stockées sur seulement 5 bits [pas de bits de poids forts], mais à chaque espace, tu rajoutes 2x8+5=21 bits; donc tu ne gagnes par rapport au format brut que [n étant la longueur moyenne d'un mot] si (21+n*5)<(n*8) soit n*3>21 soit plus de 7 lettres par mot )

OK j'ai compris cette fois, mais ce que tu appelles bit de poids fort c'est en fait le numéro du bit le plus fort à 1 (pour moi, le bit de poids fort c'est le bit 7, alors forcément je ne pouvais pas comprendre).
Ceci dit j'ai toujours la même question, avec un système comme ça tu n'as pratiquement aucune chance de tomber juste sur la fin d'un octet à la fin de chaque séquence... tu considères tout ton fichier comme une suite de *bits* ??
(si c'est le cas je ne vois pas pourquoi tu t'embêtes à mettre trois bits nuls quand l'octet est à 0, tu pourrais aussi bien les virer si tu n'as pas d'alignement ?)
Enfin ça me semble quand même bien compliqué pour des résultats pas très bons ? (a priori)

Au fait :

Le gros point noir de ma méthode c'est que le temps de compression est assez lent et demande un fichier temporaire

Tu rigoles? C'est un algorithme parfaitement linéaire, et d'ailleurs je me demande si c'est pas au moins aussi rapide de compresser que de décompresser


Et ta méthode, dans le pire des cas, au lieu de se comporter comme une compression raisonnable et d'avoir un fichier 5% plus gros en sortie, sort un fichier 2x plus gros : si une partie du fichier se compresse mal, tu as perdu tout ce que tu avais gagné autrement. En plus, là, à chaque caractère, tu perds 4 bits pour pouvoir gérer 16 caractères à la suite : mais ce cas-là est extrêmement rare (et quand il arrive, on n'est plus à 1 ou 2 bits près), il vaudrait mieux prendre un code à longueur variable qui favorise les petits nombres.

Lys> je pense qu'il considère le fichier comme une suite de bits, oui (c'est comme ça que fait la majorité des compresseurs, sauf si tu veux vraiment une décompression ultra-rapide et que tu peux sacrifier un peu sur le taux de compression)

je pense qu'il considère le fichier comme une suite de bits, oui (c'est comme ça que fait la majorité des compresseurs, sauf si tu veux vraiment une décompression ultra-rapide et que tu peux sacrifier un peu sur le taux de compression)

Ah je ne savais pas #débarque#

Bah tu peux aussi considérer le fichier comme un minuscule sous-intervalle de [0;1] (d'amplitude 2^-nombre de bits d'entrée) et utiliser un codage entropique : c'est encore plus efficace (ça revient à prendre un nombre "fractionnaire" de bits pour chaque valeur, et pas entier), mais c'est plus lent et un peu plus lourd à implémenter. Mais je ne pense pas que ça soit ce que cherche geo².

Quand il y a une suite de 0, les 3 bits de bit de poids fort ne servent à rien est n'existe pas.
Ma méthode de compression peut paraître vraiment nul et ne compresse rien voir faiblement or c'est faux, bien sûr dans le cas d'un texte pure oui mais dans le cas des fichiers avec format type word, bitmap, base de données, data... il s'en sort bien, par exemple une base de données de 1,5 Mo il l'a compressé à 66% soit taille final de 500 Ko. Pour la décompression elle est rapide contrairement à ce qu'on peux penser.

Bon bien sûr il faut revoir ce format et je dois trouver un truc bien plus puissant...
Mon but et de trouver une compression linéaire donc compression en temps réel mais avec un taux résonnable et une décompression ultra rapide.

En tout cas je présume que ton algo s'en sort bcp moins bien que LZW, non? Et que RLE puis Huffman? (en faisant pas trop n'importe quoi avec RLE, hein)

Pour la décompression elle est rapide contrairement à ce qu'on peux penser.

Je serais curieux de savoir qui pense ça

lol.

Ca donne quoi alors ?
S'il s'en sort moins bien que RLE, il y a des chances que Huffmann se passe mal - et je ne parle même pas de LZW.
Si tu veux t'amuser à esplorer des trucs, regarde Shannon Fano, c'est asymptotiquement équivalent à Huffmann. Ou le codage arithmétique/entropique.

Il y a un bouquin là-dessus sur eMule : the Data Compression Book, ils parlent même des fractales pour compresser.

Bah j'avance, je suis sur l'algo de compression LZW qui fonctionne très bien et donne de bon résultat malgré que je bloque un peu pour lé décompression, j'ai quelques problèmes.
Pour Huffman je l'ai réalisé et ça focntionne bien aussi, moins bien que LZW pour les taux mais les résultats sont interessant. Néanmoins mon algo de compression LZW est super leeeeeeennt, 2 mins pour compresser 2 Mo
Par contre je ne pense pas faire l'algo Shannon Fano car ça me semble inutile, les résultats sont très proche de Huffman?

Merci pour le bouquin je vais voir si je peux me le procurer.

Les algos niveaux taux de compression du plus faible au plus puissant:

RLE, Mon format, Huffman, LZW

RLE tourne entre -50% et 20%
Mon format entre -5% et 30%
Huffman entre 20% et 50%
LZW entre 30% et 60%

Au fait, pour LZW, extrait du site d'Unisys :

The U.S. LZW patent expires June 20, 2003, the counterpart Canadian patent expires July 7, 2004, the counterpart patents in the United Kingdom, France, Germany and Italy expire June 18, 2004, and the Japanese counterpart patents expire June 20, 2004.

Donc à moins de payer une licence ou de ne distribuer ton prog qu'après le 18 juin, tu n'as pas le droit d'utiliser LZW pour l'instant

./14> LZW n'est pas plus efficace que ça? Normalement si c'est bien implémenté, ça doit être bien plus efficace que Huffman...

Lol il est bien plus efficace que Huffman mais pas avec BWT+LZW, BWT+Huff donne de sacrés résultats.

Oui, avec la BWT c'est clair que tu vas avoir de bien meilleurs résultats (cf bzip2). Mais de toute façon si tu veux un truc qui bouffe pas trop de RAM et qui soit rapide, tu peux faire une croix dessus...

Je vais voir quand j'aurais finie mon programme quelles est la meilleur compression pour ce que je veux faire sur TI. Je pense à du DCT mais à essayer.
En tout cas mon logiciel arrive à la cheville de Winzip certaines fois mais bien sûr y a un truc qui le rend très lent à la compression en LZW

Pour Shannon-Fano, c'est moins bon que le Huffman de manière systématique, donc oublie. C'est juste pour faire un peu moins de calculs que dans la compression Huffman, en sacrifiant la qualité de compression.

Mouerf, la génération de l'arbre prend vraiment un temps négligeable => excuse pipo

Clair, c'est vraiment nul comme méthode. Je ne sais pas pourquoi ils perdent leur temps à nous apprendre cette méthode à la con.

Kevin Kofler
: Clair, c'est vraiment nul comme méthode. Je ne sais pas pourquoi ils perdent leur temps à nous apprendre cette méthode à la con.

Parce qu'elle a été trouvée en premier, que la génération de l'arbre est presque plus logique, qu'assymptotiquement, il fait le travail d'Huffman, ...

La DCT, c'est pour de la compression avec pertes, en général. Sinon, tu passes aux ondelettes entières qui permettent de compresser sans pertes - comme dans le domaine biomédical -, j'ai une publication à ce niveau, c'est intéressant.

Ouai DCT c'est pour les images et le son...

Par contre LZ77+Huffman donne Winzip??? C'est quoi au juste le LZH?, j'ai aucune infos là dessus.

lol je vois que de ne pas faire Shannon-Fano n'est pas une grande perte.

Par contre je sais qu'il existe 3 algos diffrent pour Huffman, c'est juste une gestion de la table je crois?
non adaptative.
adaptative
semi-adaptative

Pour ma part j'ai réalisé la méthode adaptative, c'est un bon choix où y a possibilitée de faire mieux er équilibrer l'arbre apporte un avantage considérable?

geogeo :
Ouai DCT c'est pour les images et le son...

Par contre LZ77+Huffman donne Winzip??? C'est quoi au juste le LZH?, j'ai aucune infos là dessus.

lol je vois que de ne pas faire Shannon-Fano n'est pas une grande perte.

Par contre je sais qu'il existe 3 algos diffrent pour Huffman, c'est juste une gestion de la table je crois?
non adaptative.
adaptative
semi-adaptative
Pour ma part j'ai réalisé la méthode adaptative, c'est un bon choix où y a possibilitée de faire mieux er équilibrer l'arbre apporte un avantage considérable?

LZW, c'est la compression par dictionnaire, mais il y a eu le LZ77 et le LZ78.
Non adaptatif = création de l'arbre au départ
adaptatif = création de l'arbre en cours de compression avec l'ajout d'un caractère d'échappement dans l'arbre
semi = on vide l'arbre régulièrement - comme les dictionnaires dans d'autres méthodes d'ailleurs

Equilibrer l'arbre d'apporte rien, il faut qu'il soit déséquilibré pour que le codage d'un caractère prenne moins de place - tu calcules la longueur moyenne par somme longueur du caractère * probabilité d'apparition, le but est que ce soit < 8 bits, pour un caractère -

Ouai ok je vois. Mais rien sur le LZH

geogeo :
Ouai ok je vois. Mais rien sur le LZH

jamais entendu parler...

LZH=LZ+Huffman

LZ77?? et non LZW.

Pour la lenteur j'ai corrigé le problème en achant la recherche du dictionnaire.

Oui, LZ77.