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 wink

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 smile -
) :| 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 wink1
)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 smile
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]
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

2

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

3

felicitations smile

4

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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

5

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...
Cours et tutos Asm: http://membres.lycos.fr/sirryl

6

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"
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

7

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

8

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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

9

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.
So much code to write, so little time.

10

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!

11

>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 !!! grin
So much code to write, so little time.

12

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!

13

comme si que je le savais pas ? (cf. grin)
et le ziph est bien meilleur que quoi ???
So much code to write, so little time.

14

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

15

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]
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

16

>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à ? tongue

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 grin
[edit]Edité par Nitro le 27-09-2001 à 17:22:19[/edit]
So much code to write, so little time.

17

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|confus
Parce que sinon, le fichier compressé est plus gros qu'à l'origine!!sad si on réunit les 2!picol

18

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).
So much code to write, so little time.

19

je vois!eek

20

de plus on peut utiliser RLE pour compresser ce tableau et gagner encore de la place smile
So much code to write, so little time.

21

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

22

Le Huffman progressif n'a pas besoin de stocker le tableau dans le fichier. Et en plus il compresse mieux smile
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

23

>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.
So much code to write, so little time.

24

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).
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

25

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.
So much code to write, so little time.

26

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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

27

28

Merci c'est cool smile

Je l'ai mis dans mes bookmarks, sinon y'a rien sur les Huffman progressifs dedans. Tu as une URL sur ton HP Nitro ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

29

meme ds les faqs ?

30

Ouai j'ai jeté un rapide coup d'oeil ; apparamment il n'y a rien.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.