Les créateurs de cet algorithme sont Abraham LEMPEL et Jakob ZIV. Ils créent d’abord en 1977 le code LZ77. L’année suivante, ils créent le compresseur LZ78 spécialisé dans la compression d’images. C’est en 1984 que Terry WELCH de la société Unisys, le modifia pour l’utiliser dans ses disques durs, et rajouta donc son initiale à celles d'Abraham LEMPEL et de Jakob ZIV. Le LZW est né.
1) La table ASCII
La mémoire de l'ordinateur conserve toutes les données sous forme numérique. Il n'existe pas de méthode pour stocker directement les caractères. Chaque caractère possède donc son équivalent en code numérique : c'est le code ASCII (American Standard Code for Information Interchange – c’est-à-dire « Code Américain Standard pour l'Echange d'Informations »). Le code ASCII de base représentait les caractères sur 7 bits (c'est-à-dire 128 caractères possibles, de 0 à 127). Il y a maintenant 8 bits, donc 256 caractères possibles : de 0 à 255.
- Les codes 0 à 31 ne sont pas des lettres ou des symboles. On les appelle caractères de
contrôle car ils permettent de faire des actions telles que :
- retour à la ligne (CR)
- Bip sonore (BEL)
- Les codes 65 à 90 représentent les majuscules.
- Les codes 97 à 122 représentent les minuscules. Il suffit de modifier le 6ème bit pour passer des majuscules aux minuscules, c'est-à-dire ajouter 32 au code ASCII en base décimale.
2) Fonctionnement de l'algorithme
Exemple :
Nous allons coder la chaîne CHAD CHAD CHAD CHAD CHAD.
| Octet lu | Tampon | La séquence est- elle apprise ? | Adresse de la séquence apprise | Séquence renvoyée (code ASCII) |
|---|---|---|---|---|
| C | C | Non | - | - |
| H | CH | Oui | 258 | C (67) |
| A | HA | Oui | 259 | H (72) |
| D | AD | Oui | 260 | A (65) |
| "espace" | D"espace" | Oui | 261 | D (68) |
| C | "espace"C | Oui | 262 | "espace" (32) |
| H | CH | Non | - | (256 = 100000000) |
| A | CHA | Oui | 263 | CH (258) |
| D | AD | Non | - | - |
| "espace" | AD"espace | Oui | 264 | AD (260) |
| C | "espace"C | Non | - | - |
| H | "espace"CH | Oui | 265 | "espace"C (262) |
| A | HA | Non | - | - |
| D | HAD | Oui | 266 | HA (259) |
| "espace" | D"espace" | Non | - | - |
| C | D"espace"C | Oui | 267 | D"espace" (261) |
| H | CH | Non | - | - |
| A | CHA | Non | - | - |
| D | CHAD | Oui | 268 | CHA (263) |
| "espace" | D"espace" | Non | - | - |
| C | D"espace"C | Non | - | - |
| H | D"espace"CH | Oui | 269 | D"espace"C (267) |
| A | HA | Non | - | - |
| D | HAD | Non | - | HAD (266) |
3) Etude de lignes spécifiques
-
Lignes 2 et 3
Octet lu Tampon La séquence est- elle apprise ? Adresse de la séquence apprise Séquence renvoyée (code ASCII) H CH Oui 258 C (67) A HA Oui 259 H (72) Ici, il faut suivre la partie droite du schéma représentant l’algorithme LZW car la séquence lue n’est pas connue.
Pour la première ligne du tableau ci-dessus, le tampon contient CH, qui n’est pas dans la bibliothèque. Il va donc enregistrer la séquence CH sous l’adresse 258. Ensuite, il renvoie la séquence apprise (CH) sans le dernier octet (H) : il renvoie donc C.Pour la deuxième ligne, on vide le tampon (sauf le dernier octet, ici H) et on prend l’octet suivant : A. La séquence apprise est donc HA sous l’adresse 259.
-
Ligne 7
Octet lu Tampon La séquence est- elle apprise ? Adresse de la séquence apprise Séquence renvoyée (code ASCII) H CH Non - (256 = 100000000) La séquence CH étant déjà apprise, il ne devrait pas y avoir de séquence renvoyée. Cependant, puisque c’est la première fois qu’une séquence enregistrée est répétée, on renvoie la séquence 256.
-
Ligne 9
Octet lu Tampon La séquence est- elle apprise ? Adresse de la séquence apprise Séquence renvoyée (code ASCII) D AD Non - - La séquence AD étant déjà apprise, rien n’est renvoyé.
-
Ligne 24 (Dernière ligne)
Octet lu Tampon La séquence est- elle apprise ? Adresse de la séquence apprise Séquence renvoyée (code ASCII) D HAD Non - HAD (266) La séquence HAD est déjà apprise. Théoriquement, rien ne devrait être renvoyé, mais puisque c’est la dernière ligne, il faut renvoyer tous les octets du tampon.
4) Résultat de la compression
Avant la compression, notre chaîne faisait 24 octets.
Après la compression LZW, notre chaîne tient : 5x8 + 9x9 = 121 bits soit 16 octets.
On a donc un quotient de compression de 1,5 , un taux de compression de 67% et un gain de compression de 33%.
5) Les limites de la compression LZW
Comme la compression RLE, mais en moindre mesure, la compression LZW ne sera pas rentable s’il n’y a pas assez de répétitions.
- Dans le domaine de la compression d’images, la compression LZW est relativement peu efficace.
- Un exemple de compression où la compression LZW est inefficace :
La chaîne « CHAD » fait non compressée 4 octets. Après compression, elle fait toujours 4 octets, aucune séquence apprise n’étant utilisée.
6) Utilisation
La compression LZW est à l’origine de plusieurs implémentations pour les modems bas débit (56k) fonctionnant avec la norme V42 bis, pour le format d’images GIF, ou dans de nombreux logiciels de compression comme PKZIP, ARC, Winzip, Winrar, …