Introduction¶

Objectif¶

L'objectif de ce TP est de faire un programme mp2zip.exe qui nous permettra d'exécuter

mp2zip comp fichier pour compresser un fichier en un fichier fichier.mp2zip par Huffman
mp2zip decomp fichier.mp2zip pour décompresser un fichier compressé précédemment par Huffman.

Modules¶

Pour cela, on va découper le TP en plusieurs sous-parties qui seront codées pour certaines dans des modules.

On a déjà vu les modules en OCaml quand on a utilisé par exemple List, Printf ou encore Graphics. Pour simplifier, on va utiliser dune ici et en compilant le projet, si on a un fichier monfichier.ml on pourra accéder aux fonctions et types définis avec Monfichier.mafonction.

Donc, pour vous, tout se passe comme si on travaillait avec plusieurs fichiers .c comme on a pu le faire, sauf qu'il n'y a pas besoin de faire de .h : tout le contenu est accessible à côté. En utilisant la syntaxe Module.fonction on n'a pas besoin de faire l'équivalent de #include (c'est open Module qui joue ce rôle, mais comme pour les from module import * en Python, on évite).

Remarque : on pourrait vouloir cacher une partie de l'interface aux appelants, comme on peut le faire avec un .h qui ne rend pas tout visible. C'est possible en OCaml, on crée pour ça un fichier .mli contenant l'interface. Ici, on bénéficie juste d'un mécanisme de OCaml pour générer des interfaces maximales par défaut.

Note : il faut créer dans votre répertoire pour le TP :

un fichier mp2zip.ml qui sera le programme principal et qui appellera les fonctions des autres modules
un fichier dune avec le contenu :
```
(executable
    (name mp2zip))
```
si vous avez une erreur de PROJECT ROOT, un fichier dune-project contenant la ligne (lang dune 3.0)

Tas et files de priorité¶

On pourra utiliser les fichiers suivants :

tas.ml :

type 'a t = {
    elements : 'a array;
    mutable taille : int
}

let cree taille_max defaut = 
    { 
        elements = Array.make taille_max defaut; 
        taille = 0 
    }

let est_vide tas = tas.taille = 0

let taille tas = tas.taille

let pere a =
    if a = 0
    then failwith "racine"
    else (a+1)/2 - 1

let gauche a = 2*(a+1) - 1
let droite a = 2*(a+1)

let maximum tas = tas.elements.(0)

let nth tas i = tas.elements.(i)

let swap v x y =
    let t = v.(x) in
    v.(x) <- v.(y);
    v.(y) <- t

let ajoute x tas =
    let pos = ref tas.taille in
    tas.elements.(tas.taille) <- x;
    tas.taille <- tas.taille + 1;
    while !pos > 0 && nth tas (pere !pos) < nth tas !pos do
        let p = pere !pos in
        swap tas.elements p !pos;
        pos := p
    done

let max_pere_fils tas a =
    let max_courant = ref a in

    if tas.taille > gauche a 
        && nth tas (gauche a) > nth tas !max_courant
    then max_courant := gauche a;
    if tas.taille > droite a 
        && nth tas (droite a) > nth tas !max_courant
    then max_courant := droite a;
    !max_courant

let extrait_maximum tas =
    assert (tas.taille > 0);
    tas.taille <- tas.taille - 1;
    let x = tas.elements.(0) in
    if tas.taille > 0
    then begin
        let pos = ref 0 in
        tas.elements.(0) <- tas.elements.(tas.taille);
        while max_pere_fils tas !pos <> !pos do
            let max_fils = max_pere_fils tas !pos in
            swap tas.elements !pos max_fils;
            pos := max_fils
        done
    end;
    x

filePriorite.ml :

type ('a, 'b) t = ('b * 'a) Tas.t

let cree taille_max defval defprio = 
    Tas.cree taille_max (defprio, defval)

let ajoute file x p =
    Tas.ajoute (p, x) file

let retire file =
    let _, x = Tas.extrait_maximum file in
    x

Attention : Tas est un tas max, donc FilePriorite.retire renvoie l'élément de priorité maximale. Pour l'algorithme de Huffman, où l'on veut extraire les deux arbres de plus petites fréquences, on pourra utiliser comme priorité l'opposé de la fréquence.

Au secours, je n'ai pas dune¶

On peut simuler l'usage de plusieurs fichiers dans un seul en les emballant dans des modules :

