LES HUFFMAN DE CPPFRANCE

Messages postés
759
Date d'inscription
samedi 15 mai 2004
Statut
Membre
Dernière intervention
30 janvier 2011
- - Dernière réponse : cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
- 11 juil. 2007 à 17:42
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/38961-les-huffman-de-cppfrance

cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
jeune d'accord.
débutant ... ca se discute (mais pourquoi pas) ...
Ricky_MacElroy
Messages postés
10
Date d'inscription
mardi 10 juillet 2007
Statut
Membre
Dernière intervention
26 mai 2008
-
Pas trop mal pour un jeune débutant, il manque un zeste de clarté dans le code.
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Notons qu'un Huffman sur une image n'aurait d'intérêt que si, effectivement, le champ "data" est bien aligné, et surtout si seulement une poignée de couleurs sont présentes. Or pour ça, une "colormap" ferait bien mieux l'affaire. Je ne pense pas qu'il faille réellement envisager Huffman pour autre chose que du texte ascii ^^.
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
effectivement pour les bitmaps, je prie pour que cela tombe juste, que le header soit aligné sur 3 octets (ie 24 bits), mais je m'en preoccûpe pas trop car si vous voulez comprimer des bitmaps alors il faut faire un prgm specifique dans lequel vous lisez le header ect... le but de cette source était évidemment pas là. Si le header (chunk & compagnie...) n'est pas aligné alors j'aurais 6 fois plus de valeurs de 24 bits avec en moyenne 6 fois moins d'occurences (le 6 provient du 6=3! (factoriel 3) et le 3 provient du 24 bits (car 24=8*3)) donc le fichier sera moins bien zipé
pyrogx
Messages postés
1
Date d'inscription
vendredi 7 février 2003
Statut
Membre
Dernière intervention
5 novembre 2006
-
Moi je dis franchement un grand bravo pour toutes ces comparaisons, très appréciables. De plus, c'est une bonne idée de permettre la compression par blocs de 16, 24 ou 32 bits, car il est vrai que les répétitions peuvent être très nombreuses par blocs, comme avec les images BMP par exemple.

