Compression LZW

Les trois dernières séries du semestre forment un mini-projet dont le but est de réaliser un compresseur/décompresseur de fichier utilisant l'algorithme de Lempel, Ziv et Welch (LZW). Ce mini-projet, non trivial, utilise un grand nombre des concepts vus au cours du semestre et constitue donc une excellente révision.

Cette première série du mini-projet a pour but d'introduire l'algorithme LZW et de le mettre en œuvre pour compresser et décompresser des chaînes de caractères.

Pour faciliter votre travail, nous vous fournissons une archive Zip contenant la définition de :

• l'interface LZWEncoder représentant un encodeur (compresseur) LZW,
• l'interface LZWDecoder représentant un décodeur (décompresseur) LZW,
• la classe LZWTest, un test JUnit pour des mises en œuvre des deux interfaces ci-dessus, qui restent à écrire.

L'algorithme LZW encode des chaînes de caractères tirés d'un alphabet donné en listes d'entiers. Pour ce faire, il utilise un dictionnaire d'encodage, une table de chaînes de longueurs diverses.

Par exemple, admettons que l'on dispose du dictionnaire suivant pour encoder des chaînes composées de caractères tirés de l'alphabet {a, b, n} :

index	chaîne
0	a
1	b
2	n
3	na
4	an
5	baba

Au moyen de ce dictionnaire, on peut encoder la chaîne bananbaba par la liste [1, 4, 4, 5]. Le premier élément de cette liste (1) est l'index de la chaîne b, le second et le troisième (4) celui de la chaîne an, et le dernier (5) celui de la chaîne baba. En mettant bout-à-bout les chaînes du dictionnaire à ces index, on obtient la chaîne à bananbaba. Bien entendu, il est également possible d'encoder cette chaîne différemment, mais la liste [1, 4, 4, 5] est l'encodage le plus court possible avec le dictionnaire donné.

Il est facile de voir que, si le dictionnaire est bien choisi, la version encodée d'une chaîne peut être représentée de manière plus compacte que la chaîne elle-même. Dès lors, à condition que le dictionnaire soit adapté, l'encodage LZW permet de compresser des chaînes de caractères.

Comment être sûr que le dictionnaire utilisé est bien adapté à l'encodage d'une chaîne donnée ? Une idée serait de construire, une fois pour toutes, différents dictionnaires adaptés à différentes situations. Par exemple, on pourrait construire un dictionnaire adapté au français à partir des mots les plus fréquents de cette langue. Cette solution n'est toutefois pas idéale, la constitution d'un bon ensemble de dictionnaires étant une tâche fastidieuse.

Au lieu de cela, l'idée de l'algorithme LZW est de construire ce dictionnaire au fur et à mesure de l'encodage de la chaîne. Initialement, le dictionnaire contient exactement une entrée pour chaque caractère de l'alphabet. Pour notre exemple, l'alphabet étant {a, b, n}, le dictionnaire initial pourrait donc être :

index	chaîne
0	a
1	b
2	n

Ce dictionnaire initial garantit que toute chaîne composée des caractères de l'alphabet peut être encodée, puisque chaque caractère possède une entrée. L'encodage peut donc commencer avec ce dictionnaire, et de nouvelles entrées peuvent lui être ajoutées au fur et à mesure, selon la technique suivante.

Dans un premier temps, le plus long préfixe de la chaîne à encoder qui se trouve dans le dictionnaire est identifié. Cela fait, l'index de ce préfixe est émis, c-à-d qu'il est ajouté à la liste encodée. Ensuite, si le dictionnaire n'est pas plein, une nouvelle entrée y est ajoutée, constituée du préfixe puis du caractère qui le suit. Finalement, le processus est répété avec la chaîne amputée de ce préfixe, jusqu'à ce que celle-ci soit vide.

Un exemple permet de mieux comprendre cet algorithme. Essayons de l'utiliser pour compresser la chaîne bananebabaane composée de caractères tirés de l'alphabet {a, b, e, n}. Le dictionnaire initial est le suivant :

index	chaîne
0	a
1	b
2	e
3	n

