begin process at 2010 02 10 12:16:16
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > COMPRESSION HUFFMAN ( INTERFACE EN API WINDOWS )

COMPRESSION HUFFMAN ( INTERFACE EN API WINDOWS )


 Information sur la source

Note :
8 / 10 - par 2 personnes
8,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Classé sous :huffman, compression, algorithme, compresser, lzw Niveau :Initié Date de création :11/07/2006 Date de mise à jour :28/08/2006 02:07:17 Vu / téléchargé :9 473 / 8 766
Auteur : deimoslp

Ecrire un message privé
Site perso
Commentaire sur cette source (17)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
Le programme que je vous propose est une implémentation de l'algorithme de Huffman (compression sans perte); il comprend un module de compression et un autre de décompression.
Il affiche également des informations sur l'entropie et la redondance du fichier source.

Au niveau du programme en lui-même, j'ai utilisé des arbres binaires pour le codage/décodage et j'ai réalisé un module de lecture/écriture asynchrone pour tenter d'améliorer les performances.

Le programme a été développé sous visual c++, donc j'ai bien peur qu'il soit difficile de le compiler dans d'autres environnements.

Toutes les critiques/remarques sont les bienvenues ^^.

Arthur


 Conclusion

1 - J'avais prévu de faire une compression sur des mots de 2,3 ou 4 octets pour améliorer les performances (3 octets pour les images par exemple) mais je n'ai pas eu le temps de me pencher sur le problème.

2 - Il y a plusieurs définitions du taux de compression, moi j'utilise : T=(taille_fichier_compressé/taille_fichier_origina l)

3 - J'ai essayé de faire des efforts sur les commentaires du code mais s'il y a des questions, je serai là pour y répondre.

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

