Compression de Huffman Programmeur : Herv PICARD Introduction : On considre un ou plusieurs fichiers volumineux. Les capacits actuelles de stockage et de dbit tant grandes mais toujours limites, on cherche rduire la place prise par ces fichiers tout en conservant linformation quils vhiculent. Dans certains cas (images, sons), on peut rduire notre gr la taille du fichier en perdant, de manire irrversible, plus ou moins dinformation (donc de la qualit) sans pour autant que lutilisateur sen aperoive. Cest le principe utilis par les formats JPEG ou MP3 par exemple. Ainsi, vous ne verrez jamais la diffrence entre un fond dcran JPEG correctement compress et son homologue BMP qui accuse pourtant une taille 15 fois suprieure.

Malheureusement, dans dautres cas, on ne peut se rsoudre perdre de linformation (imaginez un bit perdu dans un .EXE ou dans votre dclaration dimpts). Il est alors ncssaire denvisager des algorithmes de compression sans perte. Il en existe de nombreux, plus ou moins performants (RLE, Shannon-Fano, compression arithmtique). Nous tudierons ici les dtails de lalgorithme de Huffman semi-adaptatif dvelopp en 1952 par le mathmaticien ponyme ainsi que son implmentation en C.

1/ Algorithme de Huffman 1.1/ Prsentation Considrons un fichier texte. La compression de Huffman est un algorithme dit

statistique. Plus un caractre est frquent, plus il sera cod sur un nombre de bits faible. Dordinaire, un caractre (un unsigned char) est sur 8 bits. Dans la langue franaise, la lettre e, trs courante sera code sur 2 ou 3 bits tandis quun w, plus rare utilisera 8 ou 9 bits par exemple. Une premire mthode vise utiliser une table gnrique de frquence des caractres (voir figure 1) qui est rutilise chaque compression et ce indpendamment du fichier compresser. Cette table rsulte dune tude statistique de la frquence dapparition de chaque lettre. Par exemple, le e est crdit de 26% (cela veut dire quen moyenne, 26 lettres sur 100 sont des e en franais). La table fournit alors pour chaque lettre un nombre de bits et un code prcis. Limplmentation de cette mthode est triviale puisquil suffit denregistrer la table doccurrences dans le programme. Cette manire de procder est la plus rapide mais perd en efficacit si le texte est en Espagnol o la lettre o est beaucoup plus

courante que le e On voit alors quune tude statistique sur le texte compresser, visant crer une table doccurrences propre au fichier, se rvle meilleure que lutilisation dune table gnrique. Le revers de la mdaille est lintroduction dun temps de calcul supplmentaire et le rajout dun en-tte dans le fichier compress. Cest ce point de vue que nous avons choisi daborder pour mener bien le dveloppement du programme. Il existe une troisime mthode qui consiste construire larbre binaire au fur et mesure de la lecture et de ladapter en consquence. Cet algorithme permet de saffranchir de len-tte mais lactualisation de larbre rend le processus trs lent sil est mal optimis. La littrature accorde le terme dalgorithme de Huffman adaptatif.

Caract Frque Nbre Code re nce de bits (dec)

Code (bin)

E W [SPC] A J G L R Z

26% 1% 21% 14% 3% 5% 11% 17% 1%

3 9 4 5 8 8 6 4 9

5 227 8 17 189 175 31 12 302

101 011100 011 1000 10001 101111 01 101011 11 011111 1100 100101 110

Figure 1 Exemple de table doccurrences

1.2/ Etapes suivies pour la compression/dcompression Compression :

a/ Etude statistique b/ Dtermination de la table des codes et nombre de bits pour chaque caractre c/ Ecriture de la table en en-tte du fichier compress d/ Encodage du fichier compress, caractre par caractre, compte tenu de la table Dcompression : a/ Reconstruction de la table grce len-tte b/ Dcodage et reconstruction du fichier non compress, caractre par caractre Quelques remarques : Comme la table dpend du fichier compresser, il est essentiel de pouvoir la retrouver lors de la dcompression. Cest pour cette raison que lon place cette table en dbut

