Compression avec LZW

par Cryptonyx

Les questions, les commentaires et les suggestions sur cet article et sur LZW peuvent être envoyés à Cryptonyx.

Il existe de nombreux algorithmes de compression numérique dont les performances varient selon le type de données à compresser. Les taux de compression obtenus dépendent de manière significative du type que l'on traite : texte, image, son ou vidéo. Les algorithmes les plus connus sont Run Length Extension (RLE) pour les formats de fichiers BMP, JPEG pour les images fixes, MPEG pour les images vidéo, Huffman et LZW pour les fichiers de texte. Ils sont utilisés dans des logiciels comme WinZIP, GZIP, PowerArchiver, ARC ou la ZLIB. Nous avons déjà étudié (lien HTML sur HCD) un grand classique de la compression de donnée : l'algorithme de Huffman qui par une approche statistique permet de déterminer une suite de code optimale pour un fichier donné. Cet article présente un autre classique de la compression de donnée : LZW pour Lempel, Ziv et Welch. Cette compression est basée sur une approche très différente de celle choisie par Huffman et est en général très efficace pour les fichiers contenant des séquences très répétitives.

Le texte qui suit est une traduction/adaptation très libre d'un article publié en 1989 par Mark R. Nelson [référence 4]. Les exemples originaux ont été maintenus mais plusieurs modifications ont été apportées au texte original pour le rendre plus accessible et pour tenir compte du portage du source sous BCB 5.03.

Principe du LZW

L'approche de Lempel et Ziv de la compression de données fut à l'origine publiée en 1977. Les améliorations apportées par Terry Welch furent publiées en 1984. L'algorithme est remarquablement simple. Pour résumer, une compression LZW remplace des chaînes de caractères lues au fil de l'eau par un seul code sans pour autant faire une analyse préalable de l'ensemble du texte, comme c'est le cas pour une compression de type Huffman. En lieu et place, la compression ajoute simplement chaque nouvelle chaîne de caractères trouvée dans le fichier d'entrée dans une table de chaînes. La compression s'effectue par l'écriture d'un code unique en remplacement de chaque chaîne identifiée.

La séquence de code issue de la compression LZW peut avoir n'importe quelle longueur, mais chaque code contient par construction plus de bits qu'un simple caractère ASCII. Les 256 (de 0 à 255) premiers codes (si on utilise un codage sur 8 bits, de type ASCII) sont affectés par défaut au jeu de caractères standard. Les codes restants sont affectés aux chaînes déterminées par l'algorithme. L'utilitaire fourni à titre d'exemple utilise des codes de 12 bits. On aura donc les valeurs comprises entre 0 et 255 pour les caractères ACSII classiques alors que les codes compris entre 256 et 4095 se rapporteront aux chaînes générées par l'algorithme. Les codes ainsi crées auront une signification différente d'un fichier à un autre.

Compression

