Cette méthode est elle aussi basée sur la répétition d'une même séquence d'octets. Premièrement, au lieu de coder octet par octet, on va coder par mots de 12 bits :
Cela semble d'abord désavantageux de coder sur 12 bits car on perd 4 bits à chaque fois que l'on tombe sur une séquence inconnue. Mais lorsque c'est le cas, l'encodeur garde cette séquence en mémoire pour la réutiliser après et on gagnera alors au moins 4 bits à chaque séquence apprise.
| Octet lu | Séquence en attente | Séquence formée | Séquence apprise ? | Rang envoyé |
| T | Aucune. | T | Non, déjà connue. | Aucun. |
| O | T | TO | Oui ( TO => 258) | T (84) |
| N | O | ON | Oui ( ON => 259) | O (79) |
| _ | N | N_ | Oui ( N_ => 260) | N (78) |
| T | _ | _T | Oui ( _T => 261) | _ (32) |
| O | T | TO | Non, déja connue. | Aucun. |
| N | TO | TON | Oui ( TON => 262) | TO (258) |
| T | N | NT | Oui ( NT => 263) | N (78) |
| O | T | TO | Non, déja connue. | Aucun. |
| N | TO | TON | Non, déja connue. | Aucun. |
| _ | TON | TON_ | Oui ( TON_ => 264) | TON (262) |
| T | _ | _T | Non, déjà connue. | Aucun. |
| O | _T | _TO | Oui (_TO => 265) | _T (261) |
| N | O | ON | Non, déjà connu. | Aucun. |
| D | ON | OND | Oui (OND => 266) | ON (259) |
A la fin, il reste encore le caractère D en attente. Son rang (68) est alors envoyé, ainsi que le rang 256 qui indique la fin du codage. Les rangs envoyés sont donc : -84-79-78-32-258-78-262-261-259-68-256-. Il y en a donc 11 rangs ce qui fait soit 17 octets. Ici, l'algorithme a augmenter la taille de deux octets...
En voyant cette exemple, on peut penser qu'il n'est pas si puissant même avec de nombreux «TON» qui se répètent. Et pourtant, je l'ai testé avec des
fichiers plus grand et cela marchait mieux : par exemple 345 octets devenaient 290 octets. En fait, plus les fichiers sont grands et plus il a le temps d'apprendre des séquences plus grande (dans l'exemple, la plus longue n'était que de 4 octets !) et donc le gain en octets est beaucoup plus important, comme le montre ce graphique :
Le cas le plus favorable est le cas où tout les caractères sont identiques (Il faudra d'ailleurs faire attention à ce cas particulier au décodage). Par exemple : «AAAAAAAAAA» Les rangs envoyés sont « -64-258-259-260-» cela fait octets au lieu de 10.
Si X désignent le nombre de séquences envoyées (X>0) et N la longueur initiale du fichier, on aura 1 + 2 + 3 + 4 + ... + X = N. Cette égalité est équivalente à cette autre (voir dans la partie math) : . Et si x est la taille en octet du fichier compressé, on a et en reportant x dans l'égalité on obtient : . On résout ensuite cette équation et on trouve :
Quant au cas le plus défavorable, c'est celui où il n'y a pas de compression, et donc la taille du fichier est multipliée par .
Notons que pour la compression LZW, les chances de tomber sur les deux extrêmes sont plus équilibrés que dans la RLE.
Un dernier point à aborder : le code 257. Lorsque l'on a plus de place pour mémorisée les séquences, on envoie ce code qui signifie que l'on remet à zéro les séquences.
Si vous voulez avoir un exemple de programme BASIC avec l'algoritme LZW, téléchargez compression.zip (9 ko), où vous découvrirez LZW.BAS. Ce fichier compresse et décompresse des chaînes de caractère. Essayez par exemple «TON TONTON TOND» où encore «AAAAAAAAAA» pour voir si vous obtenez les mêmes résultats...
Cependant, à moins que vous n'essayez des chaînes où beaucoup de séquences se répètent, le résultat n'est pas très convainquant. J'ai reprogrammé LZW.BAS en Fich_LZW.BAS pour qu'il puisse s'occuper des fichiers. J'ai essayé avec des fichiers plus gros de l'ordre de 4 Ko et là, malgré que l'algorithme ne soit pas optimisé les fichiers sont bien compressés. Ainsi, on voit dans le fichier ZIP que les fichiers sont compressés à 60% environ sauf TEXTE2.RTF et IMAGE2.BMP, les fichiers auquels j'ai appliqué l'algorithme LZW, et que le fichier ZIP a plus de mal à compresser (taux de 2 à 4%).
