C’est
en 1977 que Jacob Ziv et Abraham Lempel ont publié un article qui est à la
base de tous les algorithmes à dictionnaire que nous utilisons actuellement.
En 1984, l’américain Terry Welch améliore l’algorithme précédent et dépose
un brevet. C’est la naissance de l’algorithme LZW. Il est plus performant que
les méthodes statistiques. IL sert de base à la norme V42bis du CCITT (Comité
Consultatif Internationale de Télégraphie et Téléphonie) que nous utilisons
dans nos modems.
Le principe de l’algorithme LZW, c’est d’utiliser un dictionnaire dynamique
qui contient des motifs du fichier traité.
L’inconvénient des algorithmes à dictionnaire, c’est qu’il est à priori
nécessaire de transmettre le dictionnaire avec les données, ce n’est pas le
cas avec LZW. Le dictionnaire est construit à la compression et reconstruit à
la décompression.
Ce qui est également intéressant, c’est qu’il est inutile de lire et
d’étudier le fichier avant de le compresser. La compression s’effectue au fur
et à mesure de la lecture, le compresseur détectant au fur et à mesure les
séquences qui se répètent.
Enfin,
on peut combiner LZW et un algorithme de codage statistique. C’est ce que
font des programmes comme ARJ ou PKZIP qui utilisent LZW puis Shannon Fano.