Cependant, ton image est principalement une suite de pixels identiques, donc le RLE (par blocs de 24 bits) est à mon avis plus efficace pour cet exemple. En revanche, pour une autre image BMP (une "vraie"), je pense que huffman marcherait mieux A CONDITION que les blocs de 24 bits tombent bien au bon endroit (début de chaque pixel). As-tu une idée pour faire ça (car avec l'entête qui a une taille variable...) ?

Mais pour en revenir à ton test et ton code, chapeau (à la fois pour le final, mais aussi pour le temps que tu as du prendre)
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Breveté contre les usages commerciaux uniquement, non? Et personnellement, je suis assez hostile au fait qu'on puisse breveter des parties de la connaissance alors ... burn all gifs! Comme si on brevetait l'usage des nombres complexes, ou de la fonction exponentiemme, ou des exponentiations modulaires ... Me parait absurde >_<. Enfin.

Concrètement, LZW existe et est librement documenté, alors pourquoi se priver de s'y intéresser et de réaliser une implémentation? Soit dit en passant, les algos LZ77 et LZ78 (?) faut quasi aussi bien. C'est juste l'arrivée de Welch qui a donné une version brevetée (ce me semble).
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Ah oui et j'ai vu que LZW est breveté? Ca veut dire quoi exactement? La source de ymca2003 est-elle illégale?
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
J'ai trouvé un code de LZW su ce site (celui de ymca2003)
Effectivement taux de compression meilleur, mais le temps lui est beaucoup moins bon sue ceux qu'on a ici

De toute facons il me semble qu'une fois qu'on choisit un algo donné et qu'on s'y tient, on peut optimiser uniquement sur la vitesse de compression/décompression
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Quand on pense que n'importe quelle implémentation baclée de lzw bat tous les codes super raffinés ici ... C'est beau l'algorithmique, mais c'est moche le monde :D.
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
>> vecchio56 :
D'accord vecchio56.
Je mettrais a jour les statistiques (le temps que je les refasse).
Tu deviens (temporairement?) champion de la compression Huffman.
Félicitation !

>> deimoslp :
je suis impatient d'avoir ta version 16 et 24 bits pour
pouvoir comparer, car pour l'instant c'est tout en 8 bits.
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Ah comme ça, oui, effectivement, c'est pareil :).
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Je parle du dernier octet du fichier compressé, indépendemment des codes de huffman
Ce nombre contient en fait le nombre de bits significatifs dans le dernier octet (j'aurais aussi pu stocker le nombre de 0 en trop, ca revient au même)
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Vecchio >> "J'ai une information 'nombre de bit à lire dans le dernier octet'
Cette information est codée sur seulement 3 bits, ca doit donc être ici que je gagne"

Comment tu t'en sors avec 3 bits? Le dernier caractère pourrait être codé sur plus de 8 bits, non? Je pense plutôt que sur 3 bits tu mets le nombre de 0 en trop, non?
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Je connais la taille du fichier compressé (GetFileSize), je sais donc quand je suis dans le dernier octet
Bien entendu, je pars du principe que le fichier est bien formé.
Ce que je stocke exactement, dans le cas d'un fichier non uniforme
-1 bit à 0
-La taille de la table, sur 12 bits
-Le nombre de bits dans le dernier octet sur 3 bits
-La table
-Le fichier compressé
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
vecchio56 tu pourrais me dire ce que tu enregistres exactement
dans ta table, car je ne pense pas que tu puisses d'en tirer
avec seulement le nombre de bits du dernier octet, car le probleme
reste ouvert : comment savoir si c'est le dernier octet ?!?

Sinon pour l'histoire du 2^256 : comme de tout facon on compte
nos occurences sur 32 bits (voire 64) il y a un probleme ...
deimoslp
Messages postés
12
Date d'inscription
dimanche 22 juin 2003
Statut
Membre
Dernière intervention
12 juillet 2007
-
ok on était synchro lol ^^
deimoslp
Messages postés
12
Date d'inscription
dimanche 22 juin 2003
Statut
Membre
Dernière intervention
12 juillet 2007
-
Erratum: il fallait lire 2^256 occurences de 0xff dans mon dernier message.

Et autant dire qu'un tel fichier est beaucoup trop volumineux (> 64000 Go) pour avoir un jour la chance d'être compressé par notre bon vieux huffman ^^.
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Dans ce cas, pour 256 c'est plutot 2^256 occurences non? Dans ce cas ca fait un peu beaucoup (moi je compresse pas les fichiers de plus de 4Go)
Donc dans la réalité, cet arbre n'est jamais construit
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Dans ce cas, pour 256 c'est plutot 2^256 occurences non? Dans ce cas ca fait un peu beaucoup (moi je compresse pas les fichiers de plus de 4Go)
Donc dans la réalité, cet arbre n'est jamais construit
deimoslp
Messages postés
12
Date d'inscription
dimanche 22 juin 2003
Statut
Membre
Dernière intervention
12 juillet 2007
-
Content de voir que je sers de référence lol.
Moi aussi j'ai amélioré mon taux de compression et la rapidité de compression(merci pour l'astuce de l'arbre bit a bit); j'ai également implémenté la compression 16 et 24 bits ... mais je pourrais avoir accés a mon ordi que mardi ... a suivre lol.

Sinon vecchio56, pour le codage a 255 bits, tu prends un fichier avec 1 occurence de l'octet 0x00, 2 occcurences de l'octet 0x01 ... 2^(n) occurences de l'octet 0x(n-1) ... et 256 occurences de l'octet 0xff;
La construction de l'arbre de codage va commencer par la 'mise en commun' des feuilles 0x00 et 0x01 en un noeud, qui aura 1+2=3 'occurences fictives'.
Comme 3<4 ce dernier noeud et la feuille 0x02 seront fusionnées en un nouveau noeud ... etc .. comme 2^0 + 2^1 + ... 2^(n-1) = 2^n -1 on obtiendra bien un arbre de profondeur 255 et un codage de 255bits pour les octets 0x00 et 0x01.
J'espère que j'ai été à peu près clair ^^.
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Si tu veux bien refaire des test aussi :)
Je me suis un peu amélioré, mes temps son comparables à deimoslp
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
J'ai une information 'nombre de bit à lire dans le dernier octet'
Cette information est codée sur seulement 3 bits, ca doit donc être ici que je gagne
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
Si tu n'as pas la taille final, comment resouds-tu le
cas suivant :
a la fin tu lis le dernier bit. Comment sais-tu que c'est
effectivement le dernier alors qu'il y a des 0 pour combler
a 8bits.
Ces 0 la sont peut-etre le code du caractere code par 000...
(autant de 0 qu'il le faut)
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Pour le taux de compression, c'est uniquement la table de huffman quie st plus petite.
Les deux premiers octets on une utilisation un peu spéciale.
Je stocke mon arbre comme toi (une bit pour savoir si noueud ou feuille de manière récursive). J'économise le premier 0, car la racine est toujours un noeud, mais ca ne fait qu'un bit d'économisé
Par contre j'écris pas la taille du fichier, elle ne sert à rien

Sinon j'ai un peu tout modifié. J'ai supprimé toutes les allocations dans le tas (sauf les buffers de lecture/écriture), tout est déclaré en statique
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
Vecchio56,
j'ai refait des testes avec ta nouvelle version, et tu es
plus performant que moi (en "taux" de compression").
Je ne sais pas pourquoi tu as juste un octet de plus
dans la table : j'ai peut etre une idee :
dans certain code j'ai enlever la partie qui enregistait
l'extension du fichier d'origine dans le fichier
destination. Mais j'ai pas fait le menage partout.
Certains entetes de fichiers peuvent encore etre raccourcis.
Pour moi le minimum c'est la taille du fichier initiale,
puis la table de huffman (alors la deux techniques, soit
on enregistre les nombres d'occurrences, soit l'arbre de
huffman, ce qui n'est pas la meme chose, meme si a partir
des statistiques on peut reconstuire l'arbre, or seul
l'arbre est utile pour la decompression) , enfin les
donnees compressees ...
Donc je pense que tu peux grater encore quelques octets.


Je code la table de huffman (c'est l'arbre !) comme suit :
je lis bits apres bits. Si je tombe sur un 1, alors
le noeud courant a deux fils (au debut le noeud courant
est la racine), si c'est 0 alors le noeux courant a aucun fils.
Puisque l'on cherche a construire un arbre de Huffman, le nombre
de fils de chaque noeud est soit 0 soit 2. Si le bits est 1 alors
on lit recursivement l'arbre a gauche, puis l'arbre a droite.
A la fin on aura construit l'arbre en le 'parcourant' de facon
infixe.(ici on oublit les derniers bits pour s'aligner sur
8 bits).Puis apres il reste a faire correspondre a chaque feuille
de l'arbre une caractere. Pour cela on recommence un parcours
infixe, et a chaque fois que l' on tombe sur une feuille
on lit dans le fichier le caractere correspondant.
Ceci est vrai pour la lecture de la table.
Pour l'ecriture c'est plus facile et similaire.


comment as-tu modifie ton algorithme ? (je parle de la
performance en taux de compression et non en temps de calcul)
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
ah!! c'est vrai je me suis replongé dedans. J'ai essayé d'améliorer un peu mon code, mais je comprends pas pourquoi ma fonction de décompression est aussi lente
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Ce benchmark aura en plus eu le mérite de mettre vecchio sur le chemin de perdition qu'est l'optimisation ^^. Et apparemment, tu constitues un bon lièvre, JCDjcd!
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Voici les comparaisons pour un fichier de 30Mo

================================================================
debian-31r2-i386-businesscard.iso
================================================================

* temps de compression du fichier :
( 1) vecchio56 [ U8] : 1218.00 ms
( 2) deimoslp [ U8] : 2485.00 ms
( 3) TheWhiteShadow [ U8] : 3391.00 ms
( 4) oim09 [ U8] : 15484.00 ms
( 5) JCDjcd [ U8] : 19016.00 ms
( 6) mido123 [ U8] : 23641.00 ms
( 7) JCDjcd [U16] : 33047.00 ms

* temps de decompression du fichier :
( 1) deimoslp [ U8] : 3453.00 ms
( 2) TheWhiteShadow [ U8] : 3953.00 ms
( 3) vecchio56 [ U8] : 4610.00 ms
( 4) oim09 [ U8] : 13875.00 ms
( 5) JCDjcd [ U8] : 13906.00 ms
( 6) mido123 [ U8] : 14109.00 ms
( 7) JCDjcd [U16] : 16781.00 ms

* taille de la table de l'algorithme d'Huffman :
( 1) JCDjcd [ U8] : 320 octets
( 2) vecchio56 [ U8] : 322 octets
( 3) TheWhiteShadow [ U8] : 390 octets
( 4) mido123 [ U8] : 808 octets
( 5) deimoslp [ U8] : 859 octets
( 6) oim09 [ U8] : 1280 octets
( 7) JCDjcd [U16] : 147456 octets

* taille du fichier compresse par rapport a celle initiale :
( 1) JCDjcd [U16] : 94.343327 %
( 2) vecchio56 [ U8] : 96.698788 %
( 3) JCDjcd [ U8] : 96.698794 %
( 4) TheWhiteShadow [ U8] : 96.699000 %
( 5) mido123 [ U8] : 96.700311 %
( 6) deimoslp [ U8] : 96.700468 %
( 7) oim09 [ U8] : 96.701797 %

JCDjcd24 et JCDjcd32 n'ont pas assez de mémoire non plus
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Etant donné que mon code générait une table un peu grosse, j'ai modifié ma représentation. (j'ai toujours une table plus grosse que la tienne, je sais pas comme t'a fait. J'irais bien voir mais j'ai vraiment du mal à lire tes codes, je sais pas pourquoi)
J'ai aussi changé quelques trucs car dans le cas ou un code de huffman serait assez long, il y aurait eu des pb d'allocation de mémoire
Si tu veux bien mettre mon fichier à jour, je te l'ai mis ici
http://vecchio56.free.fr/vecchio56.c

J'ai aussi fait des tests sur des gros fichiers (plusieurs Mo), et l'algo de Croqmort ne fonctionne pas (trop de mémoire allouée)
Celui de Malibu23 ne fonctionne jamais chez moi
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Mais peut-on vraiment avoir un fichier qui va faire un arbre de hauteur 255?
deimoslp
Messages postés
12
Date d'inscription
dimanche 22 juin 2003
Statut
Membre
Dernière intervention
12 juillet 2007
-
Félicitations pour tout ce beau boulot ! La comparaison est vraiment intéressante.

vecchio56> la profondeur maximale d'un arbre binaire à 256 feuilles est de 255 (arbre dégénéré); donc théoriquement un caractère peut se coder sur 255 bits au maximum soit 32 octets.
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
J'en profite pour poser une petite question: quelle est le plus grand code de huffman qu'on risque d'obtenir pour un caractère, dans le pire des cas? J'arrive pas à trouver ca...
zeratul67
Messages postés
98
Date d'inscription
mardi 9 avril 2002
Statut
Membre
Dernière intervention
11 mai 2008
-
merci pour le travail accompli :)
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
oué j'ai pas tout corrigé, j'ai pas élucider le problème
de lettre(...);
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
J'ai une erreur dans la fonction compress de Oim09: la variable tampon n'est pas initialisée
L'algo de Malibu123 fait planter le programme en mode release (problème dans la fonction lettre apparemment)
J'ai vu que tu as corrigé pas mal de bugs, tu as vraiment beaucoup de courage!
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
Effectivement t'a fait un gros boulot!
Je suis content mon algo n'est pas le plus mauvais ;)
cs_laurent1024
Messages postés
987
Date d'inscription
mardi 31 mai 2005
Statut
Membre
Dernière intervention
30 août 2012
12 -
Tres bien, et tres courageux de comparer différents codes (+debugger). Pour le benchmark, il manque peut-etre juste un graphique pour voir les resultats d'une manière plus globale.
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
Ben tout est dans la taille de la table
Il y a differente facon d'enregistre la table dans le fichier
Il y a des facons bourrines, et d'autres efficaces

Le taux de compression depend aussi beaucoup de la taille de decoupage
8, 16, 24, ou 32 bits. Par exemple le 24 et 32 bits sont efficaces
pour les bitmaps, mais inefficace pour les autres fichiers

Pour ce qui de ma facon d'ecrire la table :
en fait beaucoup enregistre le nombre d'occurrence, et apres lors
de la decompression du fichier, ils reconstruise l'arbre de Huffman.
Or moi je n'enregistre pas les occurrences car c'est inutile.
Ce qui est utile pour coder/decoder, c'est la forme de l'arbre.
Donc je mets dans le fichier la topologie de l'arbre de la facon
suivante : je lis bit-a-bit le fichier et : si il y a un 1
c'est que le noeud courant a 2 fils, si c'est un zero, c'est une
feuille. Puis apres avoir lu l'arbre, on y fait un parcours infixe, et
des que l'on tombe sur une feuille on lit le caractere correspondant
a la feuille dans le fichier.
Puis c'est tout, on a l'arbre, c'est suffisant, donc c'est fini pour
la table.
Galmiza
Messages postés
573
Date d'inscription
samedi 16 novembre 2002
Statut
Membre
Dernière intervention
9 avril 2008
-
Comment se fait-il qu'il y ait une si grande dispersion des résultats pour les taux de compression alors que le principe de compression est le meme (tri par fréquence d'apparition + création table + création arbre) ?

Sinon, bravo JCDjcd !
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
merci
un peu fatiguant et surtout long ...
de plus quand il y a des BUGs faut les chercher
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Ok. Quand même, bel effort de lire de façon approfondie autant de codes pour les adapter à ton framework de benchmark; C'est très appréciable :).
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
Le code de Croqmort ne propose pas d'interface ave des fichiers.
Il "Hufmanise" pas des fichiers, mais des blocs mémoires, et donc
en ce qui concerne la table, j'ai du ecrire moi meme la table qu'il
fourni dans le fichier, donc c'est pas forcement optimise, mais c'est
juste un octet de plus que la table de oim09, sinon j'ai encore regarde
le code est j'ai vu le probleme :
sa fonction CompactHuffman prend en parametre un pointeur sur
la taille des donnees entrees, ce pointeur pointe apres l'execution
de la fonction sur la taille des donnees sorties, mais le BUG est la :
en fait c'est le nombre de bits et non le nombre d'octets
(comme en entree)
Pour corriger le BUG :
changez : "Estime_Taille(Calc_Tbl,Tbl)"
en : "(Estime_Taille(Calc_Tbl,Tbl)+7)/8"

Il faudrait refaire les tests ... c'est tres long ...
Je le compte comme un BUG de sa part, et non de la mienne
donc je ne fais pas recalculer les perfs car c'est long :
j'execute 100 fois chaque fonction pour avoir le temps d'execution
des fonctions avec 2 chiffres apres la virgule (en ms)
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Absolument génial cette comparaison systématique :). Qu'est-ce qui ne va pas dans le programme de Croqmort ?
deck_bsd
Messages postés
1244
Date d'inscription
jeudi 31 mars 2005
Statut
Membre
Dernière intervention
3 août 2016
1 -
très bonne source :D
wxccxw
Messages postés
759
Date d'inscription
samedi 15 mai 2004
Statut
Membre
Dernière intervention
30 janvier 2011
-
j'aime bien ^^ GJ !