samedi 31 mai 2014

Tp compression de données

    L'objectif : implémenter une algorithme de compression capable de compresser des donnée de séquences d'ADN. Évidement je ne vous demande pas de chercher à comprendre ce qu'il y a derrière ces séquences mais juste d'être capable de les compresser...
Nous utiliserons le format « Fasta », c'est le plus simple : composée d'une entête d'une seule ligne, précédé du caractère « > », puis ensuite des lignes de 60 caractères sans espace composée. Attention les séquences contiennent principalement les caractères « a,c,g,t », mais pas seulement!... On verra en TP pourquoi... Voyez le fichier d'exemple « seq.fas » attaché à ce billet. Je vous conseille la méthode LZW en langage C, telle qu'on l'a vue en cours ensemble. Vous pourrez adapter cette méthode selon votre intuition. L'objectif de ce TP (en plus d'implémenter un algorithme de compression) est de tester votre autonomie, je donnerai donc quelques indices sur la méthode LZW et son implémentation en C, mais bien moins et bien moins détaillé que ce j'ai pu faire jusqu'à présent. Je veux que vous arriviez par vous même à organiser votre code, et à mettre en place vos stratégies de débuggage/tests. D'ailleurs, à ce propos, je vous conseille fortement de commencer par des fichiers d'exemple extrêmement simple (comme par exemple les données utilisées pour l'exemple dans le support de cours), et seulement une fois que ça fonctionne,alors, utiliser les fichier d'ADN pour tester plus a fond la méthode et surtout pour essayer d'améliorer la compression sur ce type de données.

Note importante : vous pouvez vous inspirer de méthodes déjà existantes et vous pouvez échanger vos idées entre vous, par contre vous devez tout coder vous même. Tout « copié-collé » venant d'un camarade ou d'internet est strictement interdit!

Format exigé et modalités de rendu

Votre programme doit prendre 3 paramètres et dans cet ordre :
  • « -c » ou « -d », respectivement pour signaler si vous voulez faire de la compression ou de la décompression
  • le nom du fichier d'entrée
  • le nom du fichier de sortie
exemple : pour compresser le fichier « seq.fas » dans un fichier appeler « seq.lzw », l'appel devra être comme ceci :
         ./monProgramme -c seq.fas seq.lzw
pour retrouver le fichier original dans « seq1.fas » :
         ./monProgramme -d seq.lzw seq1.fas
Votre programme sera évalué par un script, si vous ne suivez pas ces consignes votre note aura de grandes chance d'être 0 même si votre programme est correct....

Les modalités de rendu sont :
  • Un seul et unique fichier C , dont le nom est la concaténation des noms du binôme
  • Dans le mail d'envoi vous mettrez clairement les noms du binôme et quelques mots pour expliquer votre méthode (si vous avez fait quelque chose de différent de la méthode LZW, ou ce que vous aurez ajouté à cette méthode).
  • Vous utilisez le système d'accusé réception, pour vous assurer la bonne réception du message (ne comptez pas sur moi pour le faire pour vous.)
  • Date de rendu : lundi 18 mai, attention la dernière séance de TP sur le sujet sera la semaine précédente, je vous laisse le week-end pour finaliser votre travail. Le lundi 18 nous entamerons déjà le second TP du module, en Java.
Tout manquement à ces modalités pourra vous coûter des points, merci de les respecter, c'est ce qui va me permettre de pouvoir corriger rapidement...

Évaluation du travail

Il faut que la compression se fasse sans perte (j'utiliserai la commande unix « cmp » pour vérifier), et évidement vous devez arriver à compresser puis décompresser un fichier sans perdre un seul caractère (ni en ajouter). Ne donner qu'un programme de compression sans décompression amènera à la note 0 (et pas 10!). Le taux de compression que réalisera votre programme sera le point principal de la notation. Notez cependant que l'encombrement mémoire sera aussi évalué (taille que le programme occupe en mémoire), ainsi que la vitesse d'exécution. Comme à chaque fois, j'utiliserai valgrind pour détecter les erreurs et fuites mémoires (ce qui vous coûtera beaucoup de points si vous négligez cet aspect de la programmation).

Notez aussi que j'utiliserai d'autres fichiers d'ADN que celui d'exemple pour évaluer votre programme, ne vous « spécialisez » donc pas trop sur celui là...

Remarque : J'ai programmé une version sur 16 bit (en utilisant des « unsigned short int »), qui fait ~130 lignes et qui réduit la taille du fichier « seq.fas » d'environ 57% ,et en n'utilisant ~500 ko de mémoire (cette information est donné par Valgrind à la fin de son exécution). Ce programme s'exécute en moins de 5 secondes avec Valgrind (et moins de 2 secondes en exécution normale). Tout ça pour dire que ce n' est pas excessivement compliqué. Ces chiffres donnent une aussi une base de référence. Je pense que vous pouvez faire mieux.

Annexe(s):

seq.fas  :: 12.95 KB