Flots LZW à taille variable

Le but de cette série, la dernière du mini-projet LZW, est d'améliorer le (dé)compresseur LZW de la série précédente pour faire varier la taille des valeurs encodées et améliorer ainsi le taux de compression. Pour démarrer, nous vous conseillons donc de prendre soit votre solution de la série précédente, soit notre corrigé.

Pour mémoire, le (dé)compresseur LZW de la série précédente représente chaque valeur encodée sous la forme d'un entier de 12 bits. Ces entiers de 12 bits sont écrits dans (ou lus depuis) un flot sous-jacent au moyen d'une paire de classes nommées Bits12OutputStream et Bits12InputStream qui vous avaient été fournies.

Représenter les valeurs encodées par des entiers de 12 bits est bien entendu correct, comme nous l'avons vu, mais n'est pas vraiment optimal. En effet, on sait qu'initialement le dictionnaire contient 256 valeurs, donc un index dans ce dictionnaire-là peut se représenter au moyen de 8 bits seulement. Dès le premier ajout au dictionnaire effectué, 8 bits ne suffisent plus, mais 9 suffisent. Cela reste vrai jusqu'à ce que 257 ajouts aient été faits, moment auquel le dictionnaire contient 513 valeurs, nécessitant 10 bits. Et ainsi de suite jusqu'à ce que le dictionnaire atteigne sa taille maximale, fixée à 2¹⁶, et que toutes les index nécessitent 16 bits.

Il est possible de tirer parti de cette observation pour réaliser une version du (dé)compresseur LZW utilisant un nombre de bits variant de 8 à 16 pour représenter les valeurs encodées, et tel est le but de cette série.

Pour commencer, écrivez une classe nommée BitsOutputStream, très similaire à Bits12OutputStream mais offrant une méthode nommée writeU à la place de la méthode writeU12.

La méthode writeU est une généralisation de la méthode writeU12 qui permet d'écrire entre 0 et 16 bits dans le flot sous-jacent, plutôt que 12. Tout comme writeU12, elle prend donc en argument un entier de type int contenant, dans ses bits de poids faible, les bits à écrire ; mais elle prend de plus un second argument, compris entre 0 et 16, donnant le nombre de bits à écrire.

L'idée de la classe BitsOutputStream est de stocker les bits qu'on lui demande d'écrire jusqu'à ce qu'elle en ait au moins 8. A ce moment, il lui est possible d'écrire les 8 premiers d'entre-eux dans le flot sous-jacent, et de les supprimer du stock.

Nous appellerons ces bits stockés temporairement les bits en attente. Ils peuvent naturellement être placés dans les bits de poids faible d'un entier de type int. Un second entier mémorise le nombre de ces bits.

Pour faciliter la compréhension du fonctionnement de cette classe, imaginons qu'on l'utilise comme illustré ci-dessous pour écrire successivement 7, 4 puis 7 bits dans un flot sous-jacent :

1: BitsOutputStream s = new BitsOutputStream(…);
2: s.writeU(0b1010101, 7);
3: s.writeU(0b1111, 4);
4: s.writeU(0b0101010, 7);
5: s.close();

A la création de l'instance de BitsOutputStream (après la ligne 1), le nombre de bits en attente vaut 0 et l'entier les contenant a donc tous ses bits à 0.

Après le premier appel à writeU (ligne 2), le nombre de bits en attente vaut 7 et l'entier les contenant vaut …1010101.

Le second appel à writeU (ligne 3) est plus intéressant et mérite d'être détaillé. Dans un premier temps, les 4 nouveaux bits sont ajoutés à ceux en attente. Dès lors, l'entier les contenant vaut …10101011111 et le nombre de bits en attente est de 11. Ce nombre étant supérieur à 8, il est possible d'écrire un octet dans le flot sous-jacent. Cet octet est composé des 8 bits de poids le plus fort parmi les 11 attente, à savoir 10101011. Une fois cet octet écrit dans le flot sous-jacent, le nombre de bits en attente est de 3 et l'entier les contenant vaut …111.

