Flots LZW
Série 12 – corrigé

Le code du corrigé est disponible sous la forme d'une archive Zip, qui contient également le code de l'énoncé. Les solutions aux différents exercices sont brièvement discutées ci-dessous.

Les attributs et le constructeur de la classe LZWOutputStream sont assez similaires à ceux de la classe LZWConcreteEncoder de la série 2. La principale différence est due au fait que l'alphabet est celui des octets, et non plus des caractères. Dès lors, les entrées du dictionnaire et le préfixe sont des chaînes d'octets, que nous avons choisi assez naturellement de représenter par des listes d'entiers de type List<Integer>. Ces listes conviennent bien ici étant donné qu'elles sont comparées de manière structurelle. Bien entendu, les listes stockées dans le dictionnaire doivent être immuables, tandis que la liste représentant le préfixe ne l'est pas.

La classe LZWOutputStream commence donc ainsi :

public final class LZWOutputStream extends OutputStream {
  private final static int DICT_CAPACITY = 4096;
  private final Bits12OutputStream out;
  private final Map<List<Integer>, Integer> dict;
  private final List<Integer> prefix;

  public LZWOutputStream(OutputStream out) {
    Map<List<Integer>, Integer> dict =
      new HashMap<>(DICT_CAPACITY);
    for (int i = 0; i <= 0xFF; ++i)
      dict.put(List.of(i), i);

    this.out = new Bits12OutputStream(out);
    this.dict = dict;
    this.prefix = new ArrayList<>();
  }

  // … méthodes write et close
}

La méthode write se charge de traiter le prochain octet reçu et correspond, en gros, au corps de la boucle for de la méthode encode de la classe LZWConcreteEncoder. Elle commence donc par ajouter l'octet reçu au préfixe, et si celui-ci est toujours dans le dictionnaire, ne fait rien d'autre.

Par contre, si le préfixe ne se trouve pas dans le dictionnaire, alors elle effectue les deux actions requises par l'algorithme LZW, à savoir :

1. elle écrit dans le flot sous-jacent, sous forme d'entier 12 bits et donc à travers un Bit12OutputStream, l'index du préfixe amputé de son dernier octet, qu'elle sait présent dans le dictionnaire,
2. si le dictionnaire n'est pas plein, elle y ajoute une nouvelle entrée pour le nouveau préfixe.

Cela fait, le préfixe est vidé de la totalité de ses octets sauf le dernier. Le code de la méthode write est donc le suivant :

@Override
public void write(int b0) throws IOException {
  int b = b0 & 0xFF;

  prefix.add(b);
  if (dict.containsKey(prefix))
    return;

  List<Integer> choppedPrefix =
    prefix.subList(0, prefix.size() - 1);
  out.writeU12(dict.get(choppedPrefix));

  if (dict.size() < DICT_CAPACITY) {
    List<Integer> immutablePrefix =
      unmodifiableList(new ArrayList<>(prefix));
    dict.put(immutablePrefix, dict.size());
  }
  choppedPrefix.clear();
}

La méthode close se charge quant à elle de bien écrire le dernier préfixe, s'il n'est pas vide, avant de fermer le flot sous-jacent. Elle correspond donc, en gros, au code qui se trouve après la boucle for dans la méthode encode de la classe LZWConcreteEncoder.

@Override
public void close() throws IOException {
  if (! prefix.isEmpty()) {
    out.writeU12(dict.get(prefix));
    prefix.clear();
  }
  out.close();
}

Les attributs et le constructeur de la classe LZWInputStream sont assez similaires à ceux de la classe LZWConcreteDecoder, avec les mêmes différences que celles mentionnées pour l'exercice 1.

Une petite difficulté existe néanmoins pour le décodeur : lorsqu'une valeur compressée de 12 bits est lue depuis le flot sous-jacent, il est possible que l'entrée du dictionnaire qui lui correspond contienne plus d'un octet. Mais comme la méthode read ne peut les retourner que un à la fois, il faut qu'elle puisse les stocker de manière temporaire. Pour ce faire, un attribut nommé currList est ajouté à la classe LZWInputStream. Un deque convient assez bien pour représenter cette liste, étant donné que les ajouts — depuis le dictionnaire — se font à une extrémité, tandis le retrait — pour l'appelant de la méthode read — se fait depuis l'autre extrémité.

En plus de cet attribut currList, il convient d'en ajouter un représentant la dernière liste d'octets décodée, nommé prevList, utile entre autres pour déterminer les ajouts à faire au dictionnaire.

La classe LZWInputStream débute donc ainsi :

public final class LZWInputStream extends InputStream {
  private final static int DICT_CAPACITY = 4096;
  private final Bits12InputStream in;
  private final List<List<Integer>> dict;
  private final Deque<Integer> currList;
  private List<Integer> prevList;

  public LZWInputStream(InputStream in) {
    List<List<Integer>> dict =
      new ArrayList<>(DICT_CAPACITY);
    for (int i = 0; i <= 0xFF; ++i)
      dict.add(List.of(i));

    this.in = new Bits12InputStream(in);
    this.dict = dict;
    this.currList = new ArrayDeque<>();
    this.prevList = null;
  }

  // … méthodes read et close
}

La méthode read utilise l'attribut currList mentionné ci-dessus pour savoir quel octet retourner. Si currList n'est pas vide, elle en retourne simplement le premier octet ; sinon elle se charge d'abord de la remplir en décodant la prochaine valeur de 12 bits du flot sous-jacent puis en consultant le dictionnaire à la position donnée par celle-ci. Comme dans la série 2, il faut traiter correctement le cas où la valeur lue du flot sous-jacent n'est pas encore dans le dictionnaire.

Dans l'ensemble, le corps de la méthode read ressemble beaucoup au corps de la méthode decode de la classe LZWConcreteDecoder de la série 2.

@Override
public int read() throws IOException {
  if (currList.isEmpty()) {
    int i = in.readU12();
    if (i == -1)
      return -1;

    List<Integer> newList = i < dict.size()
      ? dict.get(i)
      : copyAndAppendHead(prevList, prevList);

    if (dict.size() < DICT_CAPACITY && prevList != null)
      dict.add(copyAndAppendHead(prevList, newList));

    currList.addAll(newList);
    prevList = newList;
  }
  return currList.removeFirst();
}

private <T> List<T> copyAndAppendHead(List<T> l,
				      List<T> l2) {
  List<T> r = new ArrayList<>(l.size() + 1);
  r.addAll(l);
  r.add(l2.get(0));
  return Collections.unmodifiableList(r);
}

La méthode close est très simple puisqu'elle n'a rien d'autre à faire que fermer le flot sous-jacent.

Notre version du programme de compression est extrêmement simple et ne mérite pas de description détaillée. Il examine l'extension du nom du fichier passé en argument, et si celle-ci est égale à .lzw alors il le décompresse, sinon il le compresse.