module Tas = struct
    type 'a t = {
        elements : 'a array;
        mutable taille : int
    }

    let cree taille_max defaut = 
        { 
            elements = Array.make taille_max defaut; 
            taille = 0 
        }

    let est_vide tas = tas.taille = 0

    let taille tas = tas.taille

    let pere a =
        if a = 0
        then failwith "racine"
        else (a+1)/2 - 1

    let gauche a = 2*(a+1) - 1
    let droite a = 2*(a+1)

    let maximum tas = tas.elements.(0)

    let nth tas i = tas.elements.(i)

    let swap v x y =
        let t = v.(x) in
        v.(x) <- v.(y);
        v.(y) <- t

    let ajoute x tas =
        let pos = ref tas.taille in
        tas.elements.(tas.taille) <- x;
        tas.taille <- tas.taille + 1;
        while !pos > 0 && nth tas (pere !pos) < nth tas !pos do
            let p = pere !pos in
            swap tas.elements p !pos;
            pos := p
        done

    let max_pere_fils tas a =
        let max_courant = ref a in

        if tas.taille > gauche a 
            && nth tas (gauche a) > nth tas !max_courant
        then max_courant := gauche a;
        if tas.taille > droite a 
            && nth tas (droite a) > nth tas !max_courant
        then max_courant := droite a;
        !max_courant

    let extrait_maximum tas =
        assert (tas.taille > 0);
        tas.taille <- tas.taille - 1;
        let x = tas.elements.(0) in
        if tas.taille > 0
        then begin
            let pos = ref 0 in
            tas.elements.(0) <- tas.elements.(tas.taille);
            while max_pere_fils tas !pos <> !pos do
                let max_fils = max_pere_fils tas !pos in
                swap tas.elements !pos max_fils;
                pos := max_fils
            done
        end;
        x
end

module FilePriorite = struct 
    type ('a, 'b) t = ('b * 'a) Tas.t

    let cree taille_max defval defprio = 
        Tas.cree taille_max (defprio, defval)

    let ajoute file x p =
        Tas.ajoute (p, x) file

    let retire file =
        let _, x = Tas.extrait_maximum file in
        x
end

Huffman¶

Fichier huffman.ml

Ce fichier va contenir les fonctions liées à la création et l'utilisation du code de Huffman.

On va utiliser le type

type arbre = Char of int | Node of arbre * arbre

pour l'arbre.

On identifie ainsi complètement un caractère à l'octet, et donc l'entier entre 0 et 255, qui le représente.

Les occurrences de caractères seront données dans un tableau int array de 256 valeurs, où la ième valeur donne la fréquence du caractère de numéro \(i\). On aura alors des valeurs nulles pour les caractères non présents, elles seront ignorées lorsqu'on va construire l'arbre.

construit_arbre : int array -> arbre qui renvoie l'arbre de Huffman pour un tableau d'occurrences en utilisant l'algorithme glouton.
codes : arbre -> bool list array qui renvoie un tableau de 256 listes de booléens donnant le code de chacun des caractères avec la convention true = 1 = droite et false = 0 = gauche. On les donnera dans l'ordre de la racine vers la feuille, donc il faudra surement faire un List.rev sur l'accumulateur une fois la feuille atteinte.

Cas limites

On adopte la même convention que dans le cours sur les algorithmes gloutons :

si toutes les occurrences sont nulles (texte vide), il n'y a pas d'arbre et construit_arbre lève l'exception Invalid_argument ;
si un seul caractère c apparaît, construit_arbre renvoie Char c et le code de c est la liste vide.

Vérifier que vos fonctions respectent cette convention. Que vaut alors la compression d'une chaîne comme "aaaa" ? Pourquoi ne permet-elle pas, à elle seule, de retrouver la chaîne de départ ?

Compression¶

Fichier compression.ml

Pour compresser, on va adopter la stratégie suivante :

on calcule le tableau de fréquences d'une chaîne
on en déduit son arbre de Huffman
on calcule les codes de chaque caractère

Ainsi, on va écrire les fonctions :

stats : string -> int array qui renvoie le tableau de fréquences associé à une chaine de caractères passée en argument.
compresse : string -> Huffman.arbre * bool list qui renvoie l'arbre de Huffman et la compression de la chaine passée en argument.

Décompression¶

Fichier decompression.ml

Pour décompresser, on va adopter la stratégie suivante :

on lit l'arbre de Huffman
tant que la liste en entrée n'a pas été intégralement parcourue, on décode un caractère à l'aide de l'arbre et on l'ajoute

Ainsi, on va écrire les fonctions :

