Lempel-Ziv-Welch
Définition
LZW (pour Lempel-Ziv-Welch) est un algorithme de compression de données. 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 a été breveté par la société Unisys. Il a été utilisé dans les modems (norme V42 bis) et est encore utilisé dans le format d'image numérique GIF.
Principe
Cet algorithme est appelé « à dictionnaire », car il se base sur la répétition de chaines de caractères dans un même flux. Les fenêtres coulissantes de LZ77 et LZ78 ont elles disparues, remplacées par un tampon, mais le dictionnaire est lui toujours présent. Ce dernier se chargera d'enregistrer les chaines de caractères rencontrées et de leur associer un indice. Tout d'abord on initialise le dictionnaire en donnant au code '0' l'indice 1, le code '1' l'indice 2.....etc jusqu'à '255' (ce qui correspond aux 256 valeurs différentes que peut prendre un octet). L'indice 0 sera reservé pour un usage ultérieur.
On charge un premier caractère dans le tampon. La compression se passe alors comme suit :
1) On charge un nouveau caractère dans le tampon sans effacer les précédents
2) On recherche si la chaîne de caractères présente dans le tampon est présente dans le dictionnaire. Si elle l'est, on retourne à l'étape 1). Si elle ne l'est pas, on la rajoute dans le dictionnaire avec un nouvel indice et l'on émet la séquence allant du début du tampon jusqu'à l'avant-dernier caractère inclus, on supprime les caractères émis, et l'on retourne à l'étape 1).
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 inititialisé et associe l'indice 1 au code '0', l'indice 2 au code '1'.....etc jusqu'à l'indice 256 qui correspond au code '255'.
ETAPE TAMPON EMIS RAJOUT AU DICTIONNAIRE 1 '114'+'101' '115' 257 : '114'+'101' 2 '101'+'112' '102' 258 : '101'+'112' 3 '112'+'101' '113' 259 : '112'+'101' 4 '101'+'116' '102' 260 : '101'+'116' 5 '116'+'105' '117' 261 : '116'+'105' 6 '105'+'116' '106' 262 : '105'+'116' 7 '116'+'105' '0' 8 '116'+'105'+'111' '261' 263 : '116'+'105'+'111' 9 '111'+'110' '112' 264 : '111'+'110' 10 '110' '111'
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' à pour indice '115' dans le dictionnaire) et l'on supprime du tampon les caractères émis. À l'étape 2), un charge un nouveau caractère dans le tampon et comme cette chaine n'est pas présente, on la rajoute au dictionnaire. Puis on émet le code '102' que l'on supprime ensuite du tampon. Les étapes suivantes fonctionnent sur le même principe. Arrivé à l'étape 7), la chaine '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 chaine n'est pas présente dans le dictionnaire, donc on la rajoute. On émet ensuite l'indice de la chaine '116'+'105' (261) et on la supprime du dictionnaire. Les étapes suivantes suivent logiquement.