Limitons la taille maximale de ce dictionnaire à 8 entrées, pour une raison qui deviendra claire plus tard.

Initialement, le plus long préfixe de la chaîne à encoder qui apparaisse dans le dictionnaire est bien entendu constitué de sa première lettre uniquement, ici b. On encode donc ce préfixe au moyen de l'index 1, qui constituera le premier élément de la liste encodée. Ensuite, étant donné que le dictionnaire n'est pas plein, on y ajoute une entrée consituée du préfixe (b) et du caractères qui le suit dans la chaîne, ici a. On obtient alors le dictionnaire suivant :

index	chaîne
0	a
1	b
2	e
3	n
4	ba

On continue ensuite avec la chaîne amputée du préfixe à peine encodé (b), à savoir ananebabaane. Une fois encore, le plus long préfixe présent dans le dictionnaire est de longueur 1, ici a. On l'encode donc au moyen de l'index 0, puis on ajoute au dictionnaire — toujours pas plein — une nouvelle entrée constituée de ce préfixe et du prochain caractère de la chaîne, à savoir an. On obtient alors :

index	chaîne
0	a
1	b
2	e
3	n
4	ba
5	an

Cela fait, on poursuit l'encodage avec ce dictionnaire et la chaîne amputée de son préfixe (a), à savoir nanebabaane. La totalité des itérations sont décrites par la table ci-dessous, les deux premières lignes reprenant ce qui vient d'être décrit. Sur chaque ligne, le plus long préfixe apparaissant dans le dictionnaire est séparé du reste de la chaîne par un deux-points (:).

préfixe:reste	index	ajout
b:ananebabaane	1	4 = ba
a:nanebabaane	0	5 = an
n:anebabaane	3	6 = na
an:ebabaane	5	7 = ane
e:babaane	2
ba:baane	4
ba:ane	4
ane:	7

La deuxième colonne de cette table donne la liste des index qui constitue l'encodage de la chaîne avec l'algorithme LZW, à savoir [1, 0, 3, 5, 2, 4, 4, 7].

A la fin du processus d'encodage, étant donnés les ajouts faits et répertoriés dans la troisième colonne de la table ci-dessus, le dictionnaire est :

index	chaîne
0	a
1	b
2	e
3	n
4	ba
5	an
6	na
7	ane

Notez que si la taille du dictionnaire n'avait pas été (volontairement) limitée à 8 entrées, d'autres ajouts auraient été faits.

La chaîne originale contenait 13 caractères tirés d'un alphabet de taille 4. Chacun de ces caractères peut s'encoder au moyen de 2 bits, donc la taille totale de la chaîne originale est de 26 bits.

La version encodée est composée d'une liste de 8 entiers compris entre 0 et 7. Chacun d'entre eux peut donc s'encoder au moyen de 3 bits — et c'est pour garantir cela que la taille maximale du dictionnaire a été limitée à 8. La taille totale de la liste encodée est donc de 24 bits.

Le taux de compression obtenu dans cet exemple (2 bits sur 26, soit environ 8%) n'est pas très impressionnant, mais cela est principalement dû au fait que la chaîne à encoder est courte. Comme vous le verrez plus loin, la situation s'améliore avec des chaînes plus longues.

Le décodage d'une séquence encodée par l'algorithme LZW n'est pas beaucoup plus compliqué que l'encodage. La principale question qui se pose est de savoir comment le décodeur peut obtenir le dictionnaire de décodage.

Une solution possible serait d'attacher celui-ci à la liste encodée, mais la taille de cette dernière augmenterait alors considérablement, annulant souvent les gains obtenus par l'encodage.

Heureusement, il n'est pas nécessaire d'attacher ce dictionnaire puisqu'il est parfaitement possible de le reconstruire lors du décodage ! En effet, si l'on effectue le décodage de la liste d'index de son premier élément à son dernier, on peut effectuer les mêmes opérations d'ajout au dictionnaire que celles qui ont été effectuées lors de l'encodage. Bien entendu, il faut utiliser le même dictionnaire initial que lors de l'encodage, c-à-d celui composé d'une entrée pour chaque caractère de l'alphabet.

