Contexte :

La compression d’un fichier informatique désigne une procédure permettant de réorganiser le contenu de ce fichier dans le but de réduire sa taille, permettant ainsi de gagner de la place sur le disque dur, de transmettre plus rapidement ce fichier par le réseau, etc. (on peut par exemple penser aux fichiers d'extension .zip). Cette procédure repose principalement sur une transformation du contenu informatif du fichier afin de permettre une représentation plus petite de cette même information. Bien sûr, à cette procédure de compression correspond la procédure duale de décompression permettant de restituer le ficher dans son état d'origine avant compression.

Dans ce projet, on s'intéresse à la compression de texte, en étudiant un algorithme très simple de compression (codage LRE) consistant à remplacer dans un texte toute répétition de lettres par le nombre de répétition de cette lettre. Ainsi le texte aaaabbccccccaaaa sera transformé en un texte plus court a4b2c6a4

Ce qu'il faut réaliser :

• Un programme mettant en application l'algorithme de compression/décompression proposé ci-dessus.

Quelques pistes de réflexion :

• Comment évaluer l'efficacité d'une compression ?

• L'algorithme proposé est-il toujours optimal (ie. génère-t-il toujours un texte plus petit) ? Sur quel type de texte va-t-il bien fonctionner ?

• Identifier les défauts de l'algorithme proposé et proposer une (des) variante(s) basée(s) sur le même principe pour améliorer l'efficacité de la compression.

• Étudier (et implémenter ?) des algorithmes plus complexes (codage de Huffman, codage LZ77, codage LZMA, ...)

• Comprendre la différence entre compression sans perte et avec perte. Dans quelle catégorie se trouve l'algorithme proposé ? Être capable de citer d'autres exemples d'algorithme de compression.

• Quel rapport entre la notion de compression et celle d'archivage ?