Compression avec Huffman : méthode - Page 1

J'adresse ce topic à ceux qui se demande comment marche la compression de donnés (en l'occurence Huffman), mais surtout à ceux qui savent. Car la question du topic est "Ma méthode est-elle au moins aussi rapide que la traditionnelle manipulation d'arbres ?", à moins que (ça me ferait chier) j'ai une fois de plus réinventé la roue.

Conservez-le réduit dans votre barre des tâches, il vaut mieux le lire hors-connexion

La présentation de l'algorithme d'Huffman passe souvent (toujours ?) par la manipulation d'un arbre binaire. Avec moi elle va passer par la manipulation de tableaux, on oublie complètement les arbres ! On revient exactement à la même chose, mais en plus simple, voir... plus rapide ?

Voyons comment en compressant une suite de 38 octets, car rien ne vaut un exemple.


Claire fut l'éclair
en joli vent d'été
(c'est nul comme jeu de mots, mais on va faire avec)

un espace) f - 1 u - 1 t - 3 ' - 2 c - 1 n - 2 j - 1 o - 1 v - 1 d - 1

On compte la fréquence d'apparition de chaque octet, jusque là, rien de nouveau :C - 1
l - 4
a - 2
i - 3
r - 2
e - 6 (je considère les é comme des e)
_ - 6 (je considère le retour à la ligne comme

- 6 _ - 6 l - 4 i - 3 t - 3 a - 2 r - 2 ' - 2 n - 2 C - 1 f - 1 u - 1 c - 1 j - 1 o - 1 v - 1 d - 1Pour plus de clarté, on trie par ordre décroissant d'occurences, mais ce n'est pas obligatoire pour la compression :e
La nouveauté commence ici. On construit 2 tableaux ; un contient les octets surmontés de leur fréquence, l'autre les octets seuls (seuls pour l'instant -

) :| 6 | 6 | 4 | 3 | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------------------------------------------------------------------+
| e | _ | l | i | t | a | r | ' | n | C | f | u | c | j | o | v | d |

e - 
_ - 
l - 
i - 
t - 
a - 
r - 
' - 
n - 
C - 
f - 
u - 
c - 
j - 
o - 
v - 
d

On cherche les deux plus faibles fréquences. Comme on vient de trier, ce sont forcément les deux dernières colonnes. On déplace la colone de plus faible fréquence vers l'autre. Si elles sont égales, ont choisit de déplacer la plus à droite vers l'autre.
| j | o | v | | | | | | | | | | | | | | | | | d |

Enfin, on additionne leurs fréquences. Regardez la dernière colonne du tableau :| 6 | 6 | 4 | 3 | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 |
+---------------------------------------------------------------+
| e | _ | l | i | t | a | r | ' | n | C | f | u | c 

Dans notre deuxième tableau vide, on inscrit un 1 en face des octets déplacés, et un 0 en face de ceux dont la colonne a reçu nos migrants (pour l'instant on n'a qu'un seul octet par colonne 1

)e - 
_ - 
l - 
i - 
t - 
a - 
r - 
' - 
n - 
C - 
f - 
u - 
c - 
j - 
o - 
v - 0
d - 

- r - ' - n - C - f - u - c - j - 0 o - 1 v - 0 d - 1

On cherche les deux plus petites fréquences, et on recommence la manip :| 6 | 6 | 4 | 3 | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 2 | 2 |
+-----------------------------------------------------------+
| e | _ | l | i | t | a | r | ' | n | C | f | u | c | j | v |
|   |   |   |   |   |   |   |   |   |   |   |   |   | o | d |


e - 
_ - 
l - 
i - 
t - 
a 

- 0 c - 1 j - 0 o - 1 v - 0 d - 1

En continuant, on arrive rapidement à :| 6 | 6 | 4 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
+---------------------------------------------------+
| e | _ | l | i | t | a | r | ' | n | C | u | j | v |
|   |   |   |   |   |   |   |   |   | f | c | o | d |

