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
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.