Travaux Pratiques du L1 année 2001-2002

Codage de Huffman



Objectif :  Implanter l'algorithme de construction du code de Huffman associé à la distribution des caractères d'un fichier texte ainsi que les opérations d'entrée/sortie relatives aux arbres binaires. Les structures sont données à titre indicatif dans la section [1],  pour mémoire l'algorithme de Huffmann est en section [ 5 ].
 

Durée : 6 heures.

Mots clefs : arbre binaire, codage de Huffmann, compression..

[ 1 ]  Structures
 

typedef  struct noeud{ int poids; char car;
                       struct noeud *gauche, *droit} NOEUD, *ARBRE;

typedef  ARBRE  HAIE[256];

typedef  int    TABLE[256];

[ 2 ]  Première séance
TABLE  Distribution( FILE *src)
               Il s'agit de calculer la distribution des lettres d'une source.

ARBRE  Huffman(  TABLE t )
             Arbre de Huffmann de la distribution t

void   Code( ARBRE a )
      imprime le code préfixe associé à l'arbre a


[ 3 ]  Deuxième séance
 

char *  ArbreVersChaine( ARBRE a )
    construit une représentation préfixe de l'arbre a.

ARBRE  ChaineVersArbre( char * s)
    opération inverse de la précédente.

void AfficheTexte( ARBRE a)
        imprime le squelette de l'arbre a en mode texte,

[ 4 ]   Complément
 
 
void AfficheTeX( ARBRE a)
    comme AfficheTexte mais avec du code TeX-PS-tricks.


[ 5 ] Algorithme
 

Huffmann( TABLE t )
HAIE  h
INDICE i, n;
DEBUT
   n := TAILLE( t )
   i := 1;
   initialisation de la haie.
   TANT QUE ( i <= n )
      h[i] := InitArbre( i, t[i] );
      INC( i );
   FTQ
   par fréquence décroissante
   TRIER( h , n );

   i  : = n
   TANT QUE ( i > 1 )
     on greffe les noeuds les moins fréquents
      h[i - 1] := Greffe( h[i - 1], h[i] );
      remise en ordre
      ORDONNER( h, i );
      DEC( i );
   FTQ
   RETOURNER h[ 1 ]
FIN


[ 6 ] Liens

Philippe Langevin,

Novembre 2002.