Les huffman de cppfrance

4/5 (45 avis)

Vue 10 857 fois - Téléchargée 752 fois

Description

Je propose ma version de l'algorithme d'Huffman. J'ai vu qu'il y avait déjà plein de source sur ce site.
Cependant ils decoupent les fichiers par 1 octet. Je propose 4 algorithmes :
decoupage en 8 bits, 16 bits, 24 bits, et 32 bits.
Si vous trouvez un bug, SIGNALEZ-LE !

De plus j'ai pris toutes les sources d'Huffman de ce site, et puis j'ai comparé quatre choses :
- la rapidité de compression
- la rapidoté de décompression
- la taille de la table d'Huffman dans le fichier
- la taille finale du fichier comprimé

Les auteurs des sources comparées sont :
JCDjcd(les 4 algo.), mido23, oim09, Malibu23, Croqmort, Deimoslp, TheWhiteShadow, et vecchio56.
Il manque quelques auteurs :
- Kreator : ne comprime pas tous les fichiers
- GoldenEye : ne comprime pas les gros fichiers
- vieuxLion : le code est en C++, désolé, mais je sais pas faire de C++, que du C ...

Je présente les résultats des comparaisons pour différents fichiers :
- baudelaire.txt : un petit poème de Baudelaire
- nBodyProblem.c : un fichier C (cf. problème des N corps sur ce site)
- HTML.htm : un fichier html (cf. méthode d'Euler sur ce site)
- BITMAP.bmp : image avec deux-trois rectangles et un texte "hello world"
- fractale.bmp : une image d'un fractale (celle de mon pseudo)
- ZIP.zip : un zip, normalement difficilement "comprimable" (cf. jeu de la vie sur ce site)
- JPEG.jpg : un fichier au format JPEG

J'aurais juste trois remarques à faire sur les autres sources d'Huffman :
- la majorité des sources ne libére pas toute la mémoire allouée,
ce qui est grave quand on veut faire des compressions à la suite
- j'ai noté quelques bugs dans les sources non-corrigées !
- beaucoup de programme ne traite pas le cas où le fichier est uniforme (un seul caractere dans le fichier)
dans ce cas là, l'arbre d'Huffman est réduit à sa racine => beaucoup de BUG

Source / Exemple :


==================================================================
 baudelaire.txt
==================================================================

  • temps de compression du fichier :
( 1) mido123 [ U8] : 3.28 ms ( 2) JCDjcd [ U8] : 5.16 ms ( 3) Malibu23 [ U8] : 5.31 ms ( 4) deimoslp [ U8] : 5.63 ms ( 5) Croqmort [ U8] : 5.78 ms ( 6) oim09 [ U8] : 5.94 ms ( 7) vecchio56 [ U8] : 6.88 ms ( 8) TheWhiteShadow [ U8] : 11.57 ms ( 9) JCDjcd [U16] : 14.69 ms (10) JCDjcd [U32] : 15.78 ms (11) JCDjcd [U24] : 18.13 ms
  • temps de decompression du fichier :
( 1) mido123 [ U8] : 3.12 ms ( 2) vecchio56 [ U8] : 4.06 ms ( 3) deimoslp [ U8] : 4.21 ms ( 4) JCDjcd [ U8] : 4.37 ms ( 5) oim09 [ U8] : 4.69 ms ( 6) Malibu23 [ U8] : 5.31 ms ( 7) Croqmort [ U8] : 5.94 ms ( 8) JCDjcd [U16] : 7.81 ms ( 9) JCDjcd [U32] : 8.60 ms (10) JCDjcd [U24] : 9.37 ms (11) TheWhiteShadow [ U8] : 10.62 ms
  • taille de la table de l'algorithme d'Huffman :
( 1) JCDjcd [ U8] : 64 octets ( 2) Malibu23 [ U8] : 66 octets ( 3) TheWhiteShadow [ U8] : 81 octets ( 4) vecchio56 [ U8] : 168 octets ( 5) mido123 [ U8] : 174 octets ( 6) deimoslp [ U8] : 206 octets ( 7) oim09 [ U8] : 250 octets ( 8) Croqmort [ U8] : 251 octets ( 9) JCDjcd [U16] : 457 octets (10) JCDjcd [U24] : 868 octets (11) JCDjcd [U32] : 995 octets
  • taille du fichier compresse par rapport a celle initiale :
( 1) JCDjcd [ U8] : 64.711447 % ( 2) Malibu23 [ U8] : 64.806055 % ( 3) TheWhiteShadow [ U8] : 65.941343 % ( 4) vecchio56 [ U8] : 74.172185 % ( 5) mido123 [ U8] : 74.834437 % ( 6) deimoslp [ U8] : 77.767266 % ( 7) oim09 [ U8] : 82.308420 % ( 8) JCDjcd [U16] : 88.457900 % ( 9) JCDjcd [U24] : 115.894040 % (10) JCDjcd [U32] : 119.110691 % (11) Croqmort [ U8] : 124.124882 % ================================================================== nBodyProblem.c ==================================================================
  • temps de compression du fichier :
( 1) deimoslp [ U8] : 19.53 ms ( 2) vecchio56 [ U8] : 26.09 ms ( 3) oim09 [ U8] : 29.84 ms ( 4) TheWhiteShadow [ U8] : 34.07 ms ( 5) Malibu23 [ U8] : 64.53 ms ( 6) mido123 [ U8] : 66.87 ms ( 7) JCDjcd [ U8] : 87.18 ms ( 8) Croqmort [ U8] : 307.19 ms ( 9) JCDjcd [U16] : 406.88 ms (10) JCDjcd [U24] : 581.25 ms (11) JCDjcd [U32] : 667.34 ms
  • temps de decompression du fichier :
( 1) deimoslp [ U8] : 21.40 ms ( 2) TheWhiteShadow [ U8] : 31.56 ms ( 3) mido123 [ U8] : 33.29 ms ( 4) vecchio56 [ U8] : 42.81 ms ( 5) JCDjcd [ U8] : 47.97 ms ( 6) oim09 [ U8] : 79.22 ms ( 7) JCDjcd [U16] : 92.50 ms ( 8) Malibu23 [ U8] : 144.37 ms ( 9) JCDjcd [U24] : 182.50 ms (10) JCDjcd [U32] : 231.72 ms (11) Croqmort [ U8] : 304.85 ms
  • taille de la table de l'algorithme d'Huffman :
( 1) JCDjcd [ U8] : 122 octets ( 2) Malibu23 [ U8] : 125 octets ( 3) TheWhiteShadow [ U8] : 150 octets ( 4) vecchio56 [ U8] : 330 octets ( 5) mido123 [ U8] : 336 octets ( 6) deimoslp [ U8] : 368 octets ( 7) oim09 [ U8] : 480 octets ( 8) Croqmort [ U8] : 481 octets ( 9) JCDjcd [U16] : 4899 octets (10) JCDjcd [U24] : 20020 octets (11) JCDjcd [U32] : 35849 octets
  • taille du fichier compresse par rapport a celle initiale :
( 1) JCDjcd [U24] : 55.033958 % ( 2) JCDjcd [U16] : 56.508416 % ( 3) JCDjcd [U32] : 57.502543 % ( 4) JCDjcd [ U8] : 67.321106 % ( 5) Malibu23 [ U8] : 67.324387 % ( 6) TheWhiteShadow [ U8] : 67.336855 % ( 7) vecchio56 [ U8] : 67.454969 % ( 8) mido123 [ U8] : 67.459562 % ( 9) deimoslp [ U8] : 67.479904 % (10) oim09 [ U8] : 67.556022 % (11) Croqmort [ U8] : 100.318252 % ================================================================== HTML.htm ==================================================================
  • temps de compression du fichier :
( 1) deimoslp [ U8] : 10.31 ms ( 2) oim09 [ U8] : 13.44 ms ( 3) vecchio56 [ U8] : 14.69 ms ( 4) TheWhiteShadow [ U8] : 18.28 ms ( 5) Malibu23 [ U8] : 21.88 ms ( 6) mido123 [ U8] : 24.84 ms ( 7) JCDjcd [ U8] : 29.22 ms ( 8) Croqmort [ U8] : 94.53 ms ( 9) JCDjcd [U16] : 124.53 ms (10) JCDjcd [U24] : 177.66 ms (11) JCDjcd [U32] : 208.91 ms
  • temps de decompression du fichier :
( 1) deimoslp [ U8] : 10.78 ms ( 2) mido123 [ U8] : 12.97 ms ( 3) vecchio56 [ U8] : 16.72 ms ( 4) JCDjcd [ U8] : 18.13 ms ( 5) TheWhiteShadow [ U8] : 18.44 ms ( 6) oim09 [ U8] : 26.56 ms ( 7) JCDjcd [U16] : 34.84 ms ( 8) Malibu23 [ U8] : 45.31 ms ( 9) JCDjcd [U24] : 63.12 ms (10) JCDjcd [U32] : 80.31 ms (11) Croqmort [ U8] : 95.94 ms
  • taille de la table de l'algorithme d'Huffman :
( 1) JCDjcd [ U8] : 103 octets ( 2) Malibu23 [ U8] : 105 octets ( 3) TheWhiteShadow [ U8] : 127 octets ( 4) vecchio56 [ U8] : 285 octets ( 5) mido123 [ U8] : 291 octets ( 6) deimoslp [ U8] : 317 octets ( 7) oim09 [ U8] : 405 octets ( 8) Croqmort [ U8] : 406 octets ( 9) JCDjcd [U16] : 1944 octets (10) JCDjcd [U24] : 6910 octets (11) JCDjcd [U32] : 12304 octets
  • taille du fichier compresse par rapport a celle initiale :
( 1) JCDjcd [U16] : 52.433657 % ( 2) JCDjcd [U24] : 52.845440 % ( 3) JCDjcd [U32] : 57.202928 % ( 4) JCDjcd [ U8] : 60.704170 % ( 5) Malibu23 [ U8] : 60.708528 % ( 6) TheWhiteShadow [ U8] : 60.747745 % ( 7) vecchio56 [ U8] : 61.091987 % ( 8) mido123 [ U8] : 61.105059 % ( 9) deimoslp [ U8] : 61.161706 % (10) oim09 [ U8] : 61.362151 % (11) Croqmort [ U8] : 100.893285 % ================================================================== BITMAP.bmp ==================================================================
  • temps de compression du fichier :
( 1) deimoslp [ U8] : 24.53 ms ( 2) TheWhiteShadow [ U8] : 56.41 ms ( 3) vecchio56 [ U8] : 65.16 ms ( 4) oim09 [ U8] : 75.16 ms ( 5) Malibu23 [ U8] : 84.53 ms ( 6) mido123 [ U8] : 145.47 ms ( 7) JCDjcd [ U8] : 236.56 ms ( 8) JCDjcd [U32] : 486.56 ms ( 9) JCDjcd [U24] : 623.28 ms (10) JCDjcd [U16] : 823.91 ms (11) Croqmort [ U8] : 1331.25 ms
  • temps de decompression du fichier :
( 1) deimoslp [ U8] : 16.87 ms ( 2) JCDjcd [U32] : 33.91 ms ( 3) JCDjcd [U24] : 36.41 ms ( 4) JCDjcd [U16] : 40.78 ms ( 5) mido123 [ U8] : 43.59 ms ( 6) vecchio56 [ U8] : 47.65 ms ( 7) TheWhiteShadow [ U8] : 55.31 ms ( 8) JCDjcd [ U8] : 57.81 ms ( 9) oim09 [ U8] : 83.90 ms (10) Malibu23 [ U8] : 219.53 ms (11) Croqmort [ U8] : 1346.10 ms
  • taille de la table de l'algorithme d'Huffman :
( 1) JCDjcd [ U8] : 37 octets ( 2) TheWhiteShadow [ U8] : 48 octets ( 3) vecchio56 [ U8] : 98 octets ( 4) mido123 [ U8] : 104 octets ( 5) Malibu23 [ U8] : 105 octets ( 6) JCDjcd [U16] : 126 octets ( 7) deimoslp [ U8] : 132 octets ( 8) oim09 [ U8] : 140 octets ( 9) Croqmort [ U8] : 141 octets (10) JCDjcd [U24] : 371 octets (11) JCDjcd [U32] : 782 octets
  • taille du fichier compresse par rapport a celle initiale :
( 1) JCDjcd [U32] : 8.332945 % ( 2) JCDjcd [U24] : 10.853335 % ( 3) JCDjcd [U16] : 12.100704 % ( 4) JCDjcd [ U8] : 16.763527 % ( 5) TheWhiteShadow [ U8] : 16.764615 % ( 6) vecchio56 [ U8] : 16.772389 % ( 7) mido123 [ U8] : 16.773322 % ( 8) Malibu23 [ U8] : 16.775654 % ( 9) deimoslp [ U8] : 16.777675 % (10) oim09 [ U8] : 16.779541 % (11) Croqmort [ U8] : 100.022544 % ================================================================== fractale.bmp ==================================================================
  • temps de compression du fichier :
( 1) deimoslp [ U8] : 80.31 ms ( 2) vecchio56 [ U8] : 109.38 ms ( 3) oim09 [ U8] : 139.53 ms ( 4) TheWhiteShadow [ U8] : 142.34 ms ( 5) Malibu23 [ U8] : 378.44 ms ( 6) mido123 [ U8] : 442.03 ms ( 7) JCDjcd [ U8] : 493.28 ms ( 8) JCDjcd [U24] : 777.34 ms ( 9) JCDjcd [U32] : 1514.22 ms (10) Croqmort [ U8] : 1733.12 ms (11) JCDjcd [U16] : 1876.57 ms
  • temps de decompression du fichier :
( 1) deimoslp [ U8] : 86.57 ms ( 2) JCDjcd [U24] : 104.22 ms ( 3) TheWhiteShadow [ U8] : 125.78 ms ( 4) mido123 [ U8] : 172.97 ms ( 5) vecchio56 [ U8] : 228.43 ms ( 6) JCDjcd [ U8] : 259.37 ms ( 7) JCDjcd [U16] : 349.06 ms ( 8) JCDjcd [U32] : 404.53 ms ( 9) oim09 [ U8] : 445.47 ms (10) Malibu23 [ U8] : 860.00 ms (11) Croqmort [ U8] : 1714.69 ms
  • taille de la table de l'algorithme d'Huffman :
( 1) JCDjcd [ U8] : 320 octets ( 2) Malibu23 [ U8] : 323 octets ( 3) TheWhiteShadow [ U8] : 390 octets ( 4) vecchio56 [ U8] : 956 octets ( 5) mido123 [ U8] : 962 octets ( 6) deimoslp [ U8] : 992 octets ( 7) oim09 [ U8] : 1280 octets ( 8) Croqmort [ U8] : 1281 octets ( 9) JCDjcd [U24] : 3676 octets (10) JCDjcd [U16] : 17735 octets (11) JCDjcd [U32] : 53465 octets
  • taille du fichier compresse par rapport a celle initiale :
( 1) JCDjcd [U24] : 22.116565 % ( 2) JCDjcd [U32] : 30.851688 % ( 3) JCDjcd [U16] : 45.658911 % ( 4) JCDjcd [ U8] : 77.002022 % ( 5) Malibu23 [ U8] : 77.002609 % ( 6) TheWhiteShadow [ U8] : 77.009770 % ( 7) vecchio56 [ U8] : 77.076216 % ( 8) mido123 [ U8] : 77.077038 % ( 9) deimoslp [ U8] : 77.080442 % (10) oim09 [ U8] : 77.114722 % (11) Croqmort [ U8] : 100.150855 % ================================================================== ZIP.zip ==================================================================
  • temps de compression du fichier :
( 1) deimoslp [ U8] : 20.94 ms ( 2) oim09 [ U8] : 25.47 ms ( 3) TheWhiteShadow [ U8] : 31.56 ms ( 4) vecchio56 [ U8] : 33.59 ms ( 5) Malibu23 [ U8] : 55.00 ms ( 6) mido123 [ U8] : 60.94 ms ( 7) JCDjcd [ U8] : 62.97 ms ( 8) Croqmort [ U8] : 192.18 ms ( 9) JCDjcd [U32] : 1317.82 ms (10) JCDjcd [U24] : 1745.78 ms (11) JCDjcd [U16] : 2045.47 ms
  • temps de decompression du fichier :
( 1) deimoslp [ U8] : 29.22 ms ( 2) mido123 [ U8] : 30.62 ms ( 3) TheWhiteShadow [ U8] : 32.50 ms ( 4) vecchio56 [ U8] : 38.75 ms ( 5) JCDjcd [ U8] : 46.10 ms ( 6) oim09 [ U8] : 73.28 ms ( 7) Malibu23 [ U8] : 121.10 ms ( 8) Croqmort [ U8] : 200.47 ms ( 9) JCDjcd [U32] : 511.56 ms (10) JCDjcd [U24] : 673.90 ms (11) JCDjcd [U16] : 769.53 ms
  • taille de la table de l'algorithme d'Huffman :
( 1) JCDjcd [ U8] : 320 octets ( 2) Malibu23 [ U8] : 323 octets ( 3) TheWhiteShadow [ U8] : 390 octets ( 4) vecchio56 [ U8] : 772 octets ( 5) mido123 [ U8] : 778 octets ( 6) deimoslp [ U8] : 803 octets ( 7) oim09 [ U8] : 1280 octets ( 8) Croqmort [ U8] : 1281 octets ( 9) JCDjcd [U16] : 67424 octets (10) JCDjcd [U32] : 85638 octets (11) JCDjcd [U24] : 87009 octets
  • taille du fichier compresse par rapport a celle initiale :
( 1) JCDjcd [ U8] : 100.342112 % ( 2) Malibu23 [ U8] : 100.345804 % ( 3) TheWhiteShadow [ U8] : 100.423333 % ( 4) vecchio56 [ U8] : 100.893429 % ( 5) mido123 [ U8] : 100.902043 % ( 6) deimoslp [ U8] : 100.931578 % ( 7) oim09 [ U8] : 101.523505 % ( 8) Croqmort [ U8] : 101.581344 % ( 9) JCDjcd [U32] : 150.278120 % (10) JCDjcd [U24] : 168.546640 % (11) JCDjcd [U16] : 175.350726 % ================================================================== JPEG.jpg ==================================================================
  • temps de compression du fichier :
( 1) mido123 [ U8] : 12.04 ms ( 2) oim09 [ U8] : 13.28 ms ( 3) deimoslp [ U8] : 14.53 ms ( 4) TheWhiteShadow [ U8] : 15.94 ms ( 5) Malibu23 [ U8] : 18.28 ms ( 6) JCDjcd [ U8] : 19.22 ms ( 7) vecchio56 [ U8] : 26.72 ms ( 8) Croqmort [ U8] : 47.97 ms ( 9) JCDjcd [U32] : 161.87 ms (10) JCDjcd [U24] : 216.40 ms (11) JCDjcd [U16] : 314.53 ms
  • temps de decompression du fichier :
( 1) mido123 [ U8] : 7.18 ms ( 2) deimoslp [ U8] : 11.72 ms ( 3) vecchio56 [ U8] : 11.87 ms ( 4) TheWhiteShadow [ U8] : 13.59 ms ( 5) JCDjcd [ U8] : 14.22 ms ( 6) oim09 [ U8] : 18.13 ms ( 7) Malibu23 [ U8] : 26.09 ms ( 8) Croqmort [ U8] : 48.75 ms ( 9) JCDjcd [U32] : 68.59 ms (10) JCDjcd [U24] : 89.85 ms (11) JCDjcd [U16] : 127.66 ms
  • taille de la table de l'algorithme d'Huffman :
( 1) JCDjcd [ U8] : 320 octets ( 2) Malibu23 [ U8] : 323 octets ( 3) TheWhiteShadow [ U8] : 390 octets ( 4) vecchio56 [ U8] : 788 octets ( 5) mido123 [ U8] : 794 octets ( 6) deimoslp [ U8] : 822 octets ( 7) oim09 [ U8] : 1280 octets ( 8) Croqmort [ U8] : 1281 octets ( 9) JCDjcd [U32] : 11365 octets (10) JCDjcd [U16] : 11415 octets (11) JCDjcd [U24] : 11544 octets
  • taille du fichier compresse par rapport a celle initiale :
( 1) JCDjcd [ U8] : 102.770547 % ( 2) Malibu23 [ U8] : 102.798438 % ( 3) TheWhiteShadow [ U8] : 103.384158 % ( 4) vecchio56 [ U8] : 107.084418 % ( 5) mido123 [ U8] : 107.149498 % ( 6) deimoslp [ U8] : 107.400521 % ( 7) oim09 [ U8] : 111.695798 % ( 8) Croqmort [ U8] : 111.946820 % ( 9) JCDjcd [U32] : 141.502417 % (10) JCDjcd [U24] : 156.656750 % (11) JCDjcd [U16] : 183.274451 % fin du programme, appuyez sur une touche

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

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)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.