La compression LZW

Abraham Lempel et Jakob Ziv sont les créateurs du compresseur LZ77, inventé en 1977 (d'où son nom). Ce compresseur était alors utilisé pour l'archivage (les formats ZIP, ARJ et LHA l'utilisent).

En 1978 ils créent le compresseur LZ78 spécialisé dans la compression d'images (ou tout type de fichier de type binaire).

En 1984, Terry Welch de la société Unisys le modifia pour l'utiliser dans des contrôleurs de disques durs, son initiale vint donc se rajouter à l'abréviation LZ pour donner LZW.
LZW est un algorithme très rapide aussi bien en compression qu'en décompression, basé sur la multiplicité des occurences de séquences de caractères dans la chaîne à encoder. Son principe consiste à substituer des motifs par un code d'affectation (indice) en construisant au fur et à mesure un dictionnaire.

De plus, il travaille sur des bits et non sur des octets, il ne dépend donc pas de la manière de laquelle le processeur code les informations. C'est un des algorithmes les plus populaires, il est notamment utilisé dans les formats TIFF et GIF. La méthode de compression LZW ayant été brevetée par la société Unisys, c'est l'algorithme LZ77, libre de droit, qui est utilisé dans les images PNG.

Construction du dictionnaire

Le dictionnaire est initialisé avec les 256 valeurs de la table ASCII. Le fichier à compresser est découpé en chaînes d'octets (ainsi pour des images monochromes - codées sur 1 bit - cette compression est peu efficace), chacune de ces chaînes est comparée au dictionnaire et est ajoutée si jamais elle n'y est pas présente.

La compression

L'algorithme parcourt le flot d'informations en le codant; si jamais une chaîne est plus petite que le plus grand mot du dictionnaire alors elle est transmise.

La décompression

Lors de la décompression, l'algorithme reconstruit le dictionnaire dans le sens inverse, ce dernier n'a donc pas besoin d'être stocké.

Dernière modification le mardi 14 octobre 2008 à 17:40:32.Ce document intitulé « Compression MZW » issu de Comment Ça Marche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.