Transformée de Burrows-Wheeler
CS-108 — Série 4
Introduction
La transformée de Burrows-Wheeler1 (Burrows-Wheeler transform ou BWT en anglais) est une technique rencontrant de multiples applications en informatique, entre autres en compression. Il s'agit d'une transformation qui s'applique à une chaîne de caractères et produit une paire composée de :
- un index,
- une permutation de la chaîne originale, c-à-d une chaîne de même longueur que l'originale, contenant les mêmes caractères, mais dans un ordre potentiellement différent.
L'intérêt de la BWT est que la version transformée de la chaîne a tendance à regrouper les caractères identiques en séquences contiguës, la rendant plus facile à compresser que la chaîne originale. Par exemple, le virelangue ci-dessous :
Un chasseur sachant chasser sait chasser sans son chien de chasse.
a pour BWT la paire composée de l'index 11 et de la chaîne ci-dessous :
nettnnrrrse.ssshhhhha dsissscccccchaoUeaasueen ssss aaaanie
Comme on le constate, la BWT de ce virelangue contient de nombreuses séquences de caractères identiques. Il n'est pas difficile d'imaginer que cette version est plus facile à compresser que l'originale.
Transformée
La construction de la BWT d'une chaîne est très simple et consiste en trois opérations :
- une liste de toutes les rotations de la chaîne est construite, liste que l'on interprète comme un tableau bidimensionnel de caractères,
- cette liste est triée par ordre alphabétique,
- la dernière colonne et l'index de la chaîne originale en sont extraits, et constituent la transformée de Burrows-Wheeler de la chaîne.
Pour illustrer cette technique, utilisons-la pour déterminer la BWT de la chaîne java. Dans un premier temps, construisons la liste de toutes les rotations de cette chaîne, dont le premier élément est la chaîne originale et chaque élément suivant est obtenu par rotation des caractères de son prédecesseur d'une position vers la droite :
java ajav vaja avaj
Ensuite, trions cette liste par ordre alphabétique :
ajav avaj java vaja
Cela fait, nous pouvons en extraire la dernière colonne, à savoir la chaîne vjaa, et l'index de la chaîne originale, à savoir 2. Nous avons donc déterminé que la BWT de la chaîne java est la paire (2, vjaa).
Transformée inverse
Aussi étonnant que cela puisse paraître, il est possible d'inverser la BWT afin d'obtenir la chaîne originale ! L'idée est de reconstruire progressivement la liste des rotations triées et, cela fait, d'en extraire l'élément à la position donnée par l'index. La reconstruction de la liste se fait en tirant parti du fait qu'elle est composée de rotations de la chaîne, et qu'elle est triée par ordre alphabétique.
Illustrons ce processus de reconstruction sur l'exemple donné plus haut. Initialement, on ne connaît rien d'autre de la liste que sa dernière colonne et sa taille. On peut donc reconstruire la liste partielle ci-dessous, où les points d'interrogation représentent des caractères encore inconnus :
???v ???j ???a ???a
Cela fait, il faut noter qu'une caractéristique importante de la liste est que si l'on fait une rotation de chacune de ses lignes (à gauche ou à droite), on ne change pas ses lignes, mais seulement leur ordre (éventuellement). On peut donc faire une rotation à droite de toutes les lignes de la liste ci-dessus pour obtenir :
v??? j??? a??? a???
Cette liste contient les mêmes lignes que celle que l'on désire reconstruire, mais elles ne sont pas forcément dans le bon ordre ! Néanmoins, il est très facile de corriger de problème, puisqu'on sait que la liste est triée par ordre alphabétique. En triant la liste partielle ci-dessus, on obtient donc :
a??? a??? j??? v???
Cela fait, on connaît la première colonne de la liste. Mais bien entendu, on connaît aussi sa dernière colonne, comme on l'a vu plus haut ! On peut donc compléter la liste ci-dessus ainsi :
a??v a??j j??a v??a
Là encore, on peut effectuer une rotation à droite de chacune des lignes pour obtenir une liste qui contient les mêmes lignes que celle en reconstruction, mais pas forcément dans le bon ordre :
va?? ja?? aj?? av??
L'ordre est une fois de plus facilement rétabli par un tri :
aj?? av?? ja?? va??
Et on peut recommencer la procédure, en ajoutant la dernière ligne, effectuant une rotation, triant le résultat, jusqu'au moment où on a déterminé la totalité des éléments. Les opérations restantes sont résumées ci-dessous (de gauche à droite) :
aj?v vaj? aja? ajav av?j jav? ava? avaj ja?a aja? jav? java va?a ava? vaj? vaja
Il ne reste maintenant plus qu'à extraire la ligne donnée par l'index (2), et on obtient la chaîne originale : java.
Squelette
Pour faciliter votre travail, nous vous fournissons un squelette de projet dans une archive Zip. Commencez par extraire son contenu puis créez un projet IntelliJ à partir du dossier BWTR.
L'archive contient une classe Pair, qui est une version légèrement augmentée de celle vue dans le cours sur la généricité. Cette classe est utile pour représenter le résultat de la BWT, étant donné que celle-ci est justement une paire composé d'un index et d'une chaîne tranformée.
L'archive contient également une classe vide, BurrowsWheelerTransform, et une classe de test, BurrowsWheelerTransformTest. Si vous exécutez ces tests, vous constaterez qu'ils échouent tous, votre but étant de compléter la classe BurrowsWheelerTransform afin qu'ils s'exécutent avec succès.
Exercice 1 : transformée
Le but du premier exercice est de programmer la transformée de Burrows-Wheeler, en complétant la méthode forward de la classe BurrowsWheelerTransform. Cette méthode doit lever l'exception IllegalArgumentException si on lui passe une chaîne vide, et sinon retourner sa transformée de Burrows-Wheeler.
Une manière de calculer la liste des rotations de la chaîne consiste à placer ses caractères dans une file (de type Queue<Character>), car il est trivial d'effectuer une rotation sur une telle file. Même si cette solution n'est pas la plus efficace, ni peut-être la plus naturelle, nous vous encourageons à l'utiliser afin de vous entraîner à manipuler les listes et leurs cas particuliers (piles, files, deques), ce qui est le but de cette série. Cela n'a toutefois rien d'obligatoire.
Attention toutefois, la liste représentant les rotations de la chaîne originale doit être une liste de chaînes, de type List<String>, et non pas une liste de files de caractères. Il vous faut donc écrire des méthodes pour transformer une chaîne en file de caractères, et inversement.
Utilisez la méthode sort de Collections (la version à un seul argument) pour trier les rotations par ordre alphabétique.
Une fois la méthode forward terminée, tous les tests n'utilisant pas la méthode backward devraient s'exécuter sans erreur.
Exercice 2 : transformée inverse
Le but du second exercice est de programmer la transformée de Burrows-Wheeler inverse, en complétant la méthode backward de la classe BurrowsWheelerTransform. Cette méthode doit lever l'exception IndexOutOfBoundsException si l'index qu'on lui passe est invalide pour la chaîne associée.
Notez que vous n'avez pas besoin pour cela de suivre à la lettre la description de l'algorithme donnée plus haut, car il est possible de faire plus simple. En particulier, plutôt que d'ajouter la chaîne encodée dans la dernière colonne de la liste puis d'effectuer une rotation à droite, il est plus simple de directement l'ajouter au début. Réfléchissez bien avant de vous mettre à programmer, cette méthode est très courte !
Une fois la méthode backward terminée, tous les tests devraient s'exécuter sans erreur. Lorsque c'est le cas, utilisez votre mise en œuvre de la BWT pour découvrir quel incipit célèbre se cache derrière la transformée mBWT construite par l'extrait de programme suivant :
String m = "ssssrs;àtsessten .hmmfffm asnsltsLlll" + "ssrlhhhrrr cl lmmb ll aaii eaaouoeçstu uuu" + "eeeeeeee suuu ennu ceeeeeeeo a"; Pair<Integer, String> mBWT = new Pair<>(17, m);
Exercice 3
On l'a vu, la transformée de Burrows-Wheeler a tendance à produire des chaînes contenant des séquences de caractères identiques.
Pouvez-vous expliquer pourquoi elle a cette tendance ?
Notes de bas de page
Du nom de ses inventeurs, Michael Burrows et David Wheeler.