LES HUFFMAN DE CPPFRANCE

Information sur la source

Catégorie :Maths & Algorithmes Classé sous : huffman, algorithme, comparaison, 32bits, 8bits Niveau : Débutant Date de création : 06/08/2006 Date de mise à jour : 13/08/2006 18:50:29 Vu / téléchargé: 5 932 / 502

Auteur : JCDjcd

Ecrire un message privé

Ce membre participe au partage de revenus publicitaires

Note :

9,67 / 10

Commentaire sur cette source (45)

Ajouter un commentaire et/ou une note

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

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

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

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Auteurs
- Croqmort
  - Croqmort.c 11 861 octets
  - Croqmort.h 263 octets
- deimoslp
  - deimoslp.c 26 204 octets
  - deimoslp.h 241 octets
- GoldenEye
  - GoldenEye.c 14 749 octets
  - GoldenEye.h 265 octets
- JCDjcdUi
  - JCDjcdUi.c 21 136 octets
  - JCDjcdUi.h 730 octets
- Kreator
  - Kreator.c 20 767 octets
  - Kreator.h 239 octets
- Malibu23
  - Malibu23.c 13 490 octets
  - Malibu23.h 283 octets
- mido123
  - mido123.c 12 282 octets
  - mido123.h 239 octets
- Oim09
  - Oim09.c 11 335 octets
  - Oim09.h 235 octets
- TheWhiteShadow
  - TheWhiteShadow.c 17 409 octets
  - TheWhiteShadow.h 232 octets
- vecchio56
  - OLD_vecchio56.c 19 961 octets
  - vecchio56.c 17 731 octets
  - vecchio56.h 220 octets
- vieuxLion
  - vieuxLion.c 602 octets
  - vieuxLion.h 220 octets
data.c 57 688 octets
data.h 20 594 octets
huffman.dsp 6 840 octets
huffman.dsw 539 octets
main.c 10 391 octets
math.c 64 040 octets
math.h 29 035 octets
paramDBG.h 2 262 octets
res.txt 10 411 octets
util.c 26 642 octets
util.h 16 582 octets

Télécharger le zip

Historique

13 août 2006 18:50:29 :: MAJ code de vecchio56

Sources du même auteur

Toutes les sources de JCDjcd

Sources de la même categorie

Toutes les sources de la catégorie Maths & Algorithmes

Sources en rapport avec celle ci

Commentaires

Commentaire de wxccxw le 06/08/2006 23:48:05

j'aime bien ^^ GJ !
Commentaire de deck_bsd le 07/08/2006 10:47:04

très bonne source :D
Commentaire de Kirua le 07/08/2006 11:01:52

Absolument génial cette comparaison systématique :). Qu'est-ce qui ne va pas dans le programme de Croqmort ?
Commentaire de JCDjcd le 07/08/2006 13:16:51

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)
Commentaire de Kirua le 07/08/2006 13:48:54

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 :).
Commentaire de JCDjcd le 07/08/2006 14:10:44

merci
un peu fatiguant et surtout long ...
de plus quand il y a des BUGs faut les chercher
Commentaire de Galmiza le 07/08/2006 15:57:13

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 !
Commentaire de JCDjcd le 07/08/2006 16:58:42

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.
Commentaire de laurent1024 le 07/08/2006 17:54:54

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.
Commentaire de vecchio56 le 07/08/2006 20:53:46 administrateur CS

Effectivement t'a fait un gros boulot!
Je suis content mon algo n'est pas le plus mauvais ;)
Commentaire de vecchio56 le 08/08/2006 10:46:41 administrateur CS

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!
Commentaire de JCDjcd le 08/08/2006 13:36:51

oué j'ai pas tout corrigé, j'ai pas élucider le problème
de lettre(...);
Commentaire de zeratul67 le 08/08/2006 15:10:59

merci pour le travail accompli :)
Commentaire de vecchio56 le 11/08/2006 11:08:27 administrateur CS

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...
Commentaire de deimoslp le 11/08/2006 12:12:04

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.
Commentaire de vecchio56 le 11/08/2006 23:01:13 administrateur CS

Mais peut-on vraiment avoir un fichier qui va faire un arbre de hauteur 255?
Commentaire de vecchio56 le 12/08/2006 16:53:24 administrateur CS

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
Commentaire de vecchio56 le 12/08/2006 17:17:58 administrateur CS

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
Commentaire de Kirua le 12/08/2006 17:28:28

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!
Commentaire de vecchio56 le 12/08/2006 17:30:25 administrateur CS

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
Commentaire de JCDjcd le 13/08/2006 19:06:06

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.

Codes (5613)

Listes de codes

Categories des codes

Trouver des codes

Top des codes

Auteurs de codes

Tutoriaux (24)

Forums (149663)

Vidéos

Livres (28482)

Outils & Liens

Emploi (CV et Offres)

Services

Téléchargement

Chat

Autres Sites

Divers

Partenaires

Section étudiants

Section pro

Connexion

Derniers blogs

Mini Sondage

Derniers logiciels

Mes RSS

Stats