Série 10 – Compression LZW : 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.

Le premier choix à faire pour écrire l'encodeur est celui de la collection à utiliser pour représenter le dictionnaire. La table associative est bien entendu la collection la plus appropriée ici, étant donné que l'encodeur doit, à chaque itération, déterminer si le dictionnaire contient le préfixe actuel. Dès lors, le dictionnaire est une table associant un index à la chaîne correspondant et a donc en Java le type Map<String, Integer>.

L'initialisation du dictionnaire ne pose pas de problème particulier, il suffit d'y placer une entrée pour chaque caractère de l'alphabet :

Map<String, Integer> dict = new HashMap<>(dictCapacity);
for (char c: alphabet)
  dict.put(String.valueOf(c), dict.size());

La méthode d'encodage est un peu plus complexe à écrire, mais suit fidèlement la description de l'algorithme donnée dans l'énoncé. La chaîne à encoder est parcourue du premier au dernier caractère, et son préfixe est progressivement accumulé dans un bâtisseur de chaîne nommé preB tandis que la version encodée est accumulée dans la liste nommée r.

A chaque itération, si le préfixe se trouve dans le dictionnaire, on passe à l'itération suivante. Dès que ce n'est plus le cas, il faut d'une part ajouter une entrée au dictionnaire s'il n'est pas encore plein, et d'autre part ajouter l'index du préfixe amputé de son dernier caractère à la liste encodée.

Une fois la chaîne parcourue dans sa totalité, il ne faut pas oublier d'ajouter le dernier index à la liste si le préfixe n'est pas vide — ce qui ne se produit que dans un cas, lorsque la chaîne à encoder est elle-même vide.

En combinant ces observations, on obtient la méthode d'encodage suivante :

public List<Integer> encode(String str) {
  List<Integer> r = new ArrayList<>();
  StringBuilder preB = new StringBuilder();
  for (int i = 0; i < str.length(); ++i) {
    String pre = preB.append(str.charAt(i)).toString();
    if (dict.containsKey(pre))
      continue;

    if (dict.size() < dictCapacity)
      dict.put(pre, dict.size());
    r.add(dict.get(pre.substring(0, pre.length() - 1)));
    preB.delete(0, preB.length() - 1);
  }
  if (preB.length() > 0)
    r.add(dict.get(preB.toString()));
  return r;
}

Tout comme pour l'encodeur, le premier choix à faire pour le décodeur est celui de la collection à utiliser pour représenter le dictionnaire. On pourrait penser utiliser à nouveau une table associative, mais associant cette fois les chaînes du dictionnaire à leur index. Même si cela n'est pas strictement faux, un meilleur choix est d'utiliser un tableau (dynamique). En effet, un tableau constitue une table associative très efficace lorsque les clefs sont un intervalle dense d'entiers, ce qui est le cas ici.

Dès lors, le dictionnaire de l'encodeur n'est pas représenté par une table associative de type Map<Integer, String> mais bien comme un tableau (dynamique) de type ArrayList<String>. Son initialisation ne pose pas plus de problème que pour l'encodeur, il suffit de lui ajouter un élément pour chaque caractère de l'alphabet, sous forme de chaîne :

List<String> dict = new ArrayList<>(dictCapacity);
alphabet.forEach(c -> dict.add(String.valueOf(c)));

La méthode de décodage est un peu plus complexe, mais pas tant que cela ! Une fois encore, la description de l'algorithme donnée dans l'énoncé est suivie de manière assez fidèle. La liste constituant la version encodée de la chaîne est parcourue, et la chaîne décodée est construite progressivement dans un bâtisseur nommé r. La variable p contient la chaîne décodée lors de l'itération précédente.

A chaque itération, deux cas peuvent se présenter :

1. le prochain index à décoder est un index valide du dictionnaire actuel, auquel cas il suffit d'en extraire la chaîne correspondante,
2. le prochain index à décoder n'est pas un index valide du dictionnaire actuel, ce qui correspond au cas problématique mentionné dans l'énoncé ; la chaîne décodée se construit toutefois facilement en concaténant la chaîne décodée à l'itération précédente (contenue dans p) avec son premier caractère.

Une fois que la chaîne correspondant à l'élément courant de la liste a été obtenue, on peut l'ajouter au bâtisseur du résultat et, si le dictionnaire n'est pas plein, ajouter l'entrée correspondante.

Le code complet de la méthode de décodage est donc :

public String decode(List<Integer> l) {
  StringBuilder r = new StringBuilder();
  String p = null;
  for (int i: l) {
    String s = i < dict.size()
      ? dict.get(i)
      : p + p.charAt(0);
    if (dict.size() < dictCapacity && p != null)
      dict.add(p + s.charAt(0));
    r.append(s);
    p = s;
  }
  return r.toString();
}