Lors du troisième appel à writeU (ligne 4), une situation similaire se présente. Les 7 nouveaux bits sont dans un premier temps ajoutés à ceux en attente, l'entier les contenant valant alors …1110101010. Etant donné que 10 bits sont maintenant en attente, il est possible d'écrire les 8 premiers d'entre-eux (11101010) dans le flot sous-jacent. Cela fait, il ne reste plus que deux bits en attente (10).

Finalement, lors de l'appel à close (ligne 5), les bits en attente doivent encore être écrits. Pour cela, 6 bits de remplissage (à 0) sont ajoutés par la méthode close afin d'avoir un total de 8 bits en attente (10000000), qui sont écrits dans le flot sous-jacent, après quoi celui-ci est fermé.

Une fois la classe BitsOutputStream écrite, modifiez la classe du flot compresseur, LZWOutputStream, pour qu'elle l'utilise à la place de Bits12OutputStream. Mais dans un premier temps, appelez writeU en fixant son second argument à 12, afin qu'elle se comporte comme la méthode writeU12 de Bits12OutputStream. Vérifiez ensuite que vous obtenez exactement les mêmes fichiers compressés qu'avec Bits12OutputStream.

Cela fait, passez à l'exercice suivant, car la variation de la taille des valeurs encodées ne sera faite que lors de l'exercice 3.

Ecrivez maintenant une classe nommée BitsInputStream généralisant Bits12InputStream de la même manière que BitsOutputStream généralise Bits12OutputStream.

En d'autres termes, elle doit offrir une méthode readU permettant de lire un nombre de bits compris entre 0 et 16 du flot sous-jacent.

Une fois la classe BitsInputStream écrite, modifiez la classe LZWInputStream pour qu'elle l'utilise à la place de Bits12InputStream. Là encore, passez toujours 12 comme nombre de bits à lire, et vérifiez que vous arrivez bien à décompresser les fichiers compressés. Cela fait, passez au dernier exercice.

Les classes BitsOutputStream et BitsInputStream écrites, il est possible d'en tirer parti pour faire varier la taille des valeurs encodées, comme expliqué dans l'introduction.

Pour ce faire, modifiez les classes LZWOutputStream et LZWInputStream afin qu'elles écrivent et lisent des valeurs encodées dont la taille en bits dépend de la taille du dictionnaire.

Notez que cela est très simple à faire pour le compresseur, mais dans le décompresseur il ne faut pas oublier que ce dernier met toujours son dictionnaire à jour avec un retard d'une itération par rapport au compresseur. Dès lors, la taille du dictionnaire à utiliser pour déterminer le nombre de bits de la valeur encodée à lire du flot sous-jacent est celle que le dictionnaire aura à la fin de l'itération courante, et pas sa taille actuelle.

Le nombre de bits \(b\) à utiliser pour encoder un index d'un dictionnaire contenant \(n\) entrées est donné par la formule suivante : \[ b = \left\lceil\log_2(n)\right\rceil \] où \(\lceil x\rceil\) représente la partie entière par excès (ceil en anglais) de \(x\), c-à-d le plus petit entier supérieur ou égal à \(x\).

En Java, il est bien entendu possible d'utiliser les méthodes de la classe Math pour traduire littéralement cette formule ainsi :

int b = (int)Math.ceil(Math.log(n) / Math.log(2));

mais cela est relativement coûteux et compliqué. Une solution plus simple consiste à utiliser la méthode numberOfLeadingZeros de la classe Integer en tirant parti de l'égalité suivante : \[ \left\lceil\log_2(x)\right\rceil = 32 - \texttt{numberOfLeadingZeros}(x - 1) \] valable pour tout \(x>0\) de type int.

En appliquant cette nouvelle version du compresseur au texte de Candide déjà utilisé pour la série précédente, vous devriez obtenir un fichier compressé d'une taille de 99 797 octets. Cela correspond à un taux de compression de plus de 57%, passablement mieux que les 48% obtenus avec le compresseur à taille fixe.

La table ci-dessous compare ce taux de compression avec celui obtenu au moyen d'autres programmes de compression :

Comme on le voit, à l'exception de compress — qui utilise aussi l'algorithme LZW — les autres programmes produisent de meilleurs résultats que le nôtre. Ils sont toutefois passablement plus complexes. (Pour la petite histoire, bzip2 et bzip3 utilisent, entre autres, la transformée de Burrows-Wheeler.)