e - 
_ - 
l - 
i - 
t - 
a - 
r - 
' - 
n - 
C - 0
f - 1
u

Attention, la suite peut paraître moins évidente si vous dormez. | | | | | | | | | | d |

 Ce sont bien des colonnes qu'on déplace :| 6 | 6 | 4 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 4 |
+-----------------------------------------------+
| e | _ | l | i | t | a | r | ' | n | C | u | j |
|   |   |   |   |   |   |   |   |   | f | c | o |
|   |   |   |   |   |   |   |   |   |   |   | v |
|   |  

Donc ce sont tous les octets des colones concernées par le déplacement qui sont affectés d'un 1 ou d'un 0. Voyez en bas de la liste, j & o ont reçu un 0, v & d un 111

 :e - 
_ - 
l - 
i - 
t - 
a - 
r - 
' - 
n - 
C - 0
f - 1
u - 0
c - 1
j - 00
o - 10
v - 01
d - 

C | | f | | u | | c | | j | | o | | v | | d |

La manip se termine lorsqu'il ne reste plus qu'une colonne :| 38 |
+----+
| e  |
| _  |
| i  |
| t  |
| l  |
| a  |
| r  |
| '  |
| n  |
| 

- 00111 o - 10111 v - 01111 d - 11111

Les déplacements ont donné cette liste :e -   000
_ -   100
l -   110
i -  0010
t -  1010
a -  0001
r -  1001
' -  0101
n -  1101
C - 00011
f - 10011
u - 01011
c - 11011
j 

Lisez les codes de droite à gauche, c'est magique (la prédécrémentation n'est pas plus lente que la postincrémentation, mais on peut inverser les listes de bits si ça gêne). A chaque octet on a la correspondance binaire compressée
Le poême compressé :
110000111000010010010000011100111010010100101110100001101101110000100100100100010110011110011101011010011110000101101010011111110100000101000

C'est beau non ?


Si jamais ce n'était pas plus rapide que le travail sur arbres, voyons la décompression, il se pourrait qu'on y gagne, je ne sais pas. Tout en image, la simplicité ne demande pas d'explication :
110000111000010010010000011100111010010100101110100001101101110000100100100100010110011110011101011010011110000101101010011111110100000101000

e - 000
_ - 100
l - 110
i - 0010
t - 1010
a - 0001
r - 1001
' - 0101
n - 1101
C - 00011
f - 10011
u - 01011
c - 11011
j - 00111
o - 10111
v - 01111
d - 11111


110000111000010010010000011100111010010100101110100001101101110000100100100100010110011110011101011010011110000101101010011111110100000101000

e - 000
_ - 100
l - 110
i - 0010
t - 1010
a - 0001
r - 1001
' - 0101
n - 1101
C - 00011
f - 10011
u - 01011
c - 11011
j - 00111
o - 10111
v - 01111
d - 11111


110000111000010010010000011100111010010100101110100001101101110000100100100100010110011110011101011010011110000101101010011111110100000101000

e - 000
_ - 100
l - 110
i - 0010
t - 1010
a - 0001
r - 1001
' - 0101
n - 1101
C - 00011
f - 10011
u - 01011
c - 11011
j - 00111
o - 10111
v - 01111
d - 11111


110000111000010010010000011100111010010100101110100001101101110000100100100100010110011110011101011010011110000101101010011111110100000101000

e - 000
_ - 100
l - 110
i - 0010
t - 1010
a - 0001
r - 1001
' - 0101
n - 1101
C - 00011
f - 10011
u - 01011
c - 11011
j - 00111
o - 10111
v - 01111
d - 11111


