La compression de données
Le codage de Lempel Ziv Welch
Cette partie va présenter une compression sans perte appelé codage de Lempel Ziv Welch (LZW). Elle va d'abord décrire le codage avant de présenter la compression et la décompression effectuées par ce codage
Description
Le codage de Lempel Ziv Welch est une adaptation du codage LZ78 d’Abraham Lempel et Jacob Ziv amélioré par Terry Welch. Les codages Lempel Ziv ont inventé et posé les bases du codage par dictonnaire et le codage LZW en est donc un lui aussi.
Un codage par dictionnaire (ou codage par facteur) est un codage basé sur un dictionnaire ou une liste de mot. Ici, l’objectif va être de remplacer un mot par sa position dans le dictionnaire.
Le codage LZW est utilisé dans les format GIF, TIFF et MOD.
Avant de commencer à présenter la compression et la décompression du codage LZW, il faut connaitre deux règles concernant le dictionnaire utilisé. Tout d'abord, celui-ci est créé et maintenu de façon à ce que pour un mot donné du dictionnaire, tous ses préfixes soient aussi présents. Ensuite, à l'initialisation, le dictionnaire contient tous les caractères ASCII
Compression
Pour présenter la compression, nous allons utiliser un exemple et nous décrirons chaque étape de compression. Codons le mot "barbapapa" à l’aide du codage LZW.
Le principe de la compression est le suivant :
- On lit une lettre du mot à coder qu’on ajoute au mot surveillé actuel (à l’origine : le mot vide):
- Si le mot est présent dans le dictionnaire, on recommence l’opération en lisant la lettre suivante
- Si le mot n’est pas présent dans le dictionnaire, on l’ajoute au dictionnaire et on code le mot privé de la dernière lettre lue avec sa position dans le dictionnaire. On recommence la lecture avec cette dernière lettre lue (et donc la première lettre non codée)
Le tableau suivant montre les étapes du calcul:
| Mot lu | Code écrit | Mot ajouté au dictionnaire (+ emplacement) |
|---|---|---|
| b | ||
| ba | 98 | ba, 257 |
| a | ||
| ar | 97 | ar, 258 |
| r | ||
| rb | 114 | rb, 259 |
| b | ||
| ba | ||
| bap | 257 | bap, 260 |
| p | ||
| pa | 112 | pa, 261 |
| a | ||
| ap | 97 | ap, 262 |
| p | ||
| pa | 261 |
Dès lors, le mot "barbapapa" est codé par "98 97 114 257 112 97 261"
Décompression
De la même manière, nous allons présenter la décompression par l’exemple en décompressant notre format compressé.
Prenons le code "98 97 114 257 112 97 261" qui représente le mot "barbapapa". Le principe de la décompression suit l'enchainement inverse. La difficulté est de rajouter les mots non rencontrés au dictionnaire.
Le principe du décodage est le suivant:
- On lit le prochain code du fichier compressé: celui-ci correspond obligatoirement à un mot du dictionnaire qu'on insère donc dans le mot décodé.
- Sauf s'il s'agit du premier code, il faut ajouter au dictionnaire le mot correspondant au mot précédent auquel à été ajouté la première lettre du mot actuel.
Le tableau suivant montre les différentes étapes de la décompression :
| Code lu | Mot lu | Mot décodé | Mot ajouté au dictionnaire (+ emplacement) |
|---|---|---|---|
| 98 | b | b | |
| 97 | a | ba | ba, 257 |
| 114 | r | bar | ar, 258 |
| 257 | ba | barba | rb, 259 |
| 112 | p | barbap | bap, 260 |
| 97 | a | barbapa | pa, 261 |
| 261 | pa | barbapapa | ap, 262 |
Ainsi, nous avons récupéré notre premier mot: barbapapa