Previous Up Next

5.1  Principes généraux

Nous allons utiliser le codage de Huffman que vous avez étudié en cours de codage au semestre précédent.

L’objectif de ces travaux pratiques est de construire deux filtres : l’un qui comprime un texte à l’aide du codage de Huffman et l’autre qui le décode. Ceci nécessite quatre étapes :

  1. Calcul des distributions de fréquence du texte ;
  2. Construction du code de Huffman correspondant ;
  3. Codage du texte et sauvegarde du code ;
  4. Décodage du texte.

Votre code utilisant l’allocation dynamique, il vous est conseillé de tester vos exécutables avec l’utilitaire valgrind.


Exercice 30 — Lecture de fichier.


Pour nous simplifier la vie dans la suite, nous allons faire une compression en deux passes (2 lectures de fichier — on parle d’algorithme de Huffman semi-adaptatif dans ce cas). Pour ce faire, donnez le code d’un programme C qui ouvre un fichier dont l’identificateur est passé en premier paramètre par le shell et affiche 2 fois ce fichier sur la sortie standard.

Vous pouvez utiliser les fonctions de la librairie standard :

#include <stdio.h>
FILE *fopen(char *filename, const char *mode);
int getc(FILE *stream);
int putchar(int c);
void rewind(FILE *stream);
int fclose(FILE *stream);



Figure 5.1: Arbre binaire représentand le code de Huffman pour le texte “example of Huffman coding” (les nombres correspondent aux fréquences d’apparition des caractères)



Pour tout commentaire : Alexandre Sedoglavic.
Previous Up Next