begin process at 2012 02 10 13:57:22
  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é :10 890 / 8 882
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 UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

Source avec Zip COMPRESSION / DECOMPRESSION SELON L'ALGORITHME LEMPELZIV 78V par th1man
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 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 huffman( compression) [ par flamme19 ] sa[size=200]lut, je cherche un programme en c++ qui fait la compression, puis la décompression d'un texte donné en utilisant l'algorithme de huffman.. compression et décompression un fichier texte selon l'algorithme de HUFFMAN [ par sarasofia ] [b]salut tout le monde s'il vous plaît[^^sad1] j ai besoin d'un programme de compression texte selon l algorithme de Huffman en C,C++, Matlab s'il vou algorithme de compression de fichier avec zlib [ par mayssakh84 ] bonjour, j'ai un programme qui utilise les méthodes deflate() et inflate() de la librairie zlib pour la compression des fichiers mon probleme c'est q compression et c++ [ par fakbill ] A l'adresse http://www.cjkware.com/wamckee/huffman.zip j'ai touvé une implémentation en c++ de l'algo de huffman.Pb: Je ne cromprends rien à la façon compression LZW [ par GATERMA ] je veux telecharger une classe qui effectue le codage LZW pour c++/builder Compression avec huffman sous SCILAB si possible Decompression aussi [ par Doser ] Besoin d'aide j suis un peu coincé compression de huffman [ par chiheb1106 ] Est-ce qu'il y a un algorithme en C qui permet de réaliser la compression et la décompression d'un fichier texte selon la méthode de Huffman sans util 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


iPod touch 3rd Generation (64 Go)
Entre 374€ et 379€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

Photothèque

Photo Green Energy Solutions With Light Bulb Morphed Into LandscapePhoto Framed Landscape Image of Monument Valley
Photo Photo aérienne de Saintes Maries de la Mer 

Visiter la photothèque
 
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 : 0,858 sec (3)

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)