du fichier compress afin de pouvoir dcompresser en toute srnit. Le but est de limiter le plus possible la place prise par cet en-tte afin de ne pas trop augmenter la taille du fichier compress. Le programme fonctionnera sur des fichiers contenant des caractres ASCII (7 bits) ou Extended ASCII (8 bits). Dans la prsentation, on supposera nanmoins que lon travaille avec des *.txt pour des raisons videntes de clart.

1.3/ Cration de la table : arbre de Huffman Raisonnons sur un exemple : soit compresser le texte : GoldenEye et Pascal programment ensemble

En ignorant la casse, on obtient la table doccurrences suivante :

Lettre O L D E N Y T P A S C R M G B

Nombre Frquence doccurence s 2 5% 3 7.5% 1 2.5% 8 20% 3 7.5% 1 2.5% 2 5% 2 5% 3 7.5% 2 5% 1 2.5% 2 5% 3 7.5% 2 5% 1 2.5%

[SPC] TOTAL

4 40 Figure 2 Exemple

10% 100%

Nous allons maintenant crer larbre de Huffman, une structure de donnes qui nous permettra daccorder un code chaque lettre, sur un certain nombre de bits, inversement proportionnel la frquence de la lettre. Pour cela, commenons par trier, par ordre croissant de frquence, les caractres. Ces derniers sont considrs comme des arbres (figure 3)

Figure 3 Construction de larbre de Huffman Etape 1

La construction de larbre est aise comprendre. On prend les deux derniers arbres (D et C) de la liste, on les fusionne dans un troisime de frquence somme des 2 prcdents et on linsre dans la liste trie. (voir figure 4)

Figure 4 Construction de larbre de Huffman Etape 2 On ritre le mme procd tant que le nombre dlments de la liste darbres est strictement suprieur 1 (voir figure 5, 6 et 7).

Figure 5

Construction de larbre de Huffman Etape 3

Figure 6 Construction de larbre de Huffman Etape 4 Voici larbre final. Le lien de gauche reoit 0 tandis que celui de droite a la valeur 1.

Figure 7 Construction de larbre de Huffman Rsultat final On remarque que plus un caractre est rare, plus il faut parcourir dtages dans larbre de Huffman. Cela correspond bien lide de compression statistique puisquun tage

reprsente 1 bit de codage. La lettre e, la plus courante, apparat au deuxime tage (on part de la racine qui fait office de rez de chausse) do un codage sur 2 bits. Rsumons lensemble des rsultats dans un tableau (figure 8) : Caractr Frquen Nombre e ce de bits O 5% 4 L 7.5% 4 D 2.5% 6 E 20% 2 N 7.5% 4 Y 2.5% 6 T 5% 4 P 5% 4 A 7.5% 4 S 5% 4 C 2.5% 6 R 5% 5 M 7.5% 4 Code de Huffman 0001 1101 111110 01 1100 111101 0000 0011 1011 0010 111111 11101 1010

G B [SPC]

5% 2.5% 10%

5 6 3

11100 111100 100

Figure 8 Table de codage de Huffman

1.4/ Rsultat de la compression (sans en-tte) Le texte original comprenait 40 caractres, des char cods sur un octet (8 bits). Par consquent la taille du fichier tait de 40 octets (320 bits). Compte tenu de la table cidessus, on obtient le rsultat suivant (figure 9): Caractre G O L D E N E Y E E T P ANb de bits 5 4 4 6 2 4 2 6 2 3 2 4 3 4 4Cumulation 5 913192125273335384044475155 SCALPROGR AMMEN T E4644

345455444 2443 2596569737680858994991031071111131171 21124126 N S E M B L E 4 4 2 4 6 4 2 130 134 136 140 146 150 152 Figure 9 Rsultat de la compression On remarque que la taille du texte compress est de 152 bits soit moins de la moiti du texte initial (320 bits pour mmoire) ! 1.5/ Quelques remarques On dfinit le ratio de compression : EMBED MathType 4.0 Equation Ici EMBED MathType 4.0 Equation

