codage huffman

Soyez le premier à donner votre avis sur cette source.

Snippet vu 13 184 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
Messages postés
12
Date d'inscription
samedi 18 octobre 2008
Statut
Membre
Dernière intervention
15 mai 2015

Merci pour ce code
Messages postés
1
Date d'inscription
lundi 16 mars 2009
Statut
Membre
Dernière intervention
24 juin 2009

Excellent travail
Messages postés
1
Date d'inscription
dimanche 3 mai 2009
Statut
Membre
Dernière intervention
5 mai 2009

Salamo Alikom
merci pour ce code , tu est vraiment aide moi .
Messages postés
2
Date d'inscription
mardi 3 octobre 2006
Statut
Membre
Dernière intervention
10 décembre 2006

Le seul code sur huffman qui fonctionne sans avoir à chippoter. Bravo
Messages postés
5
Date d'inscription
samedi 5 août 2006
Statut
Membre
Dernière intervention
19 janvier 2007

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)