Lempel-Ziv-Welch
Un article de Wikipédia, l'encyclopédie libre.
LZW (pour Lempel-Ziv-Welch) est un algorithme de compression de données sans perte. Il s'agit d'une amélioration des algorithmes LZ77 (1977) et LZ78 (1978), tous les deux écrits par Abraham Lempel et Jacob Ziv. LZW fut créé en 1984 par Terry Welch, d'où son nom.
L'algorithme LZW avait été breveté par la société Unisys[1]. Il a été utilisé dans les modems (norme V42 bis) et est encore utilisé dans le format d'image numérique GIF.
[modifier] Principe
L'algorithme général est le suivant :
- Initialisation : un dictionnaire de mots prédéfini est rempli.
- Lecture :
- L'entrée est ajoutée au tampon un caractère à la fois TANT QUE le tampon contient des mots du dictionnaire
- Au premier caractère ajouté au tampon tel que le tampon ne correspond à aucun mot du dictionnaire, on ajoute un mot au dictionnaire de la forme A + B où A est un mot du dictionnaire et B un caractère, A est sorti du tampon et renvoyé.
- Fin de l'entrée : le tampon est renvoyé s'il n'est pas vide (il correspond à un mot du dictionnaire).
Notons que les codes binaires sont tout d'abord généralement émis sur 8 bits, jusqu'à ce que ces 8 bits ne suffisent plus à coder l'indice que l'on désire(par exemple l'indice 256, qu'il est nécessaire de coder sur 9 bits). On émet alors l'indice 0 pour signifier que l'on augmente le nombre de bits émis de 1.
Prenons un exemple. Supposons que la phrase à coder soit « repetition ». À chaque lettre est associé son code ASCII. Le dictionnaire est initialisé et associe l'indice 1 au code '0', l'indice 2 au code '1'.....etc jusqu'à l'indice 256 qui correspond au code '255'.
| Étape | Tampon | Émis | Rajout au dictionnaire |
|---|---|---|---|
| 1 | '114'+'101' (re) | '115' (r) | 257 : '114'+'101' (r-e) |
| 2 | '101'+'112' (ep) | '102' (e) | 258 : '101'+'112' (e-p) |
| 3 | '112'+'101' (pe) | '113' (p) | 259 : '112'+'101' (p-e) |
| 4 | '101'+'116' (et) | '102' (e) | 260 : '101'+'116' (e-t) |
| 5 | '116'+'105' (ti) | '117' (t) | 261 : '116'+'105' (t-i) |
| 6 | '105'+'116' (it) | '106' (i) | 262 : '105'+'116' (i-t) |
| 7 | '116'+'105' (ti) = '261' | '0' (besoin d'un bit supplémentaire) | Aucun ajout |
| 8 | '261'+'111' (tio) | '261' (ti) | 263 : '261'+'111' (ti-o) |
| 9 | '111'+'110' (on) | '112' (o) | 264 : '111'+'110' (o-n) |
| 10 | '110' (n) | '111' (n) | Pas d'ajout |
- Au début de la compression, les codes binaires seront émis sur 8 bits.
- À l'étape 1, on charge dans le tampon les 2 premiers caractères. Cette suite n'est pas présente dans le dictionnaire, donc on la rajoute. On émet ensuite sur 8 bits le code '115' (car le code '114', r en ASCII, a pour indice '115' dans le dictionnaire) et l'on supprime du tampon les caractères émis.
- À l'étape 7, la chaîne '116'+'105' étant déjà présente dans le dictionnaire (indice 261), on émet le code '0' car 261 ne peut se coder sur 8 bits, il nécessite un minumum de 9 bits. Les codes émis seront donc désormais émis sur 9 bits.
- À l'étape 8, on charge un nouveau caractère dans le tampon. La chaîne n'est pas présente dans le dictionnaire, donc on la rajoute. On émet ensuite l'indice de la chaîne '116'+'105' (261) et on la supprime du dictionnaire.
- Les étapes suivantes suivent logiquement.