En rgle gnrale, un fichier texte sans pathologie particulire, est compress par cette mthode suivant un ratio de 30 60%. Les dtails concernant len-tte ont t volontairement omis car ils seront traites dans la partie suivante. Sur de trs petits fichiers ( moins de 1 Ko), len-tte est assez volumineux par rapport aux informations compresses. Le fichier rduit a alors une taille suprieure au fichier original Sur de gros fichiers, on peut appliquer lalgorithme de Huffman non pas caractre par caractre mais par tranche de 2, 3 ou 4 caractres. Le problme est que la construction de larbre prend beaucoup plus de temps (larbre est plus gros,il y 65536 doublets possibles de caractres ASCII tendu par exemple). De mme, len-tte prend une place considrable.

2/ Implmentation en C Nota : lintgralit du dveloppement a t effectue sous Visual C++ 6.0. Le programmeur a malgr tout veill fournir un code parfaitement compatible avec DJGPP/Rhide (DOS) et gcc (Unix). Pour ce dernier, ladjonction dun makefile sera envisager. Nous avons vu que lalgorithme de Huffman est assez ais comprendre. Son implmentation en C est autrement plus complexe. En effet, il est ncssaire de matriser deux structures de donnes essentielles : la liste simplement chane et larbre binaire de recherche. Par ailleurs,il nexiste en C aucune fonction pour lire/crire un bit seul. Au mieux, on est capable de lire/crire un char (8 bits). Ainsi pour n bits, on crira 1+E(n)/8 o E(n) est la partie entire de n. Lorsque le rsultat de n/8 nest pas entier, on utilise des bits de bourrage pour remplir la

tranche de 8 bits que constitue un octet. Par consquent, un peu de logique binaire ne fera pas de mal

2.1/ Arbre binaire Un arbre binaire est une structure de donnes compose dun ensemble de nuds (contenant linformation) et de branches (liens vers les 2 nuds fils). Lorsquun nud na plus de fils, on parle alors de feuille. (voir figure 10) Figure 10 Arbre binaire Les arbres que nous sommes amens utiliser sont un peu particuliers dans la mesure o le nud fils gauche contient une valeur

toujours infrieure celle du fils droit (en loccurrence 0 gauche et 1 droite). En langage C, on implmente un arbre laide de pointeurs de la manire suivante : typedef struct noeud* Arbre;//un Arbre est un ptr vers noeud typedef struct noeud {//definition dun noeud unsigned char caractere;//le caractre ASCII tendu (256) int frequence;//frquence de rptition int bit;//bit associ au noeud (0 ou 1) Arbre filsD;//lien vers le fils de droite Arbre filsG;//lien de fils de gauche} Noeud; Bien sr cela ne suffit pas, il faut adjoindre cette dfinition/dclaration des fonctions. A