110000111000010010010000011100111010010100101110100001101101110000100100100100010110011110011101011010011110000101101010011111110100000101000[pre]e - 000 _ - 100 l - 110 i - 0010 t - 1010 a - 0001 r - 1001 ' - 0101 n - 1101 C - [b]00011[/b] f - 10011 u - 01011 c - 11011 j - 00111 o - 10111 v - 01111 d - 11111 On s'arrête car on est arrivé à la fin d'une liste de bits, ici, la liste du [i]C[/i] : le premier octet est donc un [i]C[/i]. Vous l'avez compris ; on part du haut du tableau, et si le Nième lut ne correspond pas au Nième bit de la liste en face sur laquelle on est, on descend jusqu'à trouver une correspondance. Et ainsi de suite jusqu'à ce qu'on atteigne la fin d'une liste. Qu'est ce que vous pensez de cette méthode ? Si c'est une pauvre merde, argumentez, et puis ben... soyez gentils, expliquez moi ou donnez-moi des ULR sur la structure de donnés à utiliser pour les arbres, et la façon de s'en servir car je n'ai rien compris aux tutoriels que j'ai lu (c'est pour ça que j'ai dû inventer ma propre implémentation). Merci ! [edit]Edité par Thibaut le 26-09-2001 à 18:32:16[/edit]

Je crois k tu viens de battre le record du post le plus long à lire et à comprendre

felicitations

Merde, ne dérivez pas. Elle est franchement clair e mon explication. Lisez-le en prenant soin de bin voir chaque mot et matez les exemples qui sont là pour vous aider à piger. C'est sûr que ce n'est pas un exposé à lire en 1 minute.

justement, c'est ca qui est chiant! C'est le genre de truc que tu as envie de mettre de côté et de lire après...

C'est pas ce que j'ai dit dans l'intro ???????

"Conservez-le réduit dans votre barre des tâches, il vaut mieux le lire hors-connexion"

c interressant, mais je peux pas juger parce que je ne connais pas.

lzw : c'est pas le truc breveté ?
c'est plus compliqué qu'Huffman ?
c'est réellement plus puissant que le Huffman progressif ?
Mais j'aimerais avoir l'opinion des connaisseurs sur ma méthode.

LZW est completement différent... LZW77 permet de compresser/decompresser sans aucune ressource, mais on peut accelerer sensiblement la compression en utilisant un arbre binaire ou une table de hashage (mais ce n'est pas obligatoire).
Lequel est le plus performant ? Tout dépend des données que tu compresses... si il y a certains caracteres qui se répetent beaucoup plus que d'autres, huffman est quelques fois meilleur. Sinon, si ce sont des chaines qui se repetent, c'est LZW. En general, c'est LZW qui est meilleur.
Les meilleurs compresseurs actuels (gzip, bzip2, etc...) utilisent les deux. Une variante du lzw d'abord (il y en a plein) et ensuite huffman pour coder certaines données qui composent le résultat de LZW, tout cela segmenté par blocks pour éviter le plus possible l'expansion.

arf, le ziph est bien meilleur puisqu'il recompresse un fichier deja compressé!
En plus, la recompression peut aller jusqu'à 20% en plus de gagné par rapport au fichier deja compressé et ce même si le fichier à été compressé au maximum!

>arf, le ziph est bien meilleur puisqu'il recompresse un fichier deja compressé!

Ouais ouais, jusqu'à ce que le fichier soit réduit à 0 octet... pourquoi est-ce que tout le monde ne l'utilise pas, on gagnerai carrément beaucoup de place !!!

idiot, après ca, j'ai jamais réussi à encore le recompresser (à chaques fois, il reprends de la place)!
et quand je dis recompréssé, c à partir d'un zip, arj, rar, ace, etc... et non pas d'un ziph!
Et comme je l'ai deja dis au dessus, si je re-recompresse un ziph, il reprends de la place!

comme si que je le savais pas ? (cf. )
et le ziph est bien meilleur que quoi ???

ke les autres compresseurs au niveau de la re-recompression!

Moi j'aimerais savoir si la méthode d'encodage que je présente est plus rapide ou pas que la traditionnelle manipulation d'arbres.
Je ne vous demande pas si LZxx c'est mieux...

Je comprend pas que vous n'ayez pas compris la question.

alors ?
[edit]Edité par Thibaut le 27-09-2001 à 17:04:40[/edit]

>c'est plus compliqué qu'Huffman ? c'est réellement plus puissant que le Huffman progressif ?

>Je ne vous demande pas si LZxx c'est mieux...

Il n'y a pas une contradiction là ?

Et pour répondre à ta question originelle, je pense que les structures de données pour ta méthode prennent peut-etre moins de place (en admettant qu'un caractere ne puisse pas etre codé sur plus de 32 bits, ce qui n'est pas sur (?)), mais n'est pas plus rapide que de manipuler un arbre. Les arbres justement c'est pas fait pour etre chiant, c'est fait pour etre rapide en dynamique. (cf. cours d'algo)
Voila j'ai répondu, mais comme je ne suis pas un expert je ne pense pas que ça vaille grand chose
[edit]Edité par Nitro le 27-09-2001 à 17:22:19[/edit]

