Cyril Nicaud
Laboratoire d'Informatique Gaspard Monge (LIGM)
Université Paris-Est
 
Accueil Research Cours Divers



Compression -- TP 1
Implantation de Huffman : codage

Langages recommandés : Java ou Python. Demandez-moi avant si vous souhaitez utiliser un autre langage de programmation.

I. Ecrivez une méthode qui prend en argument une structure itérable de "symboles" (les symboles sont des objets qu'on peut distinguer, comparer) et qui retourne un tableau associatif (ou HashMap) qui a un symbole associe son nombre d'occurrences.

II. Implantez l'algorithme de Huffman qui crée l'arbre à partir des symboles et de leurs fréquences. On veillera à implanter l'algorithme de façon efficace.

III. Créez l'association symbole -> séquence binaire et encodez le message sous forme d'une suite de 0 et de 1. Dans un premier temps, utilisez un charactère pour 0 et un pour 1 (pas de gestion bit à bit).

IV. Testez votre programme sur ce fichier, où chaque caractère est un symbole. Quel taux de compression obtenez-vous ?

V. Toujours sur le même fichier, faîte du codage par bloc de 2 lettres (un symbole = 2 lettres consécutives). Que taux de compression obtenez-vous ?

(VI.) On souhaite faire un "Huffman sur les mots" où les symboles sont soit des mots entiers, soit des séquences de ponctuations-espaces. Par exemple le texte "ceci est : un exemple" sera découpé en symboles de la façon suivante : ['ceci',' ','est',' : ','un',' ','exemple']. Appliquez votre programme à ce découpage, quel est le taux de compression ? Et si on utilise deux arbres séparés, un pour les lettres et un pour les ponctuations ?





Compression -- TP 2
Implantation de Huffman : décodage

Assurez-vous d'avoir traité les questions I. II. et III. du TP 1 avant de commencer ce TP.

I. Faîtes une série de méthodes pour pouvoir écrire en binaire dans un fichier en passant les bits un par un (ou par un itérable de bits). En python on pourra utiliser que si s est une chaîne de 8 caractères 0 ou 1, on la transforme en un entier x (entre 0 et 255) et on l'écrit avec :

f = open(file,"wb")
x = int(s,2)
f.write(struct.pack('@B',x))
f.close()
Pour récupérer :
f = open(file,"rb")
x = struct.unpack('@B',f.read(1))[0]
f.close()
s = bin(x)[2:].zfill(8)

Il faut bien entendu inclure le package pack.

II. Modifiez la question II. du TP 1 pour pouvoir écrire l'encodage bit par bit.

III. Implantez l'algorithme d'encodage de l'arbre de Huffman vu en cours.

IV. Terminez l'implantation du codeur (calcul du nombre de bits parasites, etc).

V. Implantez le décodeur.





Compression -- TP 3
Implantation de Huffman : fin

I. Finalisez votre compression par Huffman, qu'il soit capable de compresser / décompresser un fichier (pas trop long).

II. Faîtes un programme qui crée un texte aléatoire où chaque bit est à 0 avec probabilité p et à 1 avec probabilité 1-p. Comparez les résultats obtenus en compressant un tel texte par Huffman et par Huffman par blocs (de taille 2, 3, ...) à la borne inférieure théorique donnée par l'entropie.

III. Faîtes un programme qui prend un texte t en entrée et crée la chaîne de Markov d'ordre 1 associée, comme vu en cours. Ecrivez également un programme pour générer aléatoirement un texte avec la chaîne de Markov (en donnant en paramètre le caractère de départ et la longueur du texte généré.





Compression -- TP 4 et 5
Projet

Le sujet est ICI.



Compression -- TP 6
Burrows-Wheeler et Move-to-Front

I. Implantez la transformée de Burrows-Wheeler, sans trop vous soucier des performances.

II. Implantez la transformée inverse de Burrows-Wheeler, de façon efficace (cf exercice 7 du TD 3)

IV. Implantez Move-to-Front et son inverse, de façon efficace.

V. Faire un compresseur à la bzip2 en combinant BWT, MtF et Huffmann.

VI. Améliorez les performances de I. pour qu'il puisse traiter le texte etranger.txt en moins d'une minute.