codage huffman

5/5 (6 avis)

Snippet vu 14 392 fois - Téléchargée 27 fois

Contenu du snippet

c' est le codage huffman

Source / Exemple :


/*

  • Devoir : Compression de Huffman
  • /
#include <stdio.h> #include <stdlib.h> #include <string.h> /* *
  • /
typedef unsigned char byte; typedef unsigned int uint; /* */ typedef struct _arbre* ptr_arbre; typedef struct _arbre { /* données */ byte c; uint freq; uint code_huff; byte nbr_bits; /* les fils */ ptr_arbre fils_d; ptr_arbre fils_g; }h_arbre; /* */ typedef struct _list* ptr_list; typedef struct _list { ptr_arbre noeud; ptr_list suiv; }list; /* */ typedef struct _ch_context { FILE *fin; FILE *fout; uint fsize; uint nbr_elem; ptr_arbre r_arbre; ptr_arbre car_table; }ch_context; /* *
  • /
typedef struct _dh_context { FILE *fin; FILE *fout; uint fsize; uint nbr_elem; ptr_arbre r_arbre; }dh_context; /* compression */ int comp_huffman(const char*, const char*); /* decompression */ int decomp_huffman(const char*, const char*); /*******************************************************
                                  • main**********************************
                                                                                                            • /
int main(int argc, char **argv) { int get_file_size(const char*); if ((argc != 4) || (argv[1][0] != '-') || ((argv[1][1] != 'c') && (argv[1][1] != 'd'))) { printf("Utilisation:\n"); printf(" Huffman {-c, -d} src dest\n"); printf(" -c : pour la compression\n"); printf(" -d : pour la decompression\n"); printf(" src : fichier source\n"); printf(" dest : fichier destination\n"); } else { char *fsrc, *fdest; char comp = argv[1][1]; /* les deux fichiers */ fsrc = argv[2]; fdest = argv[3]; if (comp == 'c') { /* compression */ if (comp_huffman(fsrc, fdest)) { int insize = get_file_size(fsrc); int outsize = get_file_size(fdest); printf("Compression reussie\n"); printf("Taile du fichier non compressee : %d (octets)\n", insize); printf("Taile du fichier compressee : %d (octets)\n", outsize); printf("Taux de compression : %d%%\n", ((outsize - insize)*100)/outsize); } else printf("Erreur de compression\n"); } else { /* decompression */ if (decomp_huffman(fsrc, fdest)) printf("Decompression OK\n"); else printf("Erreur de decompression\n"); } } return (0); } int get_file_size(const char *file) { int size; FILE *fp = fopen(file, "rb"); if (!fp) return (-1); fseek(fp, 0, 2); size = (int)ftell(fp); fclose(fp); return (size); } void ch_free_arbre(ptr_arbre arbre) { /* on libere tous les noeud sauf les feuille */ if (arbre) { if (arbre->fils_g && arbre->fils_d) { ch_free_arbre(arbre->fils_g); ch_free_arbre(arbre->fils_d); free(arbre); } } } /* */ void ch_free_context(ch_context* ct) { ch_free_arbre(ct->r_arbre); if (ct->car_table) { free(ct->car_table); } if (ct->fin) fclose(ct->fin); if (ct->fout) fclose(ct->fout); } /* */ void ch_inserer(ptr_list* lst, ptr_arbre arbre) { if (*lst == 0) { (*lst) = (ptr_list)malloc(sizeof(list)); (*lst)->noeud = arbre; (*lst)->suiv = 0; } else { ptr_list p = (*lst); if (p->noeud->freq > arbre->freq) { ptr_list l = (ptr_list)malloc(sizeof(list)); l->noeud = arbre; l->suiv = (*lst); (*lst) = l; } else { ptr_list q, l; while (p) { if (p->noeud->freq > arbre->freq) break; q = p; p = p->suiv; } l = (ptr_list)malloc(sizeof(list)); l->noeud = arbre; l->suiv = p; q->suiv = l; } } } /* */ int ch_calc_freq(ch_context* ct) { uint *car_freq; int i, j; car_freq = (uint*)malloc(256*sizeof(uint)); memset(car_freq, 0, 256*sizeof(uint)); rewind(ct->fin); /* etude statistique */ while (!feof(ct->fin)) { byte c; fread(&c, 1, 1, ct->fin); if (car_freq[c] == 0) (ct->nbr_elem)++; car_freq[c] = car_freq[c] + 1; } /* création de la table des caracteres du fichier */ ct->car_table = (ptr_arbre)malloc((ct->nbr_elem)*sizeof(h_arbre)); for (i = 0, j = 0; i < 256 ; i++) { if (car_freq[i] != 0) { ct->car_table[j].c = (byte)i; ct->car_table[j].freq = car_freq[i]; ct->car_table[j].code_huff = 0; ct->car_table[j].nbr_bits = 0; ct->car_table[j].fils_d = 0; ct->car_table[j].fils_g = 0; j++; } } free(car_freq); return (1); } /* */ void ch_set_bits(ptr_arbre arbre, uint code_huff, uint nbr_bits) { if (arbre) { if (arbre->fils_d && arbre->fils_g) { ch_set_bits(arbre->fils_d, code_huff, nbr_bits + 1); ch_set_bits(arbre->fils_g, code_huff | (0x1 << nbr_bits), nbr_bits + 1); } else { arbre->code_huff = code_huff; arbre->nbr_bits = nbr_bits; } } } /* */ int ch_creation_arbre(ch_context* ct) { ptr_list lst = 0; uint i, nbr_elem = ct->nbr_elem; for (i = 0; i < nbr_elem; i++) ch_inserer(&lst, &(ct->car_table[i])); /* c'est bien, les elements sont classés par ordre croissant */ /* maintenat on va grouper les deux premier */ while (nbr_elem > 1) { ptr_arbre a, a1, a2; ptr_list p; p = lst; a1 = p->noeud; a2 = p->suiv->noeud; lst = p->suiv->suiv; free(p->suiv); free(p); a = (ptr_arbre)malloc(sizeof(h_arbre)); a->c = -1; a->freq = a1->freq + a2->freq; a->code_huff = 0; a->fils_d = a1; a->fils_g = a2; ch_inserer(&lst, a); nbr_elem--; } ct->r_arbre = lst->noeud; free(lst); /* calcul du codage pour chaque caractere */ ch_set_bits(ct->r_arbre, 0, 0); return (1); } /* */ int ch_ecriture_table(ch_context* ct) { uint i, nbr_elem = ct->nbr_elem; /* nombre de caracteres */ if (!fwrite(&nbr_elem, sizeof(uint), 1, ct->fout)) return (0); /* la taille du fichier */ if (!fwrite(&(ct->fsize), sizeof(uint), 1, ct->fout)) return (0); /* ecriture de la table */ for (i = 0; i < nbr_elem; i++) { byte c, nbr_bits; uint code_huff; /* le caractere */ c = ct->car_table[i].c; if (!fwrite(&c, 1, 1, ct->fout)) return (0); /* le nombre de bit necessaire */ nbr_bits = ct->car_table[i].nbr_bits; if (!fwrite(&nbr_bits, 1, 1, ct->fout)) return (0); /* le code huffman */ code_huff = ct->car_table[i].code_huff; if (nbr_bits <= 8) { if (!fwrite(&code_huff, 1, 1, ct->fout)) return (0); } else if (nbr_bits <= 16) { if (!fwrite(&code_huff, 2, 1, ct->fout)) return (0); } else { if (!fwrite(&code_huff, 4, 1, ct->fout)) return (0); } } return (1); } /* */ ptr_arbre ch_get_arbre(ch_context* ct, byte c) { ptr_arbre a; uint i; a = ct->car_table; i = ct->nbr_elem; while (i--) { if (a->c == c) return (a); a++; } return (0); } /* */ int ch_compression(ch_context* ct) { ptr_arbre a; byte ucar = 0, c, nbr_bits; uint code_huff, pc = 0, i; rewind(ct->fin); while (!feof(ct->fin)) { fread(&c, 1, 1, ct->fin); a = ch_get_arbre(ct, c); code_huff = a->code_huff; nbr_bits = a->nbr_bits; for (i = 0; i < nbr_bits; i++) { ucar = ucar << 1; if (code_huff & 0x1) ucar = ucar | 0x1; code_huff = code_huff >> 1; pc++; if (pc == 8) { fwrite(&ucar, 1, 1, ct->fout); pc = 0; ucar = 0; } } } if (pc != 0) { /* ecriture du dernier caractere */ while (pc != 8) { ucar = ucar << 1; pc++; } fwrite(&ucar, 1, 1, ct->fout); } return (1); } /* */ int comp_huffman(const char* fsrc, const char* fdest) { ch_context ct; memset(&ct, 0, sizeof(ch_context)); ct.fin = fopen(fsrc, "rb"); if (!(ct.fin)) return (0); fseek(ct.fin, 0, 2); ct.fsize = ftell(ct.fin); /* calcule de la fréquence */ if (!ch_calc_freq(&ct)) { ch_free_context(&ct); return (0); } /* création de l'arbre de huffman */ if (!ch_creation_arbre(&ct)) { ch_free_context(&ct); return (0); } /* on est prés à la compression */ ct.fout = fopen(fdest, "wb"); if (!(ct.fin)) { ch_free_context(&ct); return (0); } /* ecriture de la table */ if (!ch_ecriture_table(&ct)) { ch_free_context(&ct); return (0); } /* compression des données */ if (!ch_compression(&ct)) { ch_free_context(&ct); return (0); } ch_free_context(&ct); return (1); } void dh_free_arbre(ptr_arbre arbre) { /* on libere tous les noeud sauf les feuille */ if (arbre) { dh_free_arbre(arbre->fils_g); dh_free_arbre(arbre->fils_d); free(arbre); } } /* */ void dh_free_context(dh_context* ct) { dh_free_arbre(ct->r_arbre); if (ct->fin) fclose(ct->fin); if (ct->fout) fclose(ct->fout); } /* */ int dh_creation_arbre(dh_context* ct) { uint i, nbr_elem; /* nombre d'element */ if (!fread(&nbr_elem, sizeof(uint), 1, ct->fin)) return (0); /* la taille du fichier */ if (!fread(&(ct->fsize), sizeof(uint), 1, ct->fin)) return (0); /* allocation de la mémoire */ ct->nbr_elem = nbr_elem; ct->r_arbre = (ptr_arbre)malloc(sizeof(h_arbre)); ct->r_arbre->c = 0xFF; ct->r_arbre->fils_d = 0; ct->r_arbre->fils_g = 0; for (i = 0; i < nbr_elem; i++) { byte c, nbr_bits, j; uint code_huff = 0; ptr_arbre a; /* le caractere */ if (!fread(&c, 1, 1, ct->fin)) return (0); /* le nombre de bit necessaire */ if (!fread(&nbr_bits, 1, 1, ct->fin)) return (0); /* le code huffman */ if (nbr_bits <= 8) { if (!fread(&code_huff, 1, 1, ct->fin)) return (0); } else if (nbr_bits <= 16) { if (!fread(&code_huff, 2, 1, ct->fin)) return (0); } else { if (!fread(&code_huff, 4, 1, ct->fin)) return (0); } /* ajout à l'arbre de huffman */ a = ct->r_arbre; for (j = 0; j < nbr_bits; j++, code_huff >>= 1) { if (code_huff & 0x1) { if (a->fils_g == 0) { a->fils_g = (ptr_arbre)malloc(sizeof(h_arbre)); a = a->fils_g; a->c = -1; a->fils_g = 0; a->fils_d = 0; } else a = a->fils_g; } else { if (a->fils_d == 0) { a->fils_d = (ptr_arbre)malloc(sizeof(h_arbre)); a = a->fils_d; a->c = 0xFF; a->fils_g = 0; a->fils_d = 0; } else a = a->fils_d; } } a->c = c; } return (1); } /* Fonction de décompression */ int dh_decompression(dh_context* ct) { ptr_arbre a = ct->r_arbre; uint j, i = 0, fsize = ct->fsize; byte c; while (!feof(ct->fin)) { fread(&c, 1, 1, ct->fin); for (j = 0; j < 8; j++) { if ((c & 0x80) == 0x80) /* 0x80 = 10000000b */ a = a->fils_g; else a = a->fils_d; c = c << 1; if ((a->fils_d == 0) && (a->fils_g == 0)) { /* une feuille */ fwrite(&(a->c), 1, 1, ct->fout); if (++i == fsize) return (1); a = ct->r_arbre; } } } return (0); } /* */ int decomp_huffman(const char* fsrc, const char* fdest) { dh_context ct; memset(&ct, 0, sizeof(dh_context)); ct.fin = fopen(fsrc, "rb"); if (!(ct.fin)) return (0); /* récréation de l'arbre */ if (!dh_creation_arbre(&ct)) { dh_free_context(&ct); return (0); } /* on est prés à la decompression */ ct.fout = fopen(fdest, "wb"); if (!(ct.fin)) { dh_free_context(&ct); return (0); } /* decompression des données */ if (!dh_decompression(&ct)) { dh_free_context(&ct); return (0); } dh_free_context(&ct); return (1); }

A voir également

Ajouter un commentaire Commentaires
yvesB87 Messages postés 12 Date d'inscription samedi 18 octobre 2008 Statut Membre Dernière intervention 15 mai 2015
12 avril 2012 à 13:59
Merci pour ce code
ybenzaki Messages postés 1 Date d'inscription lundi 16 mars 2009 Statut Membre Dernière intervention 24 juin 2009
24 juin 2009 à 12:19
Excellent travail
SIIIFE Messages postés 1 Date d'inscription dimanche 3 mai 2009 Statut Membre Dernière intervention 5 mai 2009
5 mai 2009 à 21:34
Salamo Alikom
merci pour ce code , tu est vraiment aide moi .
n2klinux Messages postés 2 Date d'inscription mardi 3 octobre 2006 Statut Membre Dernière intervention 10 décembre 2006
23 mai 2007 à 20:21
Le seul code sur huffman qui fonctionne sans avoir à chippoter. Bravo
cs_Emmanuel Delahaye Messages postés 5 Date d'inscription samedi 5 août 2006 Statut Membre Dernière intervention 19 janvier 2007
19 janv. 2007 à 15:38
A nice piece of work
Afficher les 6 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_mido123)