BWT
BWT est l'abréviation de la transformée de Burrows-Wheeler, qui réécrit le texte sous une forme où les caractères similaires se regroupent ; c'est la première étape de bzip2.
Objectif
C'est une étape de prétraitement réversible qui améliore la compression ultérieure, en regroupant les caractères identiques pour que RLE et le codage entropique fonctionnent mieux.
Mécanisme
On construit la matrice triée de toutes les rotations cycliques, on prend la dernière colonne et on note le numéro de la ligne d'origine. La transformée inverse restitue le texte original depuis la dernière colonne et le numéro de ligne via l'appariement LF.
Cas d’usage
- Compression bzip2
- Alignement génomique
- Indexation en texte intégral