L'algorithme de compression LZW est décrit de manière très synthétique en Figure 1. Un examen rapide de celui-ci montre que la compression LZW conduit à écrire (dans un tampon ou directement dans un fichier) des codes pour les chaînes déjà connues. Chaque fois qu'un nouveau code est écrit, une nouvelle chaîne est ajoutée dans la table. Si cette chaîne apparaît à nouveau dans le fichier traité, son code est recherché par LZW puis écrit dans le fichier de sortie (ou dans l'exemple fourni, dans un tampon qui est écrit sur disque à la fin de la compression).

Fonction LZW_COMPRESS

Figure 1 : algorithme de compression LZW

La figure 2 montre comment LZW fonctionne à partir d'une simple chaîne de caractères. La chaîne est une suite de mots séparés par un '/'. LZW lit le premier caractère puis le second. La première opération consiste à vérifier si la chaîne "/W" formée par les deux caractères est déjà dans la table. Comme elle n'y est pas, le code du '/' formé des 8 bits du code ASCCII complété de 4 bits à zéro est enregistré dans un tampon d'attente et la chaîne "/W" est ajoutée dans la table des chaînes de caractères. Comme il y a déjà 256 caractères définis pour les codes ASCII de 0 à 255, la première chaîne ajoutée à la table peut prendre la valeur 256. Une fois que la troisième lettre, 'E', a été lue, le second code de chaîne, "WE" est ajouté à la table et le code de la lettre 'W' est enregistré, toujours dans un tampon. On continue ainsi jusqu'au second mot, où la séquence «/W» est a nouveau rencontrée et affectée du code 256. Dans ce cas, le 256 est enregistré dans le tampon de sortie et une chaîne de trois caractères est ajoutée à la table. Le processus continue jusqu'à la fin du texte et jusqu'à ce que chaque code soit enregistré dans le tampon. Le tampon est alors enregistré dans le fichier de sortie.

Séquence d'entrée = /WED/WE/WEE/WEB/WET
Caractère lu	Code issu	Nouvelle valeur	Nouvelle chaîne
/W	/	256	/W
E	W	257	WE
D	E	258	ED
/	D	259	D/
WE	256	260	/WE
/	E	261	E/
WEE	260	262	/WEE
/W	261	263	E/W
EB	257	264	WEB
/	B	265	B/
WET	260	266	/WET
EOF	T

Figure 2 : illustration de l'algorithme de compression

On voit tout de suite que la table des chaînes de caractères augmente rapidement parce qu'une nouvelle chaîne est rajoutée à chaque fois qu'un code est issu dans le tampon de sortie. Dans cet exemple avec une chaîne très redondante, 5 substitutions ont été effectuées donnant 5 nouveaux codes en plus des 7 autres codes de caractère. Si on utilisait des codes de 9 bits en sortie, les 19 caractères de la chaîne d'entrée se transformeraient en une chaîne de sortie de 13,5 octets. Avec des codes utilisant 12 bits comme dans l'exemple fourni avec cet article, on obtient 18 octets en sortie pour 19 en entrée. Cet exemple était bien sûr choisi pour mettre en évidence la substitution de code et on constate déjà que pour les fichiers de petite taille, l'efficacité de la compression ne sera pas très élevée.

Décompression

La décompression s'effectue naturellement de manière réciproque et on peut aisément noter que l'une des raisons de l'efficacité de LZW est qu'il n'est pas nécessaire de lui fournir la table des codes pour la décompression, contrairement à Huffman. La table se construit de manière dynamique parce que la compression enregistre toujours une chaîne ou un caractère en sortie avant de s'en servir pour transcodage via la table des chaînes de caractères.

Fonction LZW_DECOMPRESS

Lire CODE
        écrire CODE
        TANTQUE il y a des caractères FAIRE
                Lire CODE_SUIVANT
                CHAINE = traduire le CODE_SUIVANT
                écrire CHAINE
                CARACTERE = premier caractère de la CHAINE
                ajouter CODE + CARACTERE à la table des chaînes
                CODE = CODE_SUIVANT
       FINTANTQUE

Figure 3 : algorithme de décompression

L'algorithme de décompression est décrit en Figure 3. Comme pour la compression on ajoute une nouvelle chaîne à la table des chaînes à chaque fois qu'un nouveau code est lu. Il reste à traduire chaque code d'entrée en chaîne avant de l'écrire.

La Figure 4 montre le résultat obtenu par la décompression avec l'exemple utilisé précédemment. Il est important de noter que la table est exactement la même que celle construite pendant la compression. La séquence de sortie est identique à celle d'avant compression. On note aussi que les 256 premiers codes sont déjà définis pour transformation en chaîne à un seul caractère.

Figure 4 : illustration de l'algorithme de décompression

Le piège

Malheureusement, l'algorithme de décompression de la Figure 4 est un peu trop simple. Il existe une exception avec LZW qui provoque un cas d'erreur en phase de décompression. Si une chaîne est de la forme (CHAINE, CARACTERE) déjà définie dans la table, la séquence de sortie est de la forme CHAINE, CARACTERE, CHAINE, CARACTERE, CHAINE et dans ce cas l'algorithme de compression écrira un code avant que le décompresseur ne puisse le définir.

Un exemple simple peut illustrer ce point. Supposons que la chaîne JOEYN soit définie dans la table avec le code 300. Au cours de la lecture du fichier, supposons que la séquence JOEYNJOEYNJOEY soit placée dans la table. Le résultat de la compression va donc ressembler aux valeurs de la Figure 5.

Figure 5 : illustration du problème

Quand on trouve une telle séquence lors de la décompression, on décode d'abord le code 300 et on écrit la chaîne JOEYN. Après avoir fait ça, on ajoute la définition du code 399 dans la table. On lit alors le 400 et on s'aperçoit qu'il n'est pas dans la table, d'où le problème.

Heureusement, c'est le seul cas où la décompression aura affaire à un type de code inconnu et comme c'est bien le seul, on peut traiter facilement ce cas particulier. La version modifiée de l'algorithme de compression traite ce cas en effectuant un test sur le code. Dans l'exemple de la Figure 5, la décompression trouve un code 400 indéfini. Comme il n'est pas défini, on lui donne la valeur de CODE, qui est 300. On ajoute alors la valeur de CARACTERE, qui est 'J', à la chaîne. Ceci conduit à la traduction correcte du code 400 en "JOEYNJ".

Fonction LZW_DECOMPRESS (2)

Lire OLD_CODE
écrire OLD_CODE
CARACTERE = OLD_CODE
TANTQUE il y des caractères FAIRE
    Lire NEW_CODE
    SI NEW_CODE n'est pas dans la table des chaînes ALORS
        CHAINE = get translation of OLD_CODE
        CHAINE = CHAINE + CARACTERE
    SINON
        CHAINE = retrouver la traduction de NEW_CODE
    FINSI
    écrire CHAINE
    CARACTERE = premier caractère de CHAINE
    ajouter OLD_CODE + CARACTERE dans la table
    OLD_CODEE = NEW_CODEE
FINTANTQUE

Figure 6 : version modifiée de l'algorithme de décompression

Les choix de codage de LZW

Les concepts utilisés pour les opérations de compression et de décompression sont relativement simple et l'algorithme seul se décrit en quelques lignes. La mise en oeuvre est cependant plus compliquée à cause de la gestion de la table des chaînes.

Dans l'exemple réalisé pour la FAQ Source, il est possible de choisir des codes de 12, 13 ou 14 bits. La version fournie utilise des codes de 12 bits et on peut donc stocker jusqu'à 2 ** 12 = 4096 codes dans la table. Chaque fois qu'un nouveau caractère est lu en entrée, il faut parcourir la table pour trouver une équivalence. Si aucune équivalence n'est trouvée, alors on ajoute une nouvelle chaîne dans la table. Ceci entraîne deux problèmes.

En premier lieu, la table peut croître très rapidement. Si la longueur des chaînes est en moyenne de 3 ou 4 caractères, la quantité d'octets nécessaire pour stocker les chaînes pourrait aller jusqu'à 7 ou 8 par code. En outre, la quantité de stockage requise est alors indéterminée, parce qu'elle dépend de la longueur totale des chaînes.

Le second problème est lié à la recherche des chaînes. A chaque fois qu'un nouveau caractère est lu, il faut parcourir la table pour trouver la formée de CHAINE + CARACTERE ce qui implique le maintien d'une liste ordonnée des chaînes. La recherche de chacune des chaînes prendra en moyenne log2(taille_code) comparaisons de chaînes. L'utilisation de mots de 12 bits signifie qu'il faut potentiellement effectuer 12 comparaisons de chaines (log2(2 ** 12)) pour chaque code. Le temps CPU pour ce type de recherche est prohibitif si on recherche un peu d'efficacité.

Le premier problème peut se résoudre en stockant des chaînes sous forme de combinaisons code/caractère. Comme chaque chaîne est la combinaison d'un code existant et d'un caractère ajouté, on peut stocker chacune des chaînes sous la forme d'un code et d'un caractère. Par exemple, dans l'exemple de compression donné, la chaîne "/WEE" est en fait transformée en code 260 suivi du caractère 'E'. Cette transformation ne prend que 3 octets de stockage au lieu de 5 (si on compte le code de fin de chaîne). En déroulant la pelote, on trouve que le code 260 est stocké sous la forme du code 256 suivi du caractère E. Finallement, le code 256 est stocké sous la forme d'un '/' et d'un 'W'.

La comparaison des chaînes est un peu plus difficile. La méthode de stockage employée réduit le temps nécessaire pour effectuer une comparaison mais n'en réduit pas le nombre. Ce problème se résout en stockant les chaînes à l'aide d'une fonction de hâchage. En pratique cela veut dire que l'on accède pas au code 256 à la 256ème ligne de la table. On le stocke dans la table à une adresse qui est fonction de la chaîne. Pour retrouver une chaîne, on peut alors utiliser une chaîne intermédiaire pour générer une adresse et avec un peu de chance trouver celle qui nous intéresse en une seule tentative.

Comme le code d'une n'est plus directement connu à cause de cette façon de procéder, il faut stocker le code de chaque chaîne avec le contenu de la chaîne. Dans la version fournie, on trouve trois tableaux pour gérer les chaînes. Ce sont CodeValueTable[i], PrefixCodeTable[i] et AppendedCharacterTable[i]. Pour ajouter un nouveau code à la table, il faut utiliser la fonction de hâchage appelée FindMatch pour générer l'indice i correct. FindMatch génère une adresse puis vérifie si l'emplacement correspondant est déjà utilisé par une chaîne différente. Si c'est le cas, on effectue une autre tentative de recherche et ainsi de suite jusqu'à ce qu'une place vide soit trouvée.

La fonction de hâchage utilisée dans l'exemple est un simple ou exclusif (xor). Le préfixe et le caractère ajouté sont combinés pour former une adresse à l'intérieur de la table. Si le contenu du préfixe + caractère correspondent à la valeur déjà dans la table, la recherche s'arrête et l'adresse est renvoyée. Si l'élément de la table est déjà utilisé, un nouvelle recherche est effectuée en modifiant l'adresse par une valeur d'offset. Le processus continue jusqu'à ce qu'une place vide ou une chaîne correspondante soit trouvée. En utilisant une table de 25% environ plus importante que nécessaire, le nombre moyen de recherches reste en principe en dessous de 3. Les performances peuvent être améliorée en augmentatnt la taille de la table. Il est important de noter que pour que la seconde recherche marche dans tous les cas, la taille de la table doit être un nombre premier. Cela tient au fait que le nombre utilisé doit être un entier compris entre 0 et la taille de la table. Si ce nombre et la taille de la table n'étaient pas premiers entre eux, une recherche pourrait échouer même s'il y avait encore de la place dans la table.

La partie décompression amène aussi son lot de problèmes même si la problématique de la recherche de chaîne disparaît. Lors de la décompression, on recherche en effet des codes, ce qui signifie que l'on peut stocker les préfixes et les caractères ajoutés dans une table indexée par leur propre code de chaîne. Ceci évite le recours à une fonction de hâchage ainsi que le tableau utilisé pour stocker les codes.

Malheureusement, la méthode utilisée pour stocker les chaînes fait que celles-ci sont décodées dans l'ordre inverse. Pour contrer cet effet, les caractères d'une chaîne donnée seront stockés dans une pile et remis dans le bon ordre lors du dépilage. Cette fonction est assurée par DecodeString. Le plus dur est alors fait.

Codage de LZW

Le code fourni pour illustrer cet article n'est pas particulièrement efficace. Par exemple, les fonctions InputCode et OutputCode ne sont pas optimisées pour une application LZW utilisant des codes de longueur fixe, dans ce cas 12 bits. Elle fonctionnent aussi pour des codes de taille supérieure et sont donc assez génériques.

L'un des désavantages de l'application est qu'elle ne distingue pas la compression des petits et des gros fichiers. L'utilisation de codes de 14 ou 15 bits donnerait de meilleurs résultats sur les gros fichiers parce qu'ils ont en général plus de chaînes de caractères différentes, mais au détriment des petits fichiers (attention à la taille du tampon pour le fichier de sortie dans ce cas). Les programmes les plus évolués utilisent donc des codes de longueur variable. Par exemple, tant que la valeur de la variable NextCode reste entre 256 et 511, un logiciel comme ARC utilise des codes de 9 bits. Quand la valeur de NextCode croît au point de justifier l'emploi de codes de 10 bits, aussi bien la compression que la décompression ajustent leur taille de code. Cette souplesse fait que les versions 12 bits et 15 bits de l'application donneront aussi de bon résultats avec les petits fichiers.

Un autre problème qui se pose pour les gros fichiers est que le taux de compression commence à se dégrader au fur et à mesure que l'on avance dans la lecture du fichier d'entrée. La raison de cette dégradation est simple et s'explique par le fait que la table des chaînes ayant une taille forcément finie, elle est pleine après un certain temps et plus aucune chaîne ne peut y être ajoutée. Hors, il est assez évident que les chaînes contenues dans cette table rendent compte de la teneur du début du fichier. Rien n'indique que la suite du fichier verra les mêmes chaînes appaître et une nouvelle table est alors nécessaire.

Une façon assez classique de résoudre ce problème est de surveiller le taux de compression. Une fois que la table des chaînes est pleine, le compresseur regarde si le taux de compression se dégrade. Après un certain niveau de dégradation, on vide entièrement la table et on la reconstruit tout en marquant cet événement par un code particulier dans le fichier de sortie.

Une alternative à cette méthode serait de regarder la fréquence d'utilisation des chaînes et de supprimer périodiquement de la table les valeurs qui ne sont utilisées que rarement. Cette technique peut cependant s'avérer difficile à mettre en oeuvre pour un simple utilitaire de démonstration. Une autre option à considérer est l'utilisation d'un arbre équilibré (btree) qui évite d'avoir recours à une table et qui peut évoluer au fur et à mesure que le fichier d'entrée est lu. La vitesse de compression pourra sans doute s'en ressentir.

Une dernière optimisation pourrait consister à compresser les codes LZW grâce à un algorithme de Huffman adaptatif. On pourrait alors gagner un pourcentage de compression mais au détriment de la simplicité du code et du temps de traitement.

Résultats

Il est intéressant de faire une comparaison entre HCD, LZW et un ZIP pour se faire une idée du potentiel de LZW.

API_tutorial.pdf est le fichier du Forger sur l'API Windows. ELUN.txt contient 10 fois la lettre 'a'. HCD.html est une version de la description de HCD. test_chaine.txt contient « aaaaaaaaaabbbbbcccddefffffgggggggggg ». test_repetitions.txt contient la même chaîne repétée plus de mille fois avec des retours à la ligne.

On peut penser que le codage sur 12 bits de LZW est un handicap vis à vis d'un ZIP du commerce qui est à l'évidence très optimisé et adaptatif. A titre anecdotique, on notera aussi qu'une double compression LZW puis HCD peut dans certains cas faire gagner quelques octets sur le fichier final.

Bibliographie

1. Terry Welch, "A Technique for High-Performance Data Compression", Computer, June 1984

2. J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, May 1977

3. Rudy Rucker, "Mind Tools", Houghton Mifflin Company, 1987

4. Mark R. Nelson, LZW data compression/expansion demonstration program, Dr Dobbs' Journal, April 13, 1989