G étudié le système de compression, mais je me demande (pt'être que j'ai pas tout compris), une fois le fichier compressé, que devient le tableau de concordance |Caractère-->code|
Parce que sinon, le fichier compressé est plus gros qu'à l'origine!! si on réunit les 2!

Oui il faut réunir les deux, et il y a une méthode spéciale pour construire l'arbre qui fait qu'on peut stocker ce tableau de maniere tres efficace (du style 4 bits par caractere si je me souviens bien), méthode utilisée par zlib (sous Linux).

je vois!

de plus on peut utiliser RLE pour compresser ce tableau et gagner encore de la place

et après ca devient compliqué!!
C cool! t'as une doc dessus?

Le Huffman progressif n'a pas besoin de stocker le tableau dans le fichier. Et en plus il compresse mieux

>Le Huffman progressif n'a pas besoin de stocker le tableau dans le fichier

Le tableau est en fait stocké dans le stream, le gain est faible (je crois meme qu'on y perd) par rapport à la méthode de zlib.

Le tableau n'est pas stocké, rien nada !
L'explication tient dans un mot important du nom de la méthode : progressif. J'ai la flemme d'expliquer, cherche sur Internet si tu veux savoir comment ça marche.
Et on y gagne, surtout sur les gros fichiers hétérogènes (justement l'ennemi de la méthode d'Huffman classique).

Euh, on doit pas connaitre le meme Huffman progressif alors... dans les algos que j'ai, les nouveaux caracteres sont stockés dans le stream quand ils apparaissent.

Je crois aussi. Il y aurait donc 2 Huffman P ?

Le tient semble moins efficace puisqu'il stocke. Est-ce qu'il se "débarrasse" des octets n'apparaissant plus à un endroit donné du fichier ? Le mien, oui.

>>lzw : c'est pas le truc breveté ?
>>c'est plus compliqué qu'Huffman ?

Thibaut, je sais que tu n'aimes pas l'anglais, mais va voir ça quand meme !!!

ça parle de tout ça :

Huffman Compression
Compression FAQ - Part 1
Compression FAQ - Part 2
Compression FAQ - Part 3
16-bit RLE Compression
8-bit RLE Compression
Arithmetic Compression
ARJ Extractor
Simple Compression using an LZ buffer
Data Compression Algorithms of LARC and LHarc
Limpel-Ziv algorithm
LZW Compression Algorithm

c en partie pour toi que j'av posté ce lien dans ce topic
[edit]Edité par Pen^2 le 29-09-2001 à 17:13:17[/edit]

Merci c'est cool

Je l'ai mis dans mes bookmarks, sinon y'a rien sur les Huffman progressifs dedans. Tu as une URL sur ton HP Nitro ?

meme ds les faqs ?

Ouai j'ai jeté un rapide coup d'oeil ; apparamment il n'y a rien.