cet effet, voici les fonctions de base : Arbre nouvelArbre(unsigned char c,int b,int f) {//cre un nouveau noeud par allocation dynamique de mmoire Arbre a=(Noeud*)malloc(sizeof(noeud)); a->caractere=c; a->frequence=f; a->bit=b; a->filsD=NULL;//les fils sont vides (NULL par convention) a->filsG=NULL; return a; } Booleen estArbreVide(Arbre a) //renvoie FAUX si a NULL {//et VRAI sinon return ((a==NULL)?VRAI:FAUX); }

La dernire fonction (recherche dun caractre dans un arbre) est complexifie du fait de lexistence dun caractre NULL dans une feuille qui peut tre confondu avec un nud qui lui ne contient effectivement aucun caractre (cf figure 7 par exemple). Quant aux autres fonctions prsentes au sein du fichier arbre.h, elles sont spcifiques la compression de Huffman et seront dtailles plus loin (la fusion de 2 arbres notamment) 2.2/ Liste chane Considrons un rpertoire tlphonique de taille prdfinie: 100 noms. Pour modliser cette structure en C, on peut dclarer un tableau statique : Nom repertoire[100];

Imaginons que nous voulions laisser lutilisateur spcifier lui mme la taille du tableau N au dbut du programme. Nous comprenons aisment que les relations dun homme daffaires sont bien plus tendues que celle dun enfant de huit ans. On a alors recours une allocation dynamique de mmoire repertoire=(Nom *)malloc(N*sizeof(Nom)); On saperoit facilement que si le tableau nest pas compltement rempli, il y a un gaspillage de mmoire, les places non utilises ayant t dclares. Que faire si le tableau est dj rempli et que la personne veut rajouter un nouveau numro de tlphone ? Cest un peu ce qui se passe avec notre tableau darbres (lors de la construction de larbre final : on enlve les 2 derniers nuds et on rajoute larbre somme ). Il faut dclarer un autre tableau et dclarer

inutilement encore des octets de mmoire... Do lide de mettre en oeuvre une structure beaucoup plus souple qui autorise une naissance-une mort dans les numros de tlphones : les listes (simplement) chanes. En voici une modlisation simple applique notre problme denveloppe convexe. (figure 11)

Figure 11 Liste chane Chaque bloc/lment : possde deux champs ; un contenant linformation stocker et un autre qui est un pointeur (le lien ) vers le bloc/lment suivant. Il faut galement savoir o se trouve le dbut : il y a donc un pointeur simple appel Entre qui stocke ladresse du premier maillon. Enfin lorsquil ny a plus dlment, le champ lien du dernier

bloc pointe vers NULL par convention. On comprend aisment que linsertion dun nouvel lment (lopration denlistage) est trs simple (figure 12) :

Figure 12 Enlistage Les ajouts en dbut et fin de liste sont des cas particuliers prendre en compte. Pour dlister, on procde de la faon suivant (figure 13) :

Figure 13 Dlistage Une fois de plus le dlistage du premier maillon ou du dernier sont spcifiques.

Dans les deux cas (enlistage & dlistage) , on voit bien que ce type de structure de donnes autorise une gestion dynamique bien plus souple que les tableaux classiques. Limplmentation en C du concept de liste linaire nest pas trop complexe si on matrise correctement la notion de pointeur. Voici une partie du header concernant les listes chanes : typedef struct element *Liste;//liste = ptr vers element typedef struct element { Arbre a; Liste lien;} Element; Booleen estListeVide(Liste); Liste enlister(Liste,Arbre);//enlistage (tri par insertion) Liste delister(Liste,Arbre);//dlistage int nombreElementsListe(Liste);

Le lecteur trouvera en annexe la totalit du code source de lapplication et par consquent les dtails concernant les fonctions du header ci dessus. 2.3/ Compression Le programme C suit bien sr les tapes indiques en 1.2. 2.3.1/ Etude statistique Cette premire partie est la plus simple. En effet, ltude statistique du fichier passe par la cration dun tableau statique de 256 lments (nombre de caractres ASCII) de type Caractere.

typedef struct caractere {

int nbits;//nombre de bits int frequence;//nombre doccurences int codeHuffman;//code de Huffman attribu }Caractere; On choisit de calculer le nombre doccurences (de type int) plutt que la frquence (de type float ou double) pour des raisons de rapidit. De plus, le fichier est plac dans un buffer (cela permet dviter des appels ultrieurs fread qui est trop lente) et le tableau de Caractere actualis en consquence. La portion suivante ajoute un dcompte du nombre de caractres diffrents dont nous avons besoin pour len-tte : Caractere tableau[256]={0};//tableau de 256 Caractre int nbdifferents=0;

int i=0; char c; int sizeuc=sizeof(unsigned char); ... ...//initialisation de FILE *fichier fseek(fichier,0,SEEK_SET);//on se met au dbut du fichier bufferfichier=(char *)malloc(taille*sizeuc);//buffer fichier while(fread(&c,sizeuc,1,fichier))/ /tant quil y a lire { if(tableau[c].frequence==0)//si caractre pas dj vu nbdifferents++;//on augmente le nb de diffrents (tableau[c].frequence)++;//on augmente la frquence bufferfichier[i]=c;//remplit le buffer i++;//on passe la place suivante dans le buffer

} On aura compris que tableau[c] contient les informations relatives au cime caractre ASCII. 2.3.2/ Larbre de Huffman On utilise pour cela une liste chane darbres binaires o les noeuds contiennent tous les lments du type Caractere sauf le champ codeHuffman remplac par un champ bit mis 0 lors de la cration de la liste. On aurait pu crer un nouveau type Caractere2 rien que pour cela mais cela naurait fait quajouter la confusion. Cette liste est initialise par des arbres contenant un seul et unique noeud (voir figure 3). Le tri est fait par nombre doccurences croissant. Lide est de parcourir le tableau des 256 caractres rsultant de ltude statistique. Ds quun caractre ASCII a une frquence non nulle, un nouvel arbre est cr

et enlist la bonne place (ordre croissant des frquences). Voici le code C : Arbre a,fusion; Liste caracteres=NULL; for(i=0;ia)==ar)//si c'est le premier qu'on vire { l=l->lien;//l pointe vers le suivant free(ptrCourant);// on libre la mmoire return l; } ptrCourant=ptrCourant>lien;//sinon on passe au 2eme element while (estListeVide(ptrCourant)==FAUX)// tant que c'est pas le bon { if ((ptrCourant->a)==ar) { ptrPred->lien=ptrCourant>lien;//on saute l'elt dlist

