Compression Huffman

[Lord Nelson]

Salut,

Comme djes m'a conseillé j’essaie de comprendre comment fonctionne l'algo d'Huffman.
Cependant c'est chaud à comprendre alors je viens vous demander de l'aide

Si quelqu'un pouvait m’expliquer très simplement comme cella fonctionne
bien que j’ai regardé certain site mais ou j'ai rien capté

J'aimerais le reproduire en PureBasic mais il faut que je comprenne comment ça fonctionne pour ça !
Et aussi, y à t-il déjà un code existant que quelqu’un aurais fait ?

Merci d'avance

[G-Rom]

http://fr.wikipedia.org/wiki/Codage_de_Huffman

le but est de compter le nombre d’occurrence de chaque caractère , chaque caractère compose un noeud avec un poids , son poids représente son occurrence , l'arbre est créer à partir des noeuds , les noeuds les plus faible sont les "terminal leaf" et on remonte l'arbre suivant les poids , regarde le schéma sur wiki , il est plus que parlant...

Code : Tout sélectionner

structure node
  char.a
  weight.l
  *parent.node
  *childLeft.node
  *childRight.node
endstructure

a toi de faire le reste.

@++

[djes]

Tu peux commencer par quelque chose de plus simple, sur lequel est en train de plancher un ami . Il s'agit de l'algorithme ByteRun, qui est notoirement utilisé dans le format d'image IFF ILBM (voir là : http://home.comcast.net/~erniew/lwsdk/d ... /ilbm.html).

J'en profite pour traduire vite fait la fin de la doc qui l'explique par un pseudo-code, très simple tu vas voir : l'algo de décompression (voir l'annexe C)

DéCompresseur:
BOUCLER jusqu'à la fin de l'image
LIRE le prochain octet et le mettre dans n
SELECTIONNER n PARMI
[0..127] => copier les prochains octets (n+1) littéralement
[-1..-127] => répliquer le prochain octet (-n+1) fois
-128 => noop (pas d'opération)
FINBOUCLER;

[Lord Nelson]

Désoler mais tous ça c'est du chinois pour moi
Si tu veux bien expliquer c'est quoi le ByteRun

[djes]

Désoler mais tous ça c'est du chinois pour moi
Si tu veux bien expliquer c'est quoi le ByteRun

Pas de souci, et après, essaye de comprendre l'algo ; c'est vraiment le plus simple qui existe.

Alors voilà, regarde ton écran, tu vois des pixels de toutes les couleurs. Parfois, il y en a qui sont de la même couleur.

Exemple :

Rouge-bleu-blanc-blanc-blanc-blanc-blanc-rouge

Sans compression, il y a 8 valeurs à enregistrer.

Si, au lieu de tout enregistrer, on enregistrait différemment les fois où les pixels sont de la même couleur. Ca donnerait, par exemple :

Rouge-bleu-5 fois-blanc-rouge

On n'a plus que 5 valeurs. D'où un gain de 3 valeurs, il y a compression.

Le pseudo-code que je t'ai donné est celui qui sert dans un véritable fichier image (format IFF ILBM) pour interpréter et décompresser les données. L'algo de compression doit juste faire l'inverse...

[Lord Nelson]

Tu sais sa fait des tonnes d’essais que je fais sur les images, rien ne fonctionne !

Sauf un truc (Secret) et j'ai aussi mais sans certitude réussi à compresser une image de pixel totalement aléatoire de 5.49 Mm à 5 Mo !
Mais ça n'as aucun intérêt car ça fonctionne pas pour les autre images sans pixel aléatoire !

J'en est essayé tu sais des choses, j'ai notamment fais un genre que t'as fais là, je compte tous les pixels
identique et je stocke seulement la couleur et le nombre de fois qu'elle apparait, exemple:

124959256 3892942 1484 26 225461265458 254163231 254163231 254163231 254163231 254163231 254163231 254163231 5485262654 4885116
Devient: 124959256 3892942 1484 26 225461265458 254163231.6 5485262654 4885116

Mais..... ça marche même pas !!!, dingue hein !
Quand je compresse le résultat avec un logiciel de compression comme 7-Zip par exemple, les résultat sont encore pire !!!

J'ai aussi fais une variante ou à la place de mettre le nombre de fois qu'apparais la couleur, je remplace tous les autre couleur identique qui suivent par 0
(Avent de faire ça je remplace toutes les couleur 0 de l'image par la couleur 1)

Exemple:

124959256 3892942 1484 26 225461265458 254163231 254163231 254163231 254163231 254163231 254163231 254163231 5485262654 4885116
Devient: 124959256 3892942 1484 26 225461265458 254163231 0 0 0 0 0 0 5485262654 4885116

Ici, j'étais sur que ça fonctionnerais !!!
Mais la encore c'est encore pire !!!

Moi je sais plus quoi faire !
Mais je cherche encore !

[djes]

Ne me dis pas que tu stockes ton image en texte...

[falsam]

Moi je sais plus quoi faire !
Mais je cherche encore !

Pour quelle raison ? pour le fun ?

[Lord Nelson]

Ne me dis pas que tu stockes ton image en texte...

J'ai tous essayé !!!
Texte, Binaire, Byte ou Ascii !

T'as une autre idée toi ?
Si t'as une piste, une idée, hésite pas hein

[falsam]

J'ai tous essayé !!!
Texte, Binaire, Byte ou Ascii !

A mon avis Djes pense qu'il hallucine !

[SPH]

Lord Nelson, tu me fais rire
Attaque toi a un truc plus facile qu'a la compression...

Tiens, fais un casse brique

[djes]

Quand je lis byte, binaire, texte ou ascii, oui, là, j'hallucine. La compression que je t'ai montrée ici fonctionne en moyenne assez bien pour des images qui ont des aplats (une copie d'écran par exemple). Par contre si tous les pixels sont différents, il n'y a rien à gagner. Tu pourrais me montrer le code que tu avais fait ? Il y a peut-être une petite erreur.