Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/06877.jsonl.gz/1251

Flots LZW
Série 12
Introduction
Le but de cette série, la seconde du mini-projet sur la compression 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 11. Notez qu'il est très important de bien comprendre la solution de cette série-là pour pouvoir faire celle-ci. Assurez-vous donc que ce soit bien le cas avant de poursuivre.
Pour démarrer, nous vous fournissons une archive Zip contenant :
- les classes
Bits12OutputStreamet
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.
Exercice 1 : encodeur LZW
Ecrivez une classe instanciable nommée
LZWOutputStream, héritant 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
closeafin 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 précédente, 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 à 212 = 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
Bits12OutputStreamcomme décrit ci-après.
Etant donné que ces valeurs encodées sont des entiers compris entre 0 et 4095 (inclus), 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 au fait qu'elle peut recevoir une valeur de type
int quelconque mais ne doit considérer que son octet de poids faible. Dès lors, 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) }
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.
Exercice 2 : décodeur LZW
Ecrivez une classe instanciable nommée
LZWInputStream, héritant 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
closeafin 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.
Exercice 3 : programme principal
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.
Par exemple, en l'appliquant au texte de Candide, de Voltaire, vous devriez constater que si le fichier d'entrée fait 230 604 octets, sa version compressée n'en fait plus que 119 343, un taux de compression de plus de 48%. Sans que ce résultat soit mauvais, il est possible de faire mieux, par exemple en utilisant un dictionnaire de taille variable, sujet de la prochaine série.