11 août 2006 13:29:00 :
les améliorations : - un module permettant de faire un tri par tas des feuilles de l'arbre de codage - compression sur 8,16 ou 24 bits - taille de l'entête réduite (merci à JCDjcd ;)) - correction des fuites de mémoire - code remanié pour diminuer la mémoire vive utilisée et améliorer les performances A noter que la compression 24 bits est très lente avec les gros fichiers ... je n'ai pas réussi à l'améliorer plus. Au programme de la prochaine version surement la compression 32 bits.
11 août 2006 13:29:12 :
les améliorations : - un module permettant de faire un tri par tas des feuilles de l'arbre de codage - compression sur 8,16 ou 24 bits - taille de l'entête réduite (merci à JCDjcd ;)) - correction des fuites de mémoire - code remanié pour diminuer la mémoire vive utilisée et améliorer les performances A noter que la compression 24 bits est très lente avec les gros fichiers ... je n'ai pas réussi à l'améliorer plus. Au programme de la prochaine version surement la compression 32 bits.
11 août 2006 13:29:44 :
les améliorations : - un module permettant de faire un tri par tas des feuilles de l'arbre de codage - compression sur 8,16 ou 24 bits - taille de l'entête réduite (merci à JCDjcd ;)) - correction des fuites de mémoire - code remanié pour diminuer la mémoire vive utilisée et améliorer les performances A noter que la compression 24 bits est très lente avec les gros fichiers ... je n'ai pas réussi à l'améliorer plus. Au programme de la prochaine version surement la compression 32 bits.
11 août 2006 13:29:59 :
les améliorations : - un module permettant de faire un tri par tas des feuilles de l'arbre de codage - compression sur 8,16 ou 24 bits - taille de l'entête réduite (merci à JCDjcd ;)) - correction des fuites de mémoire - code remanié pour diminuer la mémoire vive utilisée et améliorer les performances A noter que la compression 24 bits est très lente avec les gros fichiers ... je n'ai pas réussi à l'améliorer plus. Au programme de la prochaine version surement la compression 32 bits.
11 août 2006 13:30:14 :
les améliorations : - un module permettant de faire un tri par tas des feuilles de l'arbre de codage - compression sur 8,16 ou 24 bits - taille de l'entête réduite (merci à JCDjcd ;)) - correction des fuites de mémoire - code remanié pour diminuer la mémoire vive utilisée et améliorer les performances A noter que la compression 24 bits est très lente avec les gros fichiers ... je n'ai pas réussi à l'améliorer plus. Au programme de la prochaine version surement la compression 32 bits.
11 août 2006 13:30:43 :
les améliorations : - un module permettant de faire un tri par tas des feuilles de l'arbre de codage - compression sur 8,16 ou 24 bits - taille de l'entête réduite (merci à JCDjcd ;)) - correction des fuites de mémoire - code remanié pour diminuer la mémoire vive utilisée et améliorer les performances A noter que la compression 24 bits est très lente avec les gros fichiers ... je n'ai pas réussi à l'améliorer plus. Au programme de la prochaine version surement la compression 32 bits.
11 août 2006 13:31:55 :
les améliorations : - un module permettant de faire un tri par tas des feuilles de l'arbre de codage - compression sur 8,16 ou 24 bits - taille de l'entête réduite (merci à JCDjcd ;)) - correction des fuites de mémoire - code remanié pour diminuer la mémoire vive utilisée et améliorer les performances A noter que la compression 24 bits est très lente avec les gros fichiers ... je n'ai pas réussi à l'améliorer plus. Au programme de la prochaine version surement la compression 32 bits.
11 août 2006 13:35:06 :
les améliorations : - un module permettant de faire un tri par tas des feuilles de l'arbre de codage - compression sur 8,16 ou 24 bits - taille de l'entête réduite (merci à JCDjcd ;)) - correction des fuites de mémoire - code remanié pour diminuer la mémoire vive utilisée et améliorer les performances A noter que la compression 24 bits est très lente avec les gros fichiers ... je n'ai pas réussi à l'améliorer plus. Au programme de la prochaine version surement la compression 32 bits.
28 août 2006 01:52:07 :
Au programme de cette version 0.2: - Compression 16 et 24 bits - Un module de tri par tas pour accélérer le tri des symboles - Optimisation du code pour diminuer à la fois la RAM utilisée et le temps de compression - Taille de l'entête réduite(Merci à JCDjcd) A noter que la compression 24 bits sur les gros fichiers (>50Mo) peut s'avérer très lente (surtout si RAM<1Go).
28 août 2006 01:55:01 :
Au programme de cette version 0.2: - Compression 16 et 24 bits - Un module de tri par tas pour accélérer le tri des symboles - Optimisation du code pour diminuer à la fois la RAM utilisée et le temps de compression - Taille de l'entête réduite(Merci à JCDjcd) A noter que la compression 24 bits sur les gros fichiers (>50Mo) peut s'avérer très lente (surtout si RAM<1Go).
28 août 2006 01:58:32 :
Au programme de cette version 0.2: - Compression 16 et 24 bits - Un module de tri par tas pour accélérer le tri des symboles - Optimisation du code pour diminuer à la fois la RAM utilisée et le temps de compression - Taille de l'entête réduite(Merci à JCDjcd) A noter que la compression 24 bits sur les gros fichiers (>50Mo) peut s'avérer très lente (surtout si RAM<1Go).
28 août 2006 02:00:19 :
Au programme de cette version 0.2: - Compression 16 et 24 bits - Un module de tri par tas pour accélérer le tri des symboles - Optimisation du code pour diminuer à la fois la RAM utilisée et le temps de compression - Taille de l'entête réduite(Merci à JCDjcd) A noter que la compression 24 bits sur les gros fichiers (>50Mo) peut s'avérer très lente (surtout si RAM<1Go).
28 août 2006 02:03:12 :
Au programme de cette version 0.2: - Compression 16 et 24 bits - Un module de tri par tas pour accélérer le tri des symboles - Optimisation du code pour diminuer à la fois la RAM utilisée et le temps de compression - Taille de l'entête réduite(Merci à JCDjcd) A noter que la compression 24 bits sur les gros fichiers (>50Mo) peut s'avérer très lente (surtout si RAM<1Go).
28 août 2006 02:04:07 :
Au programme de cette version 0.2: - Compression 16 et 24 bits - Un module de tri par tas pour accélérer le tri des symboles - Optimisation du code pour diminuer à la fois la RAM utilisée et le temps de compression - Taille de l'entête réduite(Merci à JCDjcd) A noter que la compression 24 bits sur les gros fichiers (>50Mo) peut s'avérer très lente (surtout si RAM<1Go).
28 août 2006 02:05:08 :
Au programme de cette version 0.2: - Compression 16 et 24 bits - Un module de tri par tas pour accélérer le tri des symboles - Optimisation du code pour diminuer à la fois la RAM utilisée et le temps de compression - Taille de l'entête réduite(Merci à JCDjcd) A noter que la compression 24 bits sur les gros fichiers (>50Mo) peut s'avérer très lente (surtout si RAM<1Go).
28 août 2006 02:07:17 :
Au programme de cette version 0.2: - Compression 16 et 24 bits - Un module de tri par tas pour accélérer le tri des symboles - Optimisation du code pour diminuer à la fois la RAM utilisée et le temps de compression - Taille de l'entête réduite(Merci à JCDjcd) - Correction de quelques fuites de mémoire A noter que la compression 24 bits sur les gros fichiers (>50Mo) peut s'avérer très lente (surtout si RAM<1Go).

 Sources de la même categorie