L'idée est la suivante : à partir du second élément décodé, et tant que le dictionnaire n'est pas plein, on lui ajoute une entrée composée de la chaîne correspondant à l'élément précédent et du premier caractère de la chaîne courante.

Par exemple, la version encodée plus haut de la chaîne bananebabaane est la liste [1, 0, 3, 5, 2, 4, 4, 7]. Le premier élément décodé est la chaîne b et le second est la chaîne a. Dès lors, une fois ce second élément décodé, on ajoute au dictionnaire une nouvelle entrée composée de la chaîne correspondant à l'élément précédent (ici b) et du premier caractère de la chaîne courante (ici a), donc ba.

La table ci-dessous montre comment la chaîne encodée plus haut peut être décodée en utilisant cette technique.

index	chaîne:suffixe	ajout
1	:b
0	b:a	4 = ba
3	ba:n	5 = an
5	ban:an	6 = na
2	banan:e	7 = ane
4	banane:ba
4	bananeba:ba
7	bananebaba:ane

Dans cet exemple, le décodage se passe sans problème mais on constate une différence importante entre les mises à jour faites lors de l'encodage et celles faites lors du décodage : le décodeur a toujours une itération de retard par rapport à l'encodeur. Par exemple, l'encodeur avait ajouté l'entrée ba à la première itération, tandis que le décodeur fait cet ajout à la seconde itération.

Ce retard peut poser un problème au décodeur dans un cas seulement, qui est celui où l'encodeur utilise à une itération donnée le code correspondant à l'entrée ajoutée lors de l'itération précédente. Un tel cas se produit p.ex. si on essaie d'encoder la chaîne aaa sur l'alphabet {a} avec une taille de dictionnaire supérieure ou égale à 2. Dans ce cas, l'encodage procède ainsi :

préfixe:reste	index	ajout
a:aa	0	1 = aa
aa:	1

Comme on le voit, le code émis en dernier (1) correspond à un ajout effectué lors de l'itération précédente. Cela pose un problème au décodeur, en raison de son retard, comme on le constate si on essaie de décoder la liste [0, 1] selon la même technique que précédemment :

index	chaîne:suffixe	ajout
0	:a
1	a:???

Lorsqu'il rencontre l'index 1, le décodeur ne possède pas encore cette entrée dans son dictionnaire, ce qui est représenté ci-dessus par les trois points d'interrogation.

Est-il néanmoins possible de savoir comment décoder cet index ? Pour répondre à cette question, il convient de réfléchir à ce que l'on sait concernant l'élément à l'index inconnu.

La première chose que l'on sait à son sujet est qu'il débute par l'entrée utilisée à l'itération précédente, soit a dans notre exemple. En effet, l'encodeur ajoute toujours au dictionnaire une entrée composée de l'élément précédent suivi de la lettre suivante dans la chaîne originale. A ce stade, on sait donc déjà presque tout sur l'élément inconnu, seule sa dernière lettre nous manque encore…

On peut représenter cette connaissance en remplaçant les trois points d'interrogation dans la table plus haut par une chaîne composée de l'entrée utilisée lors de l'itération précédente (a) suivie d'un unique point d'interrogation représentant la lettre encore inconnue.

index	chaîne:suffixe	ajout
0	:a
1	a:a?

Mais que sait-on sur cette dernière lettre ? On sait qu'il s'agit de la lettre qui, dans la chaîne originale, suit l'élément décodé lors de l'itération précédente. Or cette lettre apparaît dans la table ci-dessus, juste après le deux-points : il s'agit de la première lettre de l'élément décodé lors de l'itération précédente, ici a.

En d'autres termes, lorsque le décodeur rencontre un index qui n'apparaît pas encore dans son dictionnaire, il sait d'une part que celui-ci est l'index qui serait ajouté à la fin de l'itération courante, et d'autre part que l'entrée à cet index est composée de l'entrée de l'itération précédente suivi de la première lettre de cette même entrée !

On peut donc maintenant compléter la table de décodage ci-dessous et constater que le décodeur peut, dans toute situation, reconstruire le dictionnaire d'encodage.

index	chaîne:suffixe	ajout
0	:a
1	a:aa	1 = aa