Informatique TP 43 - Algorithme de Huffman 1/2

Le but de ce TP est implémenter l’algorithme de Huffman (appliqué à des caractères représentés sur un
octet) en OCaml, et à le tester en compressant le texte intégral de "À la recherche du temps perdu", qui fait
plus de 7Mo.
Dans un second temps, chez vous, vous pouvez combiner Huffman et LZW, en appliquant d’abord l’al-
gorithme LZW, puis l’algorithme de Huffman à l’échelle de l’octet ou bien de la taille des codes LZW (cette
deuxième option donne une meilleure compression, mais l’arbre de Huffman est sensiblement plus gros et
donc sa sérialisation est aussi plus grosse).
On utilisera pour calculer l’arbre de Huffman le module [Link] (avec son interface précisée dans
[Link] qui implémente les files de priorité mutables 1 .
Les arbres préfixes (dont l’arbre de Huffman que l’on veut calculer) seront définis ainsi :
1 type arbre = Feuille of int | Noeud of arbre * arbre
L’entier entre qui étiquette chaque feuille correspond au code d’un caractère. On se donne de plus une
fonction nb_occurences : in_channel -> int Array telle que
nb_occurences entree renvoie un tableau de taille 256 contenant le nombre d’occurences de chaque octet
dans le flux entree.
On utilisera, pour lire dans un fichier, les fonctions open_in : string -> in_channel,
input_byte : in_channel -> int et close_in : in_channel -> [Link] rappelle que la fonction
input_byte lève l’exception End_of_file si le flux d’entrée est terminé.
On utilisera, pour écrire dans un fichier, les fonctions open_out : string -> out_channel,
output_byte : out_channel -> int -> unit et close_out : out_channel -> unit.
1. Construction de l’arbre et de l’encodage :
(a) Écrire une fonction arbre_huffman : int array -> arbre qui construit l’arbre de Huffman as-
socié aux nombre d’occurences de chaque caractère dans un texte, en utilisant une file de priorité.
Parmi les 256 octets possibles, on ne mettra dans l’abre que ceux qui apparaissent au moins une fois
dans le fichier.
Indication : Une fois la file de priorité construite, il peut être pertinent d’utiliser une fonction récursive
sans argument (car elle aura des effets de bords sur cette file de priorité) pour calculer l’arbre. Ceci
peut être plus facile à écrire qu’avec une boucle.
(b) Écrire une fonction tableau_encodage : arbre -> int list array qui, étant donné un arbre
correspondant à un code préfixe sur les octets, calcule un tableau de 256 listes correspondant aux
codes définis par l’arbre pour les caractères. 2 .
2. Compression :
(a) La sérialisation consiste à définir, pour un type de données, une fonction qui écrit chaque valeur
distincte de ce type comme une chaîne de caractère différente, tel qu’il soit ensuite possible d’inverser
cette fonction.
Pour un terme d’une structure inductive, écrire en entier le terme pourrait convenir, mais on cherche
en général à économiser de la place plutôt qu’à faciliter la lecture par un humain.
Proposer une sérialization pour les arbres préfixe.

1. On considère un tas binaire, qui est un arbre binaire complet, et on le représente comme un tableau dont les cases sont
les étiquettes de ses nœuds dans l’ordre d’un parcours en largeur.
2. Si vous cherchez à gagner en efficacité : plutôt qu’une liste, utilisez un couple d’entiers, le premier étant l’entier dont le
code est la représentation binaire, et le second la taille en bits du code.

MP2I 2024-2025 Nath François

Informatique TP 43 - Algorithme de Huffman 2/2

(b) Écrire une fonction serialize : out_channel -> arbre -> unit qui prend en argument un flux
de sortie et un arbre préfixe. On fait la sérialisation en énumérant les nœuds de l’arbre de façon préfixe
avec la façon suivante :
• Les nœuds internes sont représentées par un octet à 0 ;
• les feuilles sont représentées par un octet à 1 suivi de l’octet qui les étiquette.
(c) Écrire une fonction extract_byte : int list -> int * int list qui étant donné une listes de
bit correspondant à des bits déjà lus, en extrait les 8 premiers sous la forme d’un entier (on prend
les bits en gros bout), et renvoie cet entier ainsi que le reste de la liste.
Par exemple, extract_byte [0; 0; 1; 0; 1; 0; 1; 0; 1; 1] = (42, [1; 1]).
Si la liste ne contient pas aux moins 8 bits 3 , on fait comme si tous les bits manquant valaient 0.
Cette fonction servira à traiter le buffer de bits correspondant à des codes calculés mais pas encore
écrits dans la sortie.
(d) Écrire une fonction
huffman : in_channel -> out_channel -> int list array -> int list -> unit
qui prend en argument un flux d’entrée contenant le texte à compresser, un flux de sortie sur lequel
écrire le texte compressé, le tableau indiquant le code de chaque caractère, et la liste d’entiers buffer
indiquant les bits à écrire qui ne forment pas encore un octet complet.
Indication : Il est recommandé de :
• Si le flux d’entrée est fini, écrire le buffer actuel sur la sortie ;
• sinon, si le buffer contient 8 bits ou moins, lire le prochain octet du flux d’entrée ;
• sinon, le buffer actuel contient au moins 9 bits : écrire un octet dans le flux de sortie. Ceci garanti
que le nouveau buffer ne sera pas vide.
(e) Écrire une fonction compresse : bool -> string -> string -> unit qui prend en argument le
nom du fichier source et le nom souhaité du fichier de destination. Cette fonction compresse le fichier
source en suivant l’algorithme de Huffman, en utilisant les deux fonctions précédentes. Elle encode
dans cet ordre les informations suivantes :
• un entier, représenté sur 8 octets, indiquant le nombre d’octets dans la source ;
• l’arbre de Huffman, encodé avec serialize ;
• l’encodage du contenu de la source, obtenu avec huffman.
Tester cette fonction sur le fichier [Link]. Quel est le gain d’espace ? Comparer avec ce
qu’on obtient avec la compression au format .zip.
3. Décompression :
(a) Écrire une fonction deserialize : in_channel -> arbre qui calcule l’arbre dont les feuilles sont
étiquettées par des caractères, encodé dans le flux en entrée 4 .
(b) Écrire une fonction buffer_of_byte : int -> int list qui étant donné un entier, le transforme
en la liste des 8 bits (même s’il y a des 0 de poids fort) de sa représentation binaire, toujours écrite
en gros bout comme pour extract_byte.
(c) Écrire une fonction
huffman_inv : in_channel -> out_channel -> int -> arbre -> int list -> unit
qui prend en argument un flux d’entrée contenant le texte à décompresser, un flux de sortie sur lequel
écrire le texte décompressé, le nombre d’octets restant à lire, l’arbre préfixe indiquant le codage utilisé,
et la liste buffer indiquant les bits déjà lus mais pas encore décodés.
Il peut être pertinent d’écrire une fonction récursive auxiliaire pour parcourir l’arbre.
(d) Écrire une fonction decompresse : string -> string -> unit qui prend en argument le nom
d’un fichier compressé avec ce programme, et le nom souhaité du fichier décompressé, et effectue la
décompression.
Tester votre fonction avec [Link], le résultat de la compression précédente.
3. Ce qui arrivera uniquement à la fin du texte.
4. Comme on l’a vu en montrant qu’un ABSNV dont les feuilles et les nœuds internes avait des étiquettes distincts, cette
fonction arrêtera de consommer des octets du flux exactement à la fin de la sérialisation de l’arbre de Huffman, et juste avant
le début du texte compressé.

MP2I 2024-2025 Nath François