LZW

L'algorithme de compression LZW raconte une histoire singulière, celle d'une découverte théorique qui a mis des années avant de trouver sa forme pratique. Tout commence en 1977, quand Abraham Lempel et Jacob Ziv publient dans l'IEEE Transactions on Information Theory un article aux allures hermétiques intitulé « A Universal Algorithm for Sequential Data Compression ». Leur travail expose une méthode utilisant des dictionnaires de phrases qui glissent sur un texte déjà lu, construisant progressivement de nouveaux motifs en ajoutant des symboles aux séquences existantes.

L'année suivante, les deux chercheurs récidivaient dans la même revue avec une version affinée de leur algorithme. Ces publications restaient néanmoins très abstraites, posant certes les fondations théoriques mais laissant le lecteur sur sa faim quant aux applications concrètes. Il fallut attendre 1984 pour qu'un troisième larron entre en scène et transforme ces travaux académiques en une technologie utilisable.

Terry Welch travaillait au Sperry Research Center quand il publia dans Computer magazine son article « A technique for High-Performance Data Compression ». Son apport révolutionna pourtant l'approche de Lempel et Ziv. Welch eut l'idée de pré-remplir le dictionnaire avec les 256 caractères ASCII standards plutôt que de partir d'un dictionnaire vide. Cette modification permit de traiter immédiatement tous les caractères simples, y compris lors de leur première apparition. Les codes restants, de 256 à 4095 dans un dictionnaire sur 12 bits, pouvaient ainsi servir exclusivement aux nouvelles séquences découvertes.

L'algorithme LZW était né, portant les initiales de ses trois créateurs. Sa force résidait dans sa capacité à dénicher et éliminer les redondances tout en garantissant une restitution parfaite des données originales. Contrairement à d'autres méthodes, LZW n'envoyait jamais les caractères bruts mais uniquement des codes, ce qui généraient des gains substantiels sur les fichiers contenant des motifs répétitifs.

Une caractéristique remarquable de cet algorithme tenait à son autonomie lors de la décompression. Le décodeur n'avait pas besoin de recevoir le dictionnaire utilisé pour la compression ; il pouvait le reconstituer à l'identique en appliquant les mêmes règles que le compresseur. Cette propriété rendait LZW économe en mémoire et rapide à l'exécution.

L'industrie informatique s'empara de cette innovation. En 1987, CompuServe lança le format GIF (Graphics Interchange Format), qui exploitait LZW pour compresser les images. Ce format devint vite incontournable sur les premiers réseaux puis sur Internet, notamment grâce à sa capacité à stocker de nombreuses images dans un fichier unique et à gérer la transparence. UNIX intégra aussi l'algorithme dans sa commande compress, tandis que les formats TIFF et PDF l'adoptaient pour leurs besoins spécifiques.

Les performances de LZW variaient considérablement selon le type de données traitées. Les textes en langue naturelle, riches en redondances, lui convenaient parfaitement, tout comme les images contenant de vastes zones uniformes. Sur ces contenus, l'algorithme atteignait couramment des taux de compression de 50% ou plus. En revanche, les fichiers binaires donnaient des résultats plus imprévisibles : certains se compressaient mieux que du texte ordinaire, d'autres résistaient obstinément à tout traitement.

L'implémentation pratique de LZW nécessitait de résoudre quelques casse-têtes techniques. Le plus délicat survenait lors de la décompression, quand le décodeur rencontrait un code avant d'avoir pu le définir. Cette situation baroque se produisait avec des séquences du type (chaîne, caractère, chaîne, caractère, chaîne), où l'algorithme émettait un code que le décompresseur n'avait pas encore eu l'occasion de créer. Il fallait donc prévoir un mécanisme d'exception spécifique pour gérer ces cas particuliers.

La belle histoire de LZW connut un tournant inattendu dans les années 1990. Unisys, détenteur d'un brevet sur l'algorithme, commença à réclamer des redevances pour toute utilisation commerciale. Cette revendication soudaine provoqua un tollé dans la communauté informatique et poussa au développement du format PNG (Portable Network Graphics) comme alternative libre au GIF. Le brevet finit par expirer en 2003 aux États-Unis et en 2004 ailleurs, libérant enfin l'algorithme de ces contraintes juridiques.

La taille du dictionnaire influençait directement l'efficacité de la compression. Un dictionnaire de 12 bits, capable de stocker 4096 entrées, représentait souvent un équilibre satisfaisant entre taux de compression et consommation mémoire. L'algorithme gagnait en performance avec des fichiers volumineux, car le dictionnaire avait davantage d'occasions de repérer et réutiliser des motifs récurrents.

Sur les petits fichiers, LZW montrait ses faiblesses. Le coût de stockage du dictionnaire pouvait dépasser le bénéfice de la compression, rendant le fichier compressé plus volumineux que l'original. Des variantes comme LZWS (Lempel-Ziv-Welch-Setia) tentèrent d'adapter dynamiquement la stratégie selon la taille des données, avec un succès mitigé.

L'algorithme LZW établit des principes durables dans le domaine de la compression : l'usage de dictionnaires adaptatifs, la compression sans perte, l'importance de l'autonomie lors de la décompression. Il occupe une place particulière dans l'écosystème informatique. Des méthodes plus récentes offrent certes de meilleurs taux de compression, mais sa simplicité relative en fait un excellent outil pédagogique pour comprendre les mécanismes fondamentaux de la compression de données. Il reste utilisé dans certaines applications spécifiques où sa robustesse et sa rapidité d'exécution compensent ses limitations. Dans l'histoire des technologies de l'information, LZW demeure l'un des premiers algorithmes de compression à avoir connu un succès commercial durable et une adoption véritablement universelle.