Série 4 – Flots LZW

Le but de cette série, la seconde du miniprojet LZW, est d'écrire des classes permettant de compresser et décompresser des flots d'octets au moyen de l'algorithme LZW introduit dans la série 2.

Pour démarrer, nous vous fournissons une archive Zip contenant :

• les classes Bits12OutputStream et Bits12InputStream, représentant des flots d'entiers de 12 bits et décrites ci-dessous,
• une classe de test, LZWStreamTest, vous permettant de tester votre solution.

Ecrivez une classe LZWOutputStream publique et finale, qui hérite de OutputStream et qui compresse à la volée les données qu'on lui fournit avant de les passer à un flot sous-jacent, au moyen de l'algorithme LZW. Son constructeur doit prendre un seul argument, le flot sous-jacent, de type OutputStream et dans lequel les valeurs compressées sont écrites. De plus, elle doit redéfinir :

• la méthode write — uniquement la variante qui ne prend qu'un seul argument de type int — afin de compresser les données au passage, comme le fait GZIPOutputStream,
• la méthode close afin de s'assurer que toutes les valeurs compressées ont bien été écrites, et de fermer le flot sous-jacent.

Notez que LZWOutputStream représente ce que la bibliothèque Java appelle un flot filtrant, et pourrait donc hériter de FilterOutputStream plutôt que de OutputStream. Comme il n'y a pas de réel avantage à faire cela, nous ne le conseillons pas, mais ne l'interdisons pas non plus.

LZWOutputStream est assez semblable à la classe LZWConcreteEncoder de la série 2, dont vous pouvez vous inspirer, mais avec quelques différences importantes :

• l'alphabet est celui des octets, c-à-d des entiers compris entre 0 et 255,
• la taille du dictionnaire est fixée à 2¹² = 4096 entrées, ceci afin que les valeurs compressées puissent être représentées sur 12 bits,
• les données à compresser ne sont pas reçues en une seule fois, mais un octet à la fois via la méthode write ; de même, les valeurs compressées ne doivent pas être retournées en une seule fois, mais écrites petit à petit sur le flot de sortie sous-jacent, à travers un flot de type Bits12OutputStream comme décrit ci-après.

Etant donné que ces valeurs encodées sont des entiers compris entre 0 et 4095, elles peuvent se représenter au moyen d'entiers de 12 bits. Malheureusement, la bibliothèque Java n'offre que des flots d'entiers de 8 bits. Nous mettons donc à votre disposition la classe Bits12OutputStream qui permet de passer de l'un à l'autre. Son constructeur accepte un flot sous-jacent de 8 bits, tandis que sa méthode writeU12 accepte une valeur de 12 bits non signée, c-à-d comprise entre 0 et 4095.

Le principe de fonctionnement de Bits12OutputStream est relativement simple : elle découpe chaque paire successive de valeurs de 12 bits qu'elle reçoit en trois valeurs de 8 bits qu'elle écrit dans le flot sous-jacent. Si un nombre impair de valeurs de 12 bits a été fourni au moment où sa méthode close est appelée, elle ajoute 4 bits nuls de remplissage (padding) à la fin du flot pour obtenir un multiple de 8 bits.

Lors de l'écriture de la méthode write, faites bien attention à une chose : contrairement à ce que le cours pourrait laisser penser, cette méthode ne reçoit pas forcément une valeur comprise entre 0 et 255. Au lieu de cela, elle peut recevoir une valeur de type int quelconque mais ne doit considérer que son octet de poids faible. Pour ce faire, il est conseillé de l'écrire comme ci-dessous, afin d'obtenir, dans b, l'octet à effectivement écrire :

@Override
public void write(int b0) throws IOException {
    int b = b0 & 0xFF;
    // b est compris entre 0 et 255 (inclus)
    // … reste du code (qui n'utilise que b, pas b0)
}

Ne vous en faites pas si vous ne comprenez pas encore ce code, nous verrons sa signification ultérieurement.

Une fois votre encodeur écrit, vous pouvez modifier la méthode newLZWOutputStream de la classe de test fournie puis lancer les tests. Ceux n'utilisant que le compresseur devraient s'exécuter sans erreur.

Ecrivez une classe LZWInputStream publique et finale, qui hérite de InputStream et qui décompresse à la volée les données lues d'un flot sous-jacent au moyen de l'algorithme LZW. Son constructeur doit prendre un seul argument, le flot sous-jacent, de type InputStream et duquel les valeurs compressées sont lues. De plus, elle doit redéfinir :

• la méthode read — uniquement la variante qui ne prend aucun argument — afin de décompresser les données au passage, comme le fait GZIPInputStream,
• la méthode close afin de fermer le flot sous-jacent.

Bien entendu, vous pouvez vous inspirer de la classe LZWConcreteDecoder, et utiliser la classe Bits12InputStream pour lire les valeurs compressées de 12 bits du flot sous-jacent.

Une fois votre décodeur écrit, modifiez la méthode newLZWInputStream de la classe de test fournie puis lancez les tests, qui devraient tous s'exécuter sans erreur.

Ecrivez un programme principal de compression/décompression, c-à-d une classe dotée d'une méthode main permettant de compresser et décompresser des fichiers.

Vous êtes libres d'écrire un programme aussi simple ou complexe que vous le désirez, mais il doit au moins être capable de compresser ou de décompresser un fichier passé en argument sur la ligne de commande.

Pour tester votre compresseur, vous pouvez p.ex. obtenir des fichiers textuels contenant des livres du projet Gutenberg. Ainsi, si vous l'appliquez au texte de Candide, de Voltaire, vous devriez constater que si le fichier d'entrée fait 226'134 octets, sa version compressée n'en fait plus que 119'855, un taux de compression de presque 47%. Sans que ce résultat soit mauvais, il est possible de faire mieux, par exemple en utilisant un dictionnaire de taille variable comme vous le verrez par la suite.