Lempel-Ziv-Welch - Définition
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
La liste des auteurs de cet article est disponible ici.
Algorithme
Algorithme de compression :
w = Nul; tant que (lecture d'un caractère c) faire si (wc existe dans le dictionnaire) alors w = wc; sinon ajouter wc au dictionnaire; écrire le code de w; w = c; fin si fin tant que écrire le code de w; Algorithme de décompression :
lecture d'un caractère c; écrire c; // ajout suite à un oubli w = c; tant que (lecture d'un caractère c) faire si (c > 255 && l'index c existe dans le dictionnaire) faire entrée = l'entrée du dictionnaire de c; sinon si (c > 255 && l'index c n'existe pas dans le dictionnaire) faire entrée = w + w[0]; sinon entrée = c; fin si; écrire entrée; ajouter w+entrée[0] au dictionnaire; w = entrée; fin tant que; Principe
L'algorithme général est le suivant :
- Initialisation : un dictionnaire de mots prédéfinis est rempli.
- Lecture :
- Un caractère supplémentaire est ajouté au tampon TANT QUE celui-ci contient des mots présents dans le dictionnaire
- Si le tampon contient une séquence qui ne correspond à aucun mot du dictionnaire, on ajoute cette séquence au dictionnaire : elle sera donc de la forme A + B où A est un mot du dictionnaire et B un caractère, A est renvoyé et sorti du tampon.
- 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 au début 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 minimum 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 tampon.
- Les étapes suivantes suivent logiquement.
