Pascal Mathis

Projet 50 heures
Compression de données

En 1977, Abraham Lempel et Jacob Ziv ont proposé un algorithme de compression d'usage général, indépendant des données. L'algorithme LZ a connu un large succès et se retrouve dans la plupart des compresseur actuel. Outre les utilitaires spécialisés (Arc, Pkzip, Lharc, Arj utilisés par exemple par Winzip de Windows), on peut citer les logiciels de sauvegarde (QIC-122 pour les sauvegardes à bandes, PC Backup, Norton Backup, MS Backup, Sytos), les protocoles de transmission haute vitesse par modem (V42bis), ainsi que les diverses implémentations intégrées aux systèmes d'exploitation (Compress sous Unix, gzip, Dblspace de Dos6).

   Cet algorithme est fondé sur la construction d'un dictionnaire dynamique qui peut être reconstruit automatiquement par le décompacteur à la volé c'est à dire au fur et à mesure que les données sont lues. Les mots du dictionnaire peuvent être codés sur un nombre de bits fixé à l'avance ou évoluant dynamiquement (comme par exemple dans le format d'image GIF).

   L'objectif de ce projet est de réaliser tout d'abord une petite étude sur la compression de données en général : méthodes utilisées, domaine d'application, performances, etc. La recherche d'informations peut avoir lieu à la bibliothèque et sur le réseau. Il s'agit ensuite d'implanter l'algorithme LZ, que l'on aura retrouvé sur le réseau par exemple, selon deux versions : une première avec les mots du dictionnaire codés sur un nombre fixe de bits et une deuxième avec une modification dynamique de la taille des mots. Chaque approche pose des problèmes : que faire lorsque le dictionnaire est plein, est-il raisonnable d'augmenter sans cesse la taille des mots, etc. Il est demandé d'indiquer clairement les choix possibles dans chaque approche, leurs avantages, inconvénients et de justifier les stratégies adoptées. Il faudra pour finir discuter les résultats obtenus en testant les deux programmes sur des données de natures différentes (textes, images, sons, etc.).