Flots LZW à taille variable
Série 13 – corrigé

Le code du corrigé est disponible sous la forme d'une archive Zip. Les solutions aux différents exercices sont brièvement discutées ci-dessous.

La classe BitsOutputStream possède deux attributs privés de type int contenant les bits en attente (waitingBits) et leur nombre (waitingBitsCount). Initialement, ces deux attributs valent 0.

La méthode writeU commence par vérifier la validité de ses arguments, c-à-d que le nombre de bits à écrire est compris entre 0 et 16, et que la valeur ne contient pas de bits à 1 ailleurs que dans ce nombre-là de bits de poids faible. Cette seconde vérification n'est pas indispensable, mais permet de détecter des utilisations incorrectes de la classe.

Une fois ses arguments validés, elle incorpore les bits reçus dans ceux en attente, mettant également à jour leur nombre. Cela fait, elle écrit autant de ces bits que possible dans le flot sous-jacent. Une fois cette écriture terminée, il reste au maximum 7 bits en attente.

public void writeU(int v, int count) throws IOException {
  if (! (0 <= count && count <= 16))
    throw new IllegalArgumentException();
  if (! (0 <= v && v < (1 << count)))
    throw new IllegalArgumentException();

  waitingBits = (waitingBits << count) | v;
  waitingBitsCount += count;

  while (waitingBitsCount >= 8) {
    out.write(waitingBits >> (waitingBitsCount - 8));
    waitingBitsCount -= 8;
  }
}

Notez que l'appel à la méthode write du flot sous-jacent tire parti du fait que celle-ci n'écrit que les 8 bits de poids faible de son argument, ignorant les autres. Il n'est donc pas nécessaire de les masquer.

La méthode close quant à elle s'assure que tous les bits ont bien été écrits dans le flot sous-jacent, en ajoutant au besoin des bits de remplissage. Cela fait, elle ferme le flot sous-jacent.

@Override
public void close() throws IOException {
  if (waitingBitsCount > 0) {
    out.write(waitingBits << (8 - waitingBitsCount));
    waitingBitsCount = 0;
  }
  out.close();
}

La classe BitsInputStream possède les mêmes attributs privés que la classe BitsOutputStream, puisqu'elle doit également stocker temporairement des bits en attente, mais cette fois ce sont ceux obtenus du flot sous-jacent.

La méthode readU commence par vérifier la validité de son argument. Cela fait, elle lit autant d'octets du flot sous-jacent que nécessaire pour avoir en stock un nombre de bits au moins égal à celui qu'elle doit retourner.

Une fois un nombre de bits suffisant en stock (dans waitingBits), il lui est possible d'en extraire le nombre demandé et de les retourner.

public int readU(int count) throws IOException {
  if (! (0 <= count && count <= 16))
    throw new IllegalArgumentException();

  while (waitingBitsCount < count) {
    int b = in.read();
    if (b == -1)
      return -1;
    waitingBits = (waitingBits << 8) | b;
    waitingBitsCount += 8;
  }

  waitingBitsCount -= count;
  int mask = (1 << count) - 1;
  return (waitingBits >> waitingBitsCount) & mask;
}

Notez l'utilisation du masque nommé mask, dont seuls les count bits de poids faible sont à 1, utilisé pour mettre à 0 les autres bits.

La méthode close ce BitsInputStream se contente de fermer le flot sous-jacent.

L'adaptation du compresseur ne pose, comme le dit l'énoncé, pas de problème.

L'adaptation du décompresseur est un peu plus complexe car celui-ci a toujours un retard d'une itération dans sa mise à jour du dictionnaire. Il faut en tenir compte pour utiliser la bonne taille de celui-ci pour déterminer le nombre de bits de ses index.

Pour ce faire, la méthode read de la classe LZWInputStream détermine la taille future du dictionnaire, c-à-d sa taille après l'itération courante, et utilise cette taille pour calculer le nombre de bits de la prochaine valeur à lire. Seules les lignes liées à ce calcul sont données ici, le reste étant très similaire au code du corrigé de la série 12 :

boolean addEntry =
  dict.size() < MAX_CAPACITY && prevList != null;
int futureDictSize =
  dict.size() + (addEntry ? 1 : 0);