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

Abraham Lempel    Jacob Ziv

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 :

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: