Codage de Huffman
Durée : 6 heures.
L'objectif de cette feuille de travaux pratiques
est de construire un compresseur de Huffman complet qui prend en
entrée un certain nombre d'options : -a aide -s source
-o output -d decompression -c compression -t taux et , suivant les options
choisies compresse, decompresse une source s dans un fichier output.
Le sujet est long et tecnique mais il est aussi trés instructif,
les étudiants pourront travailler en groupe.
Mots clefs : arbre binaire, codage de Huffmann, compression..
[ 1 ] Structures
Pour assurer la compatibilité des codes, utiliser des structures compatibles avec les déclarations suivantes :
typedef struct noeud
{ int poids; char car;
struct noeud
*gauche, *droit} NOEUD, *ARBRE;
typedef ARBRE HAIE[256];
typedef int TABLE[256];
typedef char * CODE[256];
FILE *src, *dst;
char *source, *destination;
[ 2 ] Entrées-Sorties
void option( void)[ 3 ] Manipulation de bits
Traitement des options passées sur la ligne de commande.
Initialisation des variables globales.
void distribution(TABLE t);
Calcul de la distribution des caracteres.
int main(int argc, char * argv[]);
char GetBit( void), lecture d'un bit.[ 4 ] Arbres
void PutBit( char c), ecriture d'un bit.
void EcrireArbre( ARBRE a) Ecriture prefixe de l'arbre a
ARBRE LireArbre( void )
[ 5 ] Codes
ARBRE Huffman( TABLE t)
void LeCode( ARBRE a, CODE c)
[ 6 ] Codage et décodage
void compression( CODE c)Liens
void decompression( ARBRE a)