Source avec Zip OPERATION SUR LES MATRICES CARREES AVEC CLASSE GENERIQUE par chouhad
Source avec une capture OPÉRATIONS SUR MATRICES C++ par Minilogus
[DEV-C++] CALCUL DE LA RACINE CARRÉE D'UN RÉEL par Jhep
PROGRAMME QUI CALCUL LE PPCM ET LE PGCD par AnoSantino
EVALUER UNE EXPRESSION MATHÉMATIQUE par begueradj
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture COMPRESSION FICHIERS ALGORITHME HUFFMAN C par xtremejames183
Source avec Zip CODEUR DE HUFFMAN par webis
Source avec Zip Source avec une capture [C / WIN32] NTCLIB: COMPRESSION PAR API NATIVE par Neo_Fr
Source avec Zip LZZ HUFFMAN COMPRESSION par f_l_a_s_h_b_a_c_k
Source avec Zip COMPRESSION HUFFMAN par Kreator

Commentaires et avis

Commentaire de JCDjcd le 11/07/2006 18:38:23

pour moi l'entropie donnee comme cela "brute & seule" n'a aucun sens, il faudrait peut etre la comparer a une autre grandeur comme par exemple la longueur moyenne (ou autre chose de pertinent du genre quelle est l'entropie des images usuelles : bitmap de la mer, photos de famille, textes litteraires, conversations MSN) enfin juste pour avoir une idee, pour situer le fichier parmi ces exemples.

Commentaire de deimoslp le 11/07/2006 19:05:18

En fait j'ai juste appliqué une formule que j'ai trouvée sur le net pour calculer l'entropie.  En gros, l'entropie est comprise entre 0 et 8, dans le cas d'une compression par mots de 1 octet; plus elle est faible et plus la compression sera efficace pour le fichier ouvert.
Le taux de redondance, qui est basé sur cette grandeur est peut-etre un peu plus significatif ...

Commentaire de JCDjcd le 11/07/2006 19:14:16

mais l'entropie ce n'est pas la meme chose que la longueur moyenne des mots ...
ca serait bien de pouvoir calculer l'entropie d'un fichier, et tu montrerais la difference d'entropie (ie l'elevation d'entropie due a la compression)

Commentaire de mogwai93 le 11/07/2006 21:39:54

"Le programme a été développé sous visual c++, donc j'ai bien peur qu'il soit difficile de le compiler dans d'autres environnements."

ca passe sous DevC++ !!
en modifiant 1 ligne dans le fichier "huffman.cpp"
void donnee_construit()

il faut mettre :
// décalage
unsigned int i;
for(i=2;i<nbarbres;i++)

==> sortir unsigned int de la boucle for
pour que i soit reconnu en dehors lors de l'appel
listearbre[i-2]=noeud;

pour les warning, ils sont facilement corrigibles ;-)

