Transformation de Burrow-Wheeler
Ce procédé, mis au point pour le logiciel de compression de données Bzip2, transforme les données en les classant, de telle sorte que la compression soit plus efficace. Voici une description très (trop ?) simple de l'algorithme.
Transformation
Nous voulons transformer le mot « BANANA. » . Nous allons donc déplacer une lettre à chaque ligne du tableau, pour obtenir toutes les rotations possibles du mot. Le point '.' possède la valeur numérique la plus grande (255 par exemple).
B A N A N A .
A N A N A . B
N A N A . B A
A N A . B A N
N A . B A N A
A . B A N A N
. B A N A N A
Nous allons ensuite faire un classement alphabétique de ce tableau :
ANANA.B
ANA.BAN
A.BANAN
BANANA.
NANA.BA
NA.BANA
.BANANA
Il ne reste plus qu'à considérer la dernière colonne de texte : BNN.AAA Techniquement, cette chaîne est plus facilement compressible car les caractères sont regroupés.
Transformation inverse
L'avantage de la méthode, c'est qu'elle est réversible. Le mot compressé, BNN.AAA contient toutes les lettres du message original BANANA. ; seul l'ordre est modifié. Partons donc en sens inverse :
B N N . A A A
N N . A A A B
N . A A A B N
. A A A B N N
A A A B N N .
A A B N N . A
A B N N . A A
En classant alphabétiquement, cela donne :
AAABNN.
AABNN.A
ABNN.AA
BNN.AAA
NN.AAAB
N.AAABN
.AAABNN
On remarque que la première colonne est la même que celle utilisée pour l'encodage.
AAABNN.
En suivant la transformation, on obtient le message d'origine : BANANA.