Vidéo et imagerie numérique - Compression LZW

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é.

Trucs & astuces pertinents trouvés dans la base de connaissances

21/09 17h38	Le format GIF est soumis à une licence (Mythes et légendes)
Plus d'astuces sur « LZW »

Discussions pertinentes trouvées dans le forum

08/03 20h01	Aide à programmer LZW en C	Développement	23/11 15h54->sebsauvage	2
Discussion fermée Problème résolu		Plus de discussions sur « LZW »