Commentaire de Kirua le 12/07/2006 10:22:13

C'est T = 1 - (taille_fichier_compressé/taille_fichier_original)

puisque c'est assez logique d'avoir un taux de compression nul si le nouveau fichier à la même taille que l'original. et d'ailleurs, avec huffman, on peut aussi avoir pire. Il n'y a sans doute pas plusieurs définitions, mais il est possible que les gens ne soient pas d'accord sur le sens à donner ^^. Quoi qu'il en soit, dans les programmes pros de compression, plus le taux est élevé, mieux c'est compressé.

Et Huffman, c'est un cooooool algo :).

Commentaire de deimoslp le 12/07/2006 13:09:48

MOGWAI93 > C'est sympa d'avoir testé sous DevC++ que j'ai eu la flemme d'installer :-p; je tacherai de corriger le code dans la prochaine version.

KIRUA > En fait j'avais regardé auparavant sur la page de wikipedia http://fr.wikipedia.org/wiki/Taux_de_compression , et puis j'ai vérifié sous WinRAR, ce qu'ils appellent 'ratio' c'est bien la même chose que mon taux de compression...
Enfin tout ça c'est du détail, et je suis d'accord, Huffman est bien cool à programmer :p.

Commentaire de Kirua le 12/07/2006 13:57:59

J'ai pas lu ton code, t'as utilisé une file à priorités pour construire l'arbre, ou tu as extrait le prochain symbole à ajouter à l'arbre chaque fois en cherchant le symbole le plus répété à travers une liste? A mon avis, si tu as utilisé une priority queue, tu auras compris ma phrase, et sinon pas, parce que c'est très mal dit :p

Commentaire de deimoslp le 12/07/2006 14:30:05

Alors je vais essayer de répondre à ta question : Pour construire l'arbre de codage, j'ai fait un tri par insertion des symboles à ajouter à l'arbre, à fréquence d'apparition décroisante. Mais ce n'est pas vraiment une file en tant que telle, vu que j'ai implémenté ça dans un tableau. Il aurait été plus propre d'utiliser une liste chainée mais je n'y ai pas pensé sur le coup.
A voir pour la prochaine version...  ^^

Commentaire de Kirua le 12/07/2006 15:23:37

Ben justement, tu insère les éléments de sorte que le tableau soit tjs trié. C'est bien, mais tu as sans doute fait ça de la façon la plus directe (on avance dans le tableau, on décale toute la suite et on place l'élément). Or, il y a bien plus rapide (on fait une binary search sur le tableau par exemple, pr trouver l'endroit où effectivement placer le nouvel élément). Avec une file à priorités, tu aurais une insertion en log(n) et une extraction en log(n), ce qui est tout de même agréable, et surtout utile si tu comptes étendre huffman aux images 24 bits (bcp de symboles).

Soit dit en passant, pense à mentionner tes résultats sur les compressions d'images, ça m'intéresserait :).

Commentaire de Stormy le 12/07/2006 23:22:09

J'ai trouvé cette source vraiment édifiante pour un résultat exploitable.
Bravo et merci ++

Commentaire de vecchio56 le 13/07/2006 15:03:24 administrateur CS

Je commence juste a lire ton code et je comprends pas quand tu écris 256^sizeof(unitmem)

Commentaire de deimoslp le 13/07/2006 15:37:53

STORMY> Merci ça fait toujours plaisir :)

VECCHIO56> Il s'agit d'une erreur de ma part: je ne savais pas que l'opérateur ^ était en fait un xor, je l'ai pris pour un opérateur puissance. Quant à unitmem il s'agit d'un type(ici un unsigned char) que je pensais changer selon mes besoins (si je souhaitais travailler sur 2 ou 3 octets) mais j'ai finalement implémenté ça autrement.
Tout ça pour dire que "256^sizeof(unitmem)" correspondrait normalement au nombre de symboles codables sur 1 octet (soit 256).
J'ai corrigé tout ça dans la nouvelle version et j'espère avoir le temps de la finir avant de partir en vacances ^^.

