LES HUFFMAN DE CPPFRANCE
wxccxw
Messages postés
755
Date d'inscription
samedi 15 mai 2004
Statut
Membre
Dernière intervention
30 janvier 2011
-
6 août 2006 à 23:48
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
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
https://codes-sources.commentcamarche.net/source/38961-les-huffman-de-cppfrance
11 juil. 2007 à 17:42
débutant ... ca se discute (mais pourquoi pas) ...
11 juil. 2007 à 00:43
5 nov. 2006 à 11:49
5 nov. 2006 à 10:22
5 nov. 2006 à 02:22
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)
14 août 2006 à 02:34
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).
13 août 2006 à 22:53
13 août 2006 à 22:51
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
13 août 2006 à 22:10
13 août 2006 à 22:09
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.
13 août 2006 à 21:58
13 août 2006 à 21:34
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)
13 août 2006 à 21:31
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?
13 août 2006 à 21:28
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é
13 août 2006 à 20:54
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 ...
13 août 2006 à 20:52
13 août 2006 à 20:50
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 ^^.
13 août 2006 à 20:41
Donc dans la réalité, cet arbre n'est jamais construit
13 août 2006 à 20:41
Donc dans la réalité, cet arbre n'est jamais construit
13 août 2006 à 20:37
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 ^^.
13 août 2006 à 20:04
Je me suis un peu amélioré, mes temps son comparables à deimoslp
13 août 2006 à 19:59
Cette information est codée sur seulement 3 bits, ca doit donc être ici que je gagne
13 août 2006 à 19:56
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)
13 août 2006 à 19:39
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
13 août 2006 à 19:06
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)
12 août 2006 à 17:30
12 août 2006 à 17:28
12 août 2006 à 17:17
================================================================
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
12 août 2006 à 16:53
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
11 août 2006 à 23:01
11 août 2006 à 12:12
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.
11 août 2006 à 11:08
8 août 2006 à 15:10
8 août 2006 à 13:36
de lettre(...);
8 août 2006 à 10:46
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!
7 août 2006 à 20:53
Je suis content mon algo n'est pas le plus mauvais ;)
7 août 2006 à 17:54
7 août 2006 à 16:58
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.
7 août 2006 à 15:57
Sinon, bravo JCDjcd !
7 août 2006 à 14:10
un peu fatiguant et surtout long ...
de plus quand il y a des BUGs faut les chercher
7 août 2006 à 13:48
7 août 2006 à 13:16
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)
7 août 2006 à 11:01
7 août 2006 à 10:47
6 août 2006 à 23:48