decompresse : Huffman.arbre * bool list -> string qui va adopter la stratégie précédente pour renvoyer la chaîne décompressée.

Remarque

D'après la question sur les cas limites, quand un seul caractère apparaît, la liste de bits est vide et la boucle précédente ne produit rien. On transmet donc aussi la longueur de la chaîne d'origine : compresse renvoie un triplet (longueur, arbre, bits) et decompresse décode exactement longueur caractères (avec l'arbre Char c, chaque caractère est décodé sans lire aucun bit). Pour la chaîne vide, on renvoie une longueur nulle et decompresse doit renvoyer "" sans consulter l'arbre : on pourra utiliser une valeur arbitraire, par exemple Char 0, ou un type option.

Lecture/Écriture dans des fichiers¶

Écrire/Lire des octets¶

On va avoir besoin d'ouvrir les fichiers en lecture binaire pour cela.

Remarque

La distinction binaire/texte dépend des plateformes. Il s'agit notamment de Windows qui traite différemment les sauts de ligne depuis les années 80 et qui oblige à pratiquer cette distinction.

En OCaml, les interfaces de fichiers sont différentes et la séparation est plus profonde.

On dispose ainsi de deux fonctions

open_out_bin : string -> out_channel
open_in_bin : string -> in_channel

pour ouvrir un fichier en mode binaire en écriture ou en lecture.

Pour écrire un octet, un int entre 0 et 255 en OCaml, on va utiliser :

output_byte : out_channel -> int -> unit

Pour lire un octet :

input_byte : in_channel -> int

Les fichiers sont toujours fermés au moment où la valeur est supprimée de la mémoire par le ramasse-miettes, mais on peut forcer la fermeture avec close_out et close_in. Pour un fichier en écriture, c'est une manière de s'assurer que tout a bien été écrit.

Sérialisation d'arbres binaires¶

On parle de sérialisation d'une structure de donnée quand il s'agit de l'écrire dans un fichier car on la présente alors sous la forme d'une série d'octets.

Pour sérialiser un arbre binaire strict, on peut remarquer qu'il est uniquement caractérisé par l'ordre préfixe de ses nœuds et feuilles.

On va supposer qu'on écrit dans le fichier

0<x><y> pour représenter Node(x,y) où <x> est la sérialisation de x.
1<c> pour représenter Char c

Exemple Écrire l'arbre dont la sérialisation est 0 1 0 0 1 1 1 2 (chaque chiffre représentant un octet).

En déduire deux fonctions :

output_arbre : out_channel -> arbre -> unit qui écrit un arbre dans un fichier ouvert en binaire
input_arbre : in_channel -> arbre qui lit un arbre

Compression au niveau octet¶

Modifier les fonctions précédentes pour que les données soient lues depuis un fichier puis écrites dans un fichier.

Pour réaliser les statistiques puis compresser, il va être nécessaire de relire le fichier, pour cela on peut utiliser :

seek_in inc 0 qui revient au début du fichier associé à inc : in_channel

Votre programme mp2zip devrait maintenant pouvoir être appelé ainsi :

mp2zip comp fichier va produire un fichier.mp2zip compressé
mp2zip decomp fichier.mp2zip va produire un fichier.out décompressé (un nom différent de fichier pour ne pas écraser en faisant des tests)

Remarque

On pourra modifier les interfaces précédentes ainsi :

stats : in_channel -> int array
compresse : in_channel -> out_channel -> unit
decompresse : in_channel -> out_channel -> unit

Pour lire un fichier jusqu'au bout on peut utiliser la structure :

try
    while true do
       let b = input_byte inc in
       ....
    done;
    failwith "Impossible"
with End_of_file -> ...

Compression au niveau bit¶

La compression précédente va faire augmenter sensiblement la taille des fichiers car on prend 1 octet pour 1 bit de données.

Adapter le code précédent pour regrouper les bits par octet, c'est-à-dire par paquet de 8.

Remarque

Ce n'est pas si simple car il va falloir temporiser les écritures et conserver des données en lecture pour ne pas passer à l'octet suivant.

Il y a également un problème pour les bits finaux : si jamais la taille n'est pas un multiple de 8, le dernier octet ne sera pas rempli entièrement, il faut donc un mécanisme pour gérer cela.

Écrire la longueur du fichier d'origine en tête du fichier compressé, comme suggéré plus haut, résout ce problème : on arrête la décompression dès que ce nombre de caractères a été produit. Penser à tester avec un fichier vide et un fichier ne contenant qu'un seul caractère répété.