Commentaire de petitecherie le 17/07/2006 17:10:35

perso je trouve que c'est un code bien pensé qui m'a pas mal servi; l'implémentation rend les choses bien pratiquables...

Commentaire de JCDjcd le 05/08/2006 23:32:47

Il y a deux problemes :
le premier pas tres grave, mais ton code de gere pas les fichiers uniformes (une seul caractere), mais c'est pas important
le second : probleme de liberation memoire, j'ai enregistre chaque Malloc (ou new ...) et chaque Free (ou delete ...) et a la fin du programme il reste des blocs memoires non-liberes. J'ai mene ma petite enquete et le probleme vient de la fonction <nettoyage> : l'instruction "delete noeud;" devrait etre EN DEHORS du "if(noeud->filsg)"
car sinon les feuilles ne sont pas liberees

Commentaire de deimoslp le 28/08/2006 02:23:54

J'ai eu quelques problèmes pour l'ajout de cette première mise a jour...

J'ai cependant bien travaillé dessus, mais a vous d'en juger.

Commentaire de JulioDelphi le 31/08/2006 10:12:40 administrateur CS

Le seul problème est que tu es impatient et donc tu ne laisse pas le temps au cache de s'actualiser (plusieurs heures parfois).
PEBKAC =)

Commentaire de amira4iag le 17/04/2007 15:34:44

Quels sont les étapes pour ouvrir un nouveau projet  en visual c++ 6.0 telque le votre? votre code est important.merci

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Algorithme de compression STAR amélioré [ par hi_vivie2 ] Bonjour à tous,Je dois réaliser de manière urgente l'implémentation en java de l'algorithme de compression STAR amélioré appliqué aux images en mouvem Algorithme de compression STAR amélioré [ par hi_vivie2 ] Bonjour à tous,Je dois réaliser de manière urgente l'implémentation en java de l'algorithme de compression STAR amélioré appliqué aux images en mouvem Compression de fichier bianire [ par VinceExtense ] Je connais quelques algorithme de compression sans perte comme le codage huffman, le RLE ou avec dictionnaire.Mais il y a t'il d'autres types d'algori Algorithme de compression [ par nebneb37 ] Dans le cadre d'un dossier sur la compression, je suis a la recherche des noms des algorithmes de base des formats ZIP, RAR, ACE ... est qu'il s'agit HELP ! probleme dans une fct pour compression [ par ryoussef19 ] Bonjour, j'ai un probleme vraiment urgent !voila je cherche une fonction qui me permet de compresser un fichier en un fichier , j'utilise les deux fo implémentation de l'algorithme de huffman [ par sousou25 ] sousou25bonsoir &#224; vous tous,d&#233;sol&#233;e du d&#233;rangmt mais je voudrais savoir cmt&nbsp;utiliser des tableaux pour l'impl&#233;mentation algorithme LZW [ par wadii_issaoui ] salut, je cherche a comprendre l'algorithme de compression LZW, pour decompresser une image gif,merci de m'aider algorithme de Huffman [ par amazyo ] Bonjour, SVP je cherche depuis une semaine 'Algorithme de HUFFMAN mais pour l'instant j'ai rien trouvé, s ke vous pouvez m'aider. je vous remercie d' Compression JPEG [ par inkognitodz ] S.V.P. J'ai besoin du code (C++Builder) qui permet de compresser d algorithme de huffman [ par rymifa ] bonjour à tous ,s'il vous plait si quelqu'un poura m'aider à programmer l'algorithme de huffman avec l'affichage de l'arbre en langage c++,je vous se


Nos sponsors


Sondage...

Comparez les prix


HTC Magic
Entre 429€ et 429€

Visiter le guide achat

CalendriCode

Février 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,186 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)