L'objectif de ces travaux pratiques est de comprimer un texte à
l'aide du codage de Huffman. Ceci nécessite trois étapes :
Calcul des distributions de fréquence du texte ;
Construction du code de Huffman correspondant ;
Codage du texte.
Pour chaque étape, on vous demande de construire des fonctions
réalisant la tâche correspondante. Pour finir, vous construirez
un programme qui permet de saisir un texte sur l'entrée standard,
retourne le texte codée sur la sortie standard et le code de
Huffman sur la sortie d'erreur (pour faire simple à défaut
d'être élégant).
Calcul des distributions de fréquences du texte.
Tout d'abord, donnez la définition d'une fonction qui construit
une liste contenant l'ensemble des lettres utilisées dans le texte
ainsi que la fréquence d'occurrence de ces lettres.
Une distribution de fréquence est une application de la
forme :
f :
S
¾®
[0,1]
Ì R
x
¾®
f(x)
avec
å
x Î S
f(x)=1.
Dans notre cas la fréquence d'une lettre dans un texte est le
nombre d'occurrences de cette lettre divisée par le nombre total
de lettres.
Construction du code de Huffman.
L'algorithme de Huffman construit un arbre binaire qui permet
d'obtenir un codage optimal d'un texte.
Initialisation.
Pour commencer, on part d'une
forêt d'arbres binaires formés chacun d'une seule feuille.
Chaque feuille, contient une lettre et la fréquence
correspondante. Les fonctions de la section précédente ---
convenablement modifiée --- fournissent cette forêt codée par
une liste.
Itération.
Ensuite, on fusionne deux arbres dont
la fréquence est minimale. Cette opération consiste à
construire un nouvel arbre binaire qui a pour fils gauche l'arbre
ayant la plus petite fréquence et l'autre pour fils droit. La
fréquence associée à l'arbre ainsi obtenu est la somme des
fréquences de ces sous arbres.
Arrêt.
Notre processus se termine lorsqu'il ne
reste plus qu'un arbre dans notre forêt.
Codage du texte.
Nous disposons à présent d'un arbre représentant un code de
Huffman associé à un texte de départ ; chacune de ses feuilles
correspond à une lettre de texte. Pour obtenir le code
correspondant, on applique un algorithme de parcours d'arbre en
profondeur qui associe une suite de bits à une feuilles à partir
de sa position dans l'arbre :
à chaque bifurcation vers la gauche, on ajoute au codage de
la lettre le bit 0 ;
à chaque bifurcation vers la droite, on ajoute au codage de
la lettre le bit 1.
L'idée du codage repose sur le fait que les lettres les plus
répétées dans le texte sont proches de la racine par
construction de notre arbre et sont donc codées par le processus
ci-dessus sur un moins grand nombre de bits que leurs consoeurs.
Pour finir, vous pouvez par exemple construire une fonction qui
prend en entrée un arbre de Huffman et retourne une table
associant la lettre et son codage binaire optimal ; puis un
programme qui compresse notre texte.
