Burrows-Wheeler Transform
La transformée de Burrows-Wheeler (BWT) trie toutes les rotations cycliques d'un texte et prend la dernière colonne, regroupant les caractères similaires afin de préparer les données à la compression ultérieure.
Objectif
C'est une transformée réversible qui réécrit le texte sous une forme plus compressible (caractères similaires regroupés) ; c'est la première étape du pipeline de bzip2.
Mécanisme
On construit la matrice de toutes les rotations cycliques du texte, on trie les lignes et on prend la dernière colonne comme sortie BWT en notant l'indice de la ligne d'origine. La transformée inverse restitue le texte via l'appariement LF et cet indice.
Cas d’usage
- Prétransformée dans la compression bzip2
- Analyse de séquences génomiques
- Construction d'index en texte intégral