Transformée de Burrows-Wheeler (BWT)

Lorsqu'on trie toutes les rotations cycliques d'un texte, chaque rotation qui partage le même suffixe se retrouve adjacente aux autres. La dernière colonne — le caractère juste avant chaque préfixe trié — rassemble les caractères qui précédaient le même contexte dans le texte original. Les motifs répétés font que de nombreuses rotations partagent un suffixe commun, si bien que le même caractère précédent apparaît plusieurs fois de suite dans la dernière colonne. Ce sont ces séquences que le RLE et le codage move-to-front exploitent. La transformation est sans perte car la première colonne F (BWT triée) et la dernière colonne L (la BWT elle-même) codent ensemble une correspondance complète — la correspondance LF — permettant de reconstruire le texte original caractère par caractère à partir de ces deux colonnes et de la clé.

À elle seule, la BWT ne rend pas le texte plus petit : la sortie a exactement la même longueur et les mêmes caractères, seulement dans un ordre différent. Son vrai rôle est d'être une étape de préparation réversible qui regroupe les caractères identiques, afin que les compresseurs qui suivent — move-to-front, codage par plages, puis Huffman ou codage arithmétique — aient la tâche facile. À retenir : le gain n'est pas la taille de la sortie de la BWT, mais à quel point elle devient plus compressible.

Une idée de compression est discrètement devenue une pierre angulaire de la génomique. Enveloppée dans une structure appelée index FM, la BWT permet de chercher un court fragment d'ADN dans un génome humain de 3 milliards de lettres tout en ne stockant ce génome que dans quelques gigaoctets. Des aligneurs comme Bowtie et BWA — le Burrows-Wheeler Aligner — reposent dessus, si bien qu'un tour de compression de 1994 soutient aujourd'hui l'alignement quotidien de millions de lectures de séquençage.