Projet

DUT Informatique 1 2014/2015
Programmation Python
Projet
---
benchmark pour bzip2
Le compresseur bzip2 (et son équivalent 7zip) est le compresseur le plus efficace sur des sources de type texte fortement
structuré (comme un texte en langue naturelle). Comme nous l’avons vu au cours des 4 derniers TP, cet outil est basé
sur une chaîne d’algorithmes dans laquelle chaque maillon a pour rôle de préparer le terrain pour le suivant, jusqu’au vrai
compresseur : le codeur de Huffman.
L’objectif de ce projet est de mettre en place ces différents maillons pour construire un banc d’essai (benchmark, en anglais)
modulaire permettant de tester les performances et déterminer quelle est la meilleure combinaison.
Ressources :
Vous aurez besoin de télécharger (http://igm.univ-mlv.fr/∼incerti/1415/DUT1/projet/) :
• le module iutk.py : attention, il y a quelques modifications ⇒ récupérez la nouvelle version
• le module huffsize.py : celui du TP12
• le corpus de textes : dans le répertoire http://igm.univ-mlv.fr/∼incerti/1415/DUT1/data/
La chaîne codeur/décodeur :
Puisqu’il s’agit d’un compresseur, il faut prévoir le décompresseur. Chaque maillon de la chaine de codage
devra donc avoir son symétrique dans la chaîne de décodage :
données ⇒
source
codeur1 ⇒ codeur2 ⇒ codeur3
←−
compresseur
données
⇒
⇒ compressées
−→
décodeur3 ⇒ décodeur2 ⇒ décodeur1
←−
décompresseur
⇒ données
source
−→
Etant donné que nous souhaitons ajouter ou enlever des maillons il faudra prendre soin à ce que les sorties
des uns soient compatibles avec les entrées des autres. Celà est relativement simple en python si l’on utilise
des structures itérables simples comme des list ou des string : ce qui fonctionne sur l’une peut fonctionner
sur l’autre. Ainsi tous les algorithmes devront pouvoir accepter en entrée ces deux structures de données et
produire en sortie soit l’une soit l’autre.
Les maillons :
1
Huffman : c’est le dernier maillon, celui qui sera toujours présent. Vous n’avez pas à le coder, juste à
utiliser le module huffsize.py qui vous est fourni (cf. TP12).
Cet algorithme fonctionne sur n’importe quelle source mais on peut montrer (théorie de l’information)
qu’il est particulièrement performant sur des sources présentant un alphabet restreint (peu de symboles)
et des distributions de probabilités très inhomogènes : un petit nombre de symboles très fréquents, un
grand nombre de symboles rares (cf. Exemples).
2
RLE : le codage par plage (ou Run-Length-Encoding -- cf. TP12) transforme une source en deux séquences
liées (une liste de symboles et une liste de longueurs) en repérant les plages constantes dans la source.
Il est donc particulièrement performant sur des sources présentant de longues plages, la situation idéale
étant une source triée.
3
MTF : l’algorithme Move-To-Front (cf. TP10) transforme une source en une séquence d’entiers. Sur un
texte brut, il a pour effet de transformer les motifs qui se répètent en plages constantes (mais courtes).
On peut vérifier qu’il donne les meilleurs résultats sur des sources triées. Si la source présente de longues
plages, il peut donc être un bon pré-traitement pour RLE.
La sortie de MTF est de même longueur que l’entrée, mais on peut vérifier que, bien souvent, le nombre
de symboles (taille de l’aphabet) est moindre en sortie qu’en entrée et que la distribution des probabilités d’occurrence de ces symboles est plus inhomogène en sortie qu’en entreée. Le MTF peut donc être
également un bon pré-traitement pour Huffman.
1
4
BWT : La Transformation de Burrows-Wheeler (cf. TP9) transforme une source structurée (présentant des
motifs) en une version presque triée en regroupant les symboles présents dans les motifs fréquents. La
sortie de BWT présentera donc de longues plages constantes. En outre, contrairement à un tri classique,
cette transformation est réversible.
Cet algorithme sera donc un excellent pré-traitement pour RLE ou MTF.
Votre programme :
Les différents algorithmes de la chaîne ont déjà été réalisés en TP. Il ne reste plus qu’à assembler le tout
proprement dans un programme modulaire permettant de définir, sur la ligne de commande, la chaîne de
traitement souhaitée.
• Les modules :
Votre projet devra être constitué de 7 modules (au moins) :
1
BWT.py : contient les fonctions BWT(data)→(code,line) et iBWT(code,line)→data
2
MTF.py : contient les fonctions MTF(data)→(code,alph) et iMTF(code,alph)→data
3
RLE.py : contient les fonctions RLE(data)→(lenlist,symlist) et iRLE(lenlist,symlist)→data
4
iutk.py : il vous est fourni (attention, nouvelle version à récupérer).
5
iutkhisto.py : affichage d’histogrammes. Déjà fait au TP10, mais vous pouvez l’améliorer...
6
huffsize.py : contient la fonction huffsize(data)→bitsize . Il vous est a été donné au TP12
7
projet.py : contient la fonction de gestion de la ligne de commande getargs(argv) (et tout ce qui va
autour -- cf.TP11) ainsi que le programme principal qui met en œuvre les options
• Les options :
Elles correspondent aux fonctionalités du programme. A chaque option courte doit correspondre une
option longue.
algos
source
général
short
-h
-t
-v
-H
-f
-l
-s
-b
-m
-r
long
--help
--time
--verb
--hist
--file=
--len=
--str=
--bwt
--mtf
--rle
param
filename
size
string
action
affiche une aide et quitte le programme
détermine et affiche les temps de calcul des principales étapes
active le mode "bavard"
affiche des histogrammes
ouvre le fichier <filename> en lecture et le charge comme texte source
limite la taille des données lues dans le fichier à <size> octets
charge la chaîne <string> comme texte source
intègre les algorithmes BWT (codeur) et iBWT (décodeur)
intègre les algorithmes MTF (codeur) et iMTF (décodeur)
intègre les algorithmes RLE (codeur) et iRLE (décodeur)
le mode "bavard" : sert essentiellement à vérifier les sources intermédiaires : sortie(s) d’un algorithme,
destinée(s) à être prise(s) en entrée par les algorithmes suivants. A vous de sélectionner et formater ces
affichages pour qu’ils soient pertinents et lisibles (l’affichage par défaut des list n’est pas très convivial...)
les histogrammes : ils sont utiles pour vérifier/comparer les distributions d’occurrences des symboles et
faire le lien avec les performances des différents algorithmes. Il faut donc choisir avec pertinence quels
histogrammes afficher.
le codage de Huffman : vous noterez qu’aucune option n’est prévue pour activer la fonction huffsize.
C’est tout simplement qu’elle devra être appliquée systématiquement sur la source d’entrée et sur la
sortie finale de la chaîne de codage (cf. exemples).
Vous pouvez intégrer d’autres options, du momment que vous indiquez clairement ce qu’elles font dans
la fonction d’aide.
2
• L’affichage minimal : (cf. exemples)
Votre programme devra afficher, au minimum les informations suivantes :
• la taille de la source et le taux de compression obtenu avec Huffman
• le nom des algorithmes utilisés
• le taux de compression final obtenu avec Huffman sur la sortie de la chaîne d’algorithme.
Attention : cf. section suivante.
Données d’en-tête :
Pour évaluer le taux de compression produit par une chaîne d’algorithme, il faut tenir compte des données
supplémentaires nécéssaires au décodeur pour mettre en œuvre la chaîne de décompression. Ces éléments
sont généralement ajoutées au début du fichier compressé dans ce que l’on appelle l’en-tête (header en anglais).
En particulier, il faut prévoir au moins un octet supplémentaire par algorithme pour préciser quel traitement
a été utilisé.
• BWT : le décodeur iBWT doit connaître, outre la séquence de sortie, le numéro de ligne où se trouve la
source dans la matrice de rotation triée.
Cette information (ici un entier sur 4 octets) doit donc être prise en compte pour le calcul de la taille
des données de sortie (en plus de l’octet indiquant que l’on doit commencer par iBWT). Ainsi, puisque
l’algorithme de Huffman donne très exactement la même chose sur la source et sur sa transformée
par BWT (vous pouvez vérifier), appliquer la chaîne BWT ⇒ Huffman coûtera 5 octets de plus que
simplement Huffman . Ca n’a donc aucun intérêt.
• MTF : le décodeur iMTF doit connaître, en plus de la séquence d’entiers produite par MTF, l’alphabet
de codage de la source. Cet alphabet n’a pas à être transmis car il peut être reconstruit sans problème
soit à partir de iRLE (la liste des symboles), soit par le décompresseur Huffman. On a donc juste besoin
d’un octet pour identifier l’algorithme.
• RLE : le codeur RLE produit juste deux listes qui seront directement recodées par l’algorithme de
Huffman. Le décompresseur Huffman fournira tout ce qui est nécessaire. Il n’y a donc aucune donnée
supplémentaire à prévoir, à part l’octet d’identification de l’algorithme.
• Huffman : la fonction huffsize prend en compte tout ce qu’il faut. Il n’y a rien à prévoir d’autre que
l’octet d’identification.
Dans votre programme il vous faudra donc prendre en compte la taille de ces données d’en-tête, pour
l’ensemble des algorithmes de la chaîne de traitement, et l’ajouter à la taille renvoyée par la fonction huffsize.
Quelques exemples :
Voici quelques exmples de ce que votre programme pourrait fournir. Ici, seul le codage est présenté et les
résultats sont affichés de manière trés sommaire. Votre programme devra être un peu plus "convivial" et
devra également réaliser le décodage et bien sûr vérifier que l’on retrouve bien la source initiale.
• $>python projet.py -s "ma*maman*mange*des*mangues*et*range*des*oranges" -b -m
Huffsize(src): 76.60%
BWT => MTF => Huffsize(MTF(BWT(src))): 76.60%
☞ Sur cet exemple les performances nulles sont dues à la très faible longueur de la source : l’ajout des
données d’en-tête détruisent le faible bénéfice de BWT+MTF.
• $>python projet.py -s "ma*maman*mange*des*mangues*et*range*des*oranges" -m
Huffsize(src): 76.60%
MTF => Huffsize(MTF(src)): 70.21%
☞ Le MTF seul est plus efficace (sur ce tout petit exemple !).
• $>python projet.py -f ../data/alice.txt -l 50000 -b -r
Huffsize(src): 56.43%
BWT => RLE => Huffsize(RLE(BWT(src))): 41.29%
3
• $>python projet.py -f ../data/alice.txt -l 50000 -m -r
Huffsize(src): 56.43%
MTF => RLE => Huffsize(RLE(MTF(src))): 69.96%
☞ La combinaison MTF+RLE, sans BWT, n’est manifestement pas une bonne idée...
• $>python projet.py -f ../data/dela.txt -l 120000 -trmb
Huffsize(src): 50.45%(0.016sec)
BWT(5.521sec) => MTF(0.085sec) => RLE(0.027sec) => Huffsize(RLE(MTF(BWT(src)))): 26.76%(0.007sec)
☞ Sur cet exemple la combinaison BWT+MTF+RLE fonctionne bien...
• $>python projet.py -f ../data/dela.txt -l 1000 -bmr --hist
Huffsize(src): 46.40%
BWT => MTF => RLE => Huffsize(RLE(MTF(BWT(src)))): 24.50%
☞ Indépendemment des résultats, on peut observer les histogrammes...
Rendu :
Le projet est un travail individuel.
Vous devrez le rendre, avant le Lundi 19 Janvier 2015, par mail ([email protected]), sous la forme d’un répertoire
DUT1.NOM.Prenom.PROJETPY/ archivé (.tar.gz, zip....).
Ce répertoire contientra l’ensemble des modules (au moins 7) utiles au bon fonctionnement de votre projet,
et éventuellement un fichier texte brut expliquant ce que vous avez fait, ce que vous n’avez pas fait, ce qui
marche, les problèmes que vous avez rencontré....
L’évaluation portera bien sûr sur les algorithmes vus en TP (leur fonctionnement, leur efficacité) mais aussi
et surtout sur la structuration du programme principal (son ergonomie).
Le respect du cahier des charges (ennoncé) est bien sûr très important, de même que le respect des "bonnes
pratiques du programmeur" (commentaires, docstring). Le format de rendu (nommage de l’archive, du répertoire, des modules) est aussi un élément pris en compte.
4

Download Report