free(ptrCourant); return l; } ptrPred=ptrCourant;//sinon on passe au suivant ptrCourant=ptrCourant->lien; } return l; } Liste enlister(Liste l,Arbre ar)//ar est l'arbre enlister {//les valeurs sont tries dans l'ordre croissant a priori Liste ptrCourant=l; Liste ptrPred=ptrCourant; Liste ptrNouvelElt; if((ptrNouvelElt=(Liste)malloc(siz eof(Element)))==NULL) perror("Erreur dans l'allocation memoire");//faut quand mme vrifier ptrNouvelElt->a=ar; ptrNouvelElt->lien=NULL;

if (estListeVide(l)==VRAI)//si la liste est vide return ptrNouvelElt; else//dans tous les autres cas { while (estListeVide(ptrCourant)==FAUX) { if ((ptrCourant->a)>frequence>ar->frequence)//si le {//nouveau trouve sa place ptrNouvelElt>lien=ptrCourant;//lien vers le next if ( ptrCourant!=l)//si c'est le premier { ptrPred>lien=ptrNouvelElt ; return l; } else//si cest le premier return ptrNouvelElt;

} ptrPred=ptrCourant;//sinon au suivant dtre tudi ptrCourant=ptrCourant>lien; } ptrPred>lien=ptrNouvelElt;//si le nouveau est le dernier return l; } } void incrementerFrequence(unsigned char c,Liste l) { Liste PtrCourant=l; while(((PtrCourant->a)>caractere)!=c) PtrCourant=PtrCourant->lien; (PtrCourant->a)->frequence++; } int nombreElementsListe(Liste l)

{ int nb=0; Liste l1=l;//pointeur vers Element courant while(estListeVide(l1)==FAUX)//tan t qu'on n'est pas au bout { nb++;//on augmente le nombre l1=l1->lien;//on passe au suivant } return nb; } 4.5/ Caractere.h #ifndef CARACTERE_H #define CARACTERE_H typedef struct caractere {int nbits; int frequence;

int codeHuffman; } Caractere; #endif 4.6/ Huffman.c #include //Compression de Huffman par GoldenEye #include #include #include "arbre.h" #include "liste.h" #include "caractere.h" #define SIZE_UC sizeof(unsigned char) #define SIZE_UI sizeof(unsigned int) #define SIZE_US sizeof(unsigned short) const int SIZEEX=SIZE_UC