Transformée de Burrows-Wheeler (BWT)

observez comment des rotations cycliques se trient dans une matrice dont la dernière colonne regroupe les caractères répétés - puis inversez le tout sans perte

Valeurs de départ — Transformée de Burrows-Wheeler (BWT)

Texte d'entrée	banana

Modifiez un réglage ci-dessus et les résultats sont recalculés.

Chargement de la simulation interactive...

pourquoi trier des rotations crée des séquences répétées 🖖

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é.

La BWT réordonne, elle ne réduit pas 🖖

À elle seule, la transformée de Burrows-Wheeler (BWT) ne réduit pas la taille du texte : le résultat a exactement la même longueur et contient les mêmes caractères, mais dans un ordre différent. Elle sert en réalité de préparation réversible. En regroupant les caractères identiques, elle facilite le travail des méthodes de compression suivantes : déplacement en tête, codage par plages, puis codage de Huffman ou codage arithmétique. Avec « abracadabra$ », le résultat contient toujours les douze mêmes caractères, mais les quatre « a » se suivent alors que le texte initial n’en comportait jamais deux côte à côte.

Le même tour qui cartographie votre ADN 🖖

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.

Problème entièrement résolu

La transformée de Burrows-Wheeler de "banana$" avec les sept rotations triées 5 étapes
Trouvez la transformée de Burrows-Wheeler de « banana$ », puis déterminez si une compression a eu lieu. Il s'agit de l'étape sortie BWT : sentinelle ajoutée, les sept rotations triées, dernière colonne extraite.
1. La sentinelle est ajoutée avant toute autre opération. Comme le symbole $ se situe avant toutes les lettres dans l'ordre alphabétique et n'apparaît qu'une seule fois, deux rotations ne peuvent jamais être égales ; le tri donne donc une réponse unique et non ambiguë.
  
  $s = banana$ (n = 7), r_{k} = s [k :] + s [: k], k = 0, \dots, 6$
2. Trier lexicographiquement les rotations est la seule tâche effectuée par la transformée. En parcourant de haut en bas les sept lignes, on remarque que le tri a regroupé la chaîne selon ce qui vient après chaque position.
  
  $$banana, a$banan, ana$ban, anana$b, banana$, na$bana, nana$ba$
3. Le dernier caractère d'une rotation est celui qui précède immédiatement son premier caractère dans la chaîne d'origine. C'est pourquoi le tri produit des plages de répétition : les lignes 1 et 2 commencent toutes deux par 'a' et se terminent toutes deux par 'n', car chacun de ces 'a' est précédé d'un 'n' dans banana. La clé est le numéro de ligne de l'original, sans lequel la transformée ne peut être inversée.
  
  $L_{j} = s_{(k_{j} - 1) mod n} ⟹ L = annb$aa, key = 4$
4. Rien n'a encore été compressé, et rien ne pouvait l'être : le résultat est une permutation de l'entrée, c'est-à-dire les mêmes sept caractères dans un ordre différent. Seule la structure des plages a changé, et c'est la seule modification apportée.
  
  $b ∣ a ∣ n ∣ a ∣ n ∣ a ∣ $ : R = 7, \overset{r}{ˉ} = 1.00 ⟶ a ∣ nn ∣ b ∣ $ ∣ aa : R = 5, \overset{r}{ˉ} = \frac{7}{5} = 1.4$
5. Le codage RLE coûte deux octets par plage, ainsi cinq plages coûtent dix octets pour une entrée de sept octets. Son seuil de rentabilité ne varie pas : le nombre de plages doit être inférieur à la moitié de la longueur, ce qui signifie ici trois ou moins.
  
  $2 R = 10 > N = 7 ⟹ \frac{7}{10} = 0.70 \times, 2 R < N ⟺ R < 3.5$
Réponse

Le panneau affiche annb$aa avec key = 4, une longueur moyenne de plage de 1,4 caractère, 10 octets en RLE et un score de 0,70×. La transformée a fait exactement ce qu'elle promet : elle a augmenté la longueur moyenne des plages de 40% sans modifier un seul caractère, mais la chaîne de traitement reste perdante, car sept caractères ne constituent pas un texte suffisant pour que ce gain compense deux octets par plage. Doublez le mot et l'arithmétique s'inverse. « bananabanana$ » compte treize caractères et sa transformée est annnnbba$aaaa : six plages au lieu de cinq alors que la longueur a presque doublé, ce qui donne 12 octets contre 13 et un score de 1,08×. C'est tout l'intérêt de la TBW : le nombre de plages dépend du nombre de contextes distincts présentés par le texte et non de sa longueur. Ainsi, plus le bloc est long, plus le traitement est avantageux, c'est pourquoi bzip2 transforme des blocs allant jusqu'à 900 kB plutôt que de simples mots.

$bananabanana$ : N = 13, R = 6 ⟹ 2 R = 12 < 13, \frac{13}{12} = 1.08 \times$

Parcours

La compression à la main

Références (3)

Insight blocks 1 and 2 — the transform itself: M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm." Digital Systems Research Center, Research Report 124, 1994.
Insight block 3 — the aligners it turned into: B. Langmead, C. Trapnell, M. Pop and S. L. Salzberg, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biology 10, R25, 2009.
And the one the block names outright: H. Li and R. Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform." Bioinformatics 25(14), 1754–1760, 2009.

Par l’équipe 42Math · Mis à jour 2026-08-17

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

banana - « banana$ » devient « annb$aa » : les trois « a », auparavant toujours séparés, forment désormais deux groupes, et le nombre de plages passe de 7 à 5.
mississippi - « mississippi$ » devient « ipssm$pissii ». C’est l’exemple classique, mais sur un texte aussi court, le nombre de plages reste égal à 9. Le regroupement produit par la BWT devient avantageux avec des textes plus longs.
abracadabra - « abracadabra$ » devient « ard$rcaaaabb » : les quatre « a » se suivent, alors que le texte initial n’en comportait jamais deux côte à côte, et le nombre de plages passe de 12 à 8. Parmi les quatre exemples proposés, c’est le regroupement le plus efficace.
séquence d'ADN - « AGATCAGA$ » devient « AGC$GTAAA » : les trois « A » sont regroupés, alors qu’aucun ne côtoyait un autre « A » dans la chaîne initiale. À l’échelle d’un génome, c’est ce type de structure qu’exploite un index FM.