Lempel, Ziv and Welch

Algorithme utilisé par Up ! System

La répétition est recherchée entre le début du flux et la position courante dans le flux. La taille minimale d'une suite d'octets se répétant est deux octets. La taille minimale NbBitsMin d'un codage d'une suite d'octets dépend de la plage des valeurs de tous les octets :

• 2 bits si les valeurs sont comprises entre 0 et 1 - Cas d'une image en noir et blanc.
• 3 bits si les valeurs sont comprises entre 0 et 3 - Cas d'une image en 4 couleurs.
• 4 bits si les valeurs sont comprises entre 0 et 7 - Cas d'une image en 8 couleurs.
• 5 bits si les valeurs sont comprises entre 0 et 15 - Cas d'une image en 16 couleurs.
• 6 bits si les valeurs sont comprises entre 0 et 31 - Cas d'une image en 32 couleurs.
• 7 bits si les valeurs sont comprises entre 0 et 63 - Cas d'une image en 64 couleurs.
• 8 bits si les valeurs sont comprises entre 0 et 127 - Cas d'une image en 128 couleurs.
• 9 bits si les toutes les valeurs sont utilisées - Cas d'une image en 256 couleurs ou d'un fichier quelconque.
  

Au fur et à mesure de la compression, une table mémorisant l'association entre une suite d'octets et son codage est constituée.

Dès lors que la suite d'octets est reconnue dans le flux, on tente de la prolonger par l'octet suivant de la sorte de mettre un seul nouveau codage. A défaut, le codage de la suite précédemment reconnue est inscrit.

Il est possible de créer un nouveau codage tant que le nombre maximal de bits de celui-ci n'est pas atteint. En ce cas, la table mémorisant l'association entre une suite d'octets et son codage doit être réinitialisée.

Cet algorithme n'est pas une norme : rien ne définit quelle est la taille maximale de l'encodage - nombre de bits maximal - et quoi faire quand la table est pleine.

Ce paramétrage varie en fonction de l'application utilisant l'algorithme. Par exemple, la compression pour les images au format Graphics Interchange Format (GIF) de CompuServe est paramétrée de la manière suivante :

• NbBitsMin a pour valeur la profondeur de couleur de l'image i.e. le logarithme à base 2 du nombre de couleurs.
• NbBitsMax a pour valeur 12.
• Quand le code 2^NbBitsMin est lu, alors la table doit être réinitialisée même si elle n'est pas pleine.
• Quand la table est pleine, elle ne doit pas être réinitialisée tant que le code précédent n'est pas lu.
• Quand le code 2^NbBitsMin+1 est lu, alors le flux Lzw est terminé.
  

La convention retenue par défaut par Up ! System est la suivante :

• NbBitsMin a pour valeur 9.
• NbBitsMax a pour valeur 12.
• Quand le code 2^NbBitsMin est lu, alors la table doit être réinitialisée même si elle n'est pas pleine.
• Quand la table est pleine, elle ne doit pas être réinitialisée tant que le code précédent n'est pas lu.
• Quand le code 2^NbBitsMin+1 est lu, alors le flux Lzw est terminé.
  

Exemple d'un flux compressé par l'algorithme Lzw

Flux non compressé

Flux compressé