Compression Huffman avec LZ77 - Page 1

En faisant des recherches sur le forum je suis tombé sur ce topic très interessant sur la compression de Huffman sans création d'une table dans le fichier:
topics/1919-compression-avec-huffman-methode

Mon problème majeur c'est que je voudrais combiner LZ77 avec Huffman et ainsi coder les caractères qui n'ont pas plus être compressé avec la méthode de Huffman or je ne trouve aucune infos me permettant de réaliser un Huffman sans table ou encore mieux le dérivé de Huffman utilisé dans la compression LZH.

Après avoir regardé le sujet de Thibaut, je doute qu'un tableau soit efficace ainsi que la méthode proposé dans mon cas, je sais vraiment pas car je ne possède pas d'infos sur le sujet.

Si vous pouvez m'éclairer sur le sujet je pourrais réaliser le bon dérivé de Huffman pour être combiné avec le LZ77.

Je vois pas le pb...

Normalement un truc compressé en LZ77 ressemble à : 'b' 'l' 'a' '-' REPEAT(-4,3) '!'
Tu as juste à compresser ça en Huffman (l'alphabet faisant 257 caractères, et le (x,y) dans REPEAT(x,y) étant codé littéralement), et le tour est joué...

OK donc faire du vrai LZ77 parce que en fait j'utilise le LZSS et donc pour toi je devrait tout coder littéralement en Huffman. Bizarre comme idée mais je vais essayer mais je doute d'avoir de bon résultats.

Tu parles de LZ77+Huffman dans ta question, je vais pas te répondre à propos de LZSS

Et quelle est la méthode "non bizarre" pour toi? (pour LZ77)

Bah le LZSS est appelé couramment LZ77 car le LZ77 n'est plus utilisé c'est comme le LZ78 qu'on nomme souvent LZW...

Biarre car c'est ce que je fais pour les simples caractère et pour les répétitions c'est codé de façon presque maximal en nombre de bits de plus si le fichier ne possède pas de chiffres, son codage dans l'arbre de Huffman sera sur un nombre de bits assez important...

Bref je viens d'essayer et j'ai les même taux à quelques octets prêt.

Bah le LZSS est appelé couramment LZ77 car le LZ77 n'est plus utilisé c'est comme le LZ78 qu'on nomme souvent LZW...

Oui, je me souvenais plus de ce que c'était et ta phrase laissait suggérer que ct différent ("faire du vrai LZ77 parce que en fait j'utilise le LZSS"), mais effectivement google a l'air de trouver ça pareil...

Biarre car c'est ce que je fais pour les simples caractère et pour les répétitions c'est codé de façon presque maximal en nombre de bits de plus si le fichier ne possède pas de chiffres, son codage dans l'arbre de Huffman sera sur un nombre de bits assez important...

A la limite l'orthographe approximative ça passe, mais là ta phrase ne veut franchement rien dire et est quasi dénuée de ponctuation... Fais un effort

Bref je viens d'essayer et j'ai les même taux à quelques octets prêt.

Bah évidemment, ça dépend de la façon dont tu codes et de la nature du fichier. Si la distribution de caractères non compressés est la même que celle des caractères compressés, évidemment il n'y a strictement aucun gain. Si ce n'est pas le cas, tu y gagnes (et éventuellement le compresseur peut faire en sorte d'avoir un seuil de longueur minimale acceptable pour une répétition LZSS plus faible pour les lettres apparaissant rarement dans le texte original, ce qui peut accentuer le gain).

Il y a 3 modes de compression LZX, si le me souviens bien... le LZ77, le LZ78 et le LZW. Welch n'a pas travaillé sur le 78, mais a déposé un brevet pour son LZW, je crois, à vérifier.

Oui en effet il y a un brevet pour le LZW.
Pour que Huffman compresse il faut en fin de compte que je réalise le LZ77 et que les données soient écrites sur des octets, cela signifie un dico de 65536 caractères et un buffer de 256 caractères. Je vais voir ce que ça donne.

et que les données soient écrites sur des octets

Bah non, justement, si tu as 257 valeurs...

Pourquoi 257 valeurs? La table ASCII fait 256 valeurs Je pige pas désolé.
De plus MOHAA m'as dit qu'un Huffman progressif serait adapté mais comment réaliser un Huffman ne demandant pas de table dans le fichier ça me paraît impossible. Je vais me renseigner sur le Huffman progressif et réaliser le LZ77 seul.

Le code "répétition" est la 257^ème valeur.

(et on peut aussi affiner en prenant 256+n valeurs en prenant la convention "code 256+n" = "répétition de n+2 caractères")

J'ai trouvé des infos sur le net et je pense être capable de réaliser le huffman progressif mais reste un point que je ne comprend toujours pas. Je parle du LZSS.

Si j'ai 257 valeurs, Huffman travaillera sur le codage de 9 bits ok mais si je tombe sur le cas où j'ai:
Bit témoin+pos+size il faut que ça fasse au minimum 18 bits, bref que ça soit divisible par 9?

Rien compris, encore une fois...

Désolé mais j'ai rien compris à ton histoire de valeurs supplémentaires.

caractère a => 'a'
caractère 123 => 123
REPEAT(offset,5) => 254+5 avec comme donnée auxiliaire "offset"

Ben, au lieu de coder un caractère de {0,1,...,255}, tu codes un caractère de {0,1,...,255,rep₂,rep₃,...,rep_nmax} (que tu peux représenter par sa bijection sur {0,1,...,254+n_max} si tu veux).

(post croisé)

Ah ok je pige mieux, donc Huffman aura une table de codage de 0 à 254+nmax.

Maintenant pourquoi pas 2 tables de codage? Une pour les caractères ASCII lorsque aucune répétition n'est trouvé et l'autres pour le codage des répétitions?

Mais quand tu rencontreras un code, comment tu sauras de quelle table il vient ?

./18> Quel est l'intérêt, à part que ça compresserait moins bien? (surtout pour les fichiers très compressibles ou très peu compressibles)

./19> Bah ça l'obligerait à mettre un bit en plus, c bien le pb...

Mais quand tu rencontreras un code, comment tu sauras de quelle table il vient ?

Bah par le principe du LZSS avec le bit témoin renseignant si ce qui suit est un simple caractère ou une répétition.

./18> Quel est l'intérêt, à part que ça compresserait moins bien? (surtout pour les fichiers très compressibles ou très peu compressibles)

Bien au contraire bien sûr il faut du Huffman progressif, le but est le suivant.

On a 2 arbres de huffman donc 2 tables de codage, une pour les caractères qui n'ont pas plus être codé par LZSS et l'autre pour les offset+size ainsi Huffman sera forcément efficace à cause des données qu'il traite et qu'il codifie au fur et à mesure de la lecture du fichier.

Bon, j'abandonne...

lol après reflexion le bit est inutile puisque suivant le code que j'aurais je serais si c'est un simple caractère ou le couple pos, size.

Donc en fait j'ai une table de 257 valeurs ou la valeur 256 ce nomme REP, je code tout sur 9 bits. A chaque fois que je compresse un caractère ou une définition dans ma table de caractères j'ajoute un à la fréquence voulu puis je reconstruit l'arbre, une fois l'arbre codifie je code le caractère sur le nombre de bits voulu avec le code de Huffman. La décompression est simple, l'arbre ce reconstruit petit à petit comme à la décompression, après reconstruction d'un caractère, si je vois 256 soit REP j'ai à faire au couple pos, size sinon à un simple caractère.

On peux optimiser la compression en compressant les couples size et pos pour cela on étant la table ce que je trouve un peu inutile car créer une autre table serait plus efficace.

Voilà ce que j'ai compris.

Comment afficher un nombre sur 64 bits non signé et un nombre à virgule flotante du type, long long et double?

Comment pour des questions incompréhensibles poser, geogeo fait-il ? (je comprends bien les 9 premiers mots, mais après... )

Exemple:

double nombre1;
long long nombre2;
long double nombre3;

Comment afficher ses nombres à l'écran avec la fonction printf?

Pour afficher un nombre type double je fait printf ("%Lf\n", nombre1); mais l'affichage bug, j'ai des 0 partout avec des nombres négatif.

Comment afficher c
es nombres à l'écran avec la fonction printf?

Euh.... %f ?
au passage, je me permets de corriger la phrase :)

Les nombres sont tronqués.

ba tu rajoutes .x (x est la précision) entre % et f