Série 2 – La transformée de Burrows-Wheeler : corrigé

Le corrigé de cette série vous est fourni sous la forme d'une archive Zip incluant le code fourni dans l'énoncé. Les solutions aux principaux exercices sont brièvement décrites ci-dessous.

En supposant l'existance d'une méthode allRotations retournant la liste de toutes les rotations d'une chaîne, la méthode forward est très simple à écrire, puisqu'elle consiste simplement à trier cette liste puis à en extraire la dernière colonne et l'index de la chaîne originale. Pour obtenir ce dernier, la méthode indexOf est fort utile :

public static Pair<Integer, String> forward(String s) {
  if (s.isEmpty())
    throw new IllegalArgumentException();

  List<String> rs = allRotations2(s);
  Collections.sort(rs);
  StringBuilder b = new StringBuilder(s.length());
  for (String r: rs)
    b.append(r.charAt(r.length() - 1));
  return new Pair<>(rs.indexOf(s), b.toString());
}

La solution la plus naturelle (et efficace) pour écrire allRotations consiste à simplement construire le prochain élément de la liste en effectuant une rotation du précédent au moyen d'un bâtisseur de chaîne :

private static List<String> allRotations(String s) {
  List<String> rs = new ArrayList<>(s.length());
  while (rs.size() < s.length()) {
    rs.add(s);
    s = new StringBuilder(s.length())
      .append(s, 1, s.length())
      .append(s.charAt(0))
      .toString();
  }
  return rs;
}

Une autre solution consiste, comme le propose l'énoncé, à transformer la chaîne en une queue de caractères, puis à effectuer les rotations sur cette queue (opération triviale), en retransformant la queue en chaîne à chaque itération.

Cette solution n'est pas forcément conseillée en pratique, étant donné qu'elle est plus complexe et coûteuse que celle ci-dessus, mais elle a l'avantage d'utiliser les queues, et est donc présentée également ci-après. En plus de la méthode allRotations, deux méthodes de conversion entre chaînes et queues de caractères sont définies :

private static Queue<Character> stringToQueue(String s) {
  Queue<Character> q = new ArrayDeque<>(s.length());
  for (int i = 0; i < s.length(); ++i)
    q.add(s.charAt(i));
  return q;
}

private static String queueToString(Queue<Character> q) {
  StringBuilder b = new StringBuilder(q.size());
  q.forEach(b::append);
  return b.toString();
}

private static List<String> allRotations(String s) {
  List<String> rs = new ArrayList<>(s.length());
  Queue<Character> q = stringToQueue(s);
  while (rs.size() < s.length()) {
    rs.add(queueToString(q));
    q.add(q.remove());
  }
  return rs;
}

Une fois simplifié comme suggéré dans l'énoncé, l'algorithme de reconstruction est relativement simple : en partant d'une liste de chaînes vides, il suffit d'ajouter à chaque itération la chaîne encodée comme première colonne, de trier la liste, puis de recommencer. La méthode backward est donc plus simple encore que la méthode forward :

public static String backward(Pair<Integer, String> p) {
  if (! (0 <= p.first()
         && p.first() < p.second().length()))
    throw new IndexOutOfBoundsException();

  String s = p.second();
  List<String> rs =
    new ArrayList<>(Collections.nCopies(s.length(), ""));
  for (int i = 0; i < s.length(); ++i) {
    for (int j = 0; j < s.length(); ++j)
      rs.set(j, s.charAt(j) + rs.get(j));
    Collections.sort(rs);
  }
  return rs.get(p.first());
}

Etant donné que le tableau bidimensionnel utilisé pour le calcul de la transformée est composé des rotations de la chaîne originale, le premier et le dernier caractère de chacune de ses lignes ont la propriété importante d'être contigus dans la chaîne originale. La seule exception à cette règle est celle du premier et dernier caractère de la chaîne originale, qui se trouvent respectivement au début et à la fin d'une des rotations, sans pour autant être contigus dans la chaîne originale.

Dès lors, si on fait l'hypothèse que certaines séquences de deux lettres (appelées bigrammes) apparaissent plus souvent que d'autres, le fait de trier la liste en fonction de la première lettre aura tendance à créer des groupes de lettres identiques dans la dernière colonne.

En pratique, les langues naturelles ont toutes la propriété que la fréquence d'apparition des bigrammes est très peu uniforme. Par exemple, en français, le bigramme es est l'un des plus fréquents. Chaque fois qu'un tel bigramme apparaît dans la chaîne à transformer, une ligne de la liste des rotations se termine par un e et commence par un s. Or comme les lignes sont triées par ordre alphabétique avant l'extraction de la dernière colonne, beaucoup de ces lignes commençant par s se retrouveront côte-à-côte, ce qui aura pour conséquence de regrouper les e dans la chaîne encodée.

Ainsi, la phrase « les essais des vestes » contient 5 occurrences du bigramme es. Si on construit et trie la liste des rotations de cette phrase, on obtient :

 1:  des vestesles essais
 2:  essais des vestesles
 3:  vestesles essais des
 4: ais des vestesles ess
 5: des vestesles essais 
 6: es essais des vestesl
 7: es vestesles essais d
 8: esles essais des vest
 9: essais des vestesles 
10: estesles essais des v
11: is des vestesles essa
12: les essais des vestes
13: s des vestesles essai
14: s essais des vestesle
15: s vestesles essais de
16: sais des vestesles es
17: sles essais des veste
18: ssais des vestesles e
19: stesles essais des ve
20: tesles essais des ves
21: vestesles essais des

Dans cette liste, 7 lignes (13 à 19) commencent par s (étant donné que cette lettre apparaît 7 fois dans la phrase originale), et 5 d'entre elles font partie d'un bigramme es. Dès lors, 5 des 7 lignes se terminent par la lettre e, qui se trouvent ici être réparties en deux groupes. Ces deux groupes sont bien visibles dans la transformée de Burrows-Wheeler de la chaîne ci-dessus, composée de l'index 11 et de la chaîne ssss ldt vasieeseees .