Transformée Burrows Wheeler

La transformée de Burrows-Wheeler (aussi appelé BWT) est la seconde étape, mais pas des moindres, de l'algorithme de compression bzip2. C'est d'ailleurs l'un des deux principaux rouages de l'algorithme d'après son auteur :

bzip2 compresses files using the Burrows-Wheeler block sorting text compression algorithm, and Huffman coding.

- Julian Seward

Utilisation

Cette transformée est utilisée pour faire apparaître des motifs redondants dans une séquence de lettres ou d'octets, ce qui aide à la compression avec l'encoding d'Huffman.

Elle est aussi utilisée dans le domaine de la génétique, pour chercher une sous-chaine (une séquence) dans un génome humain de plusieurs gigaoctets.

Principe de fonctionnement

La transformée

La transformé de Burrows-Wheeler se construit à partir d'une matrice de permutations des lettres du mot (ou d'une séquence d'octet de façon générale).

Prenons le mot ABRACADABRA. Voici les étapes à suivre :

1. On créer la matrice des rotations

Il y a autant de rotations que de lettres/octets

A B R A C A D A B R A
B R A C A D A B R A A
R A C A D A B R A A B
A C A D A B R A A B R
C A D A B R A A B R A
A D A B R A A B R A C
D A B R A A B R A C A
A B R A A B R A C A D
B R A A B R A C A D A
R A A B R A C A D A B
A A B R A C A D A B R

2. On trie les lignes suivant un ordre choisi, qu'il fraudra respecter pour l'inverse de la transformée. Ici, je choisis l'ordre alphabétique

A A B R A C A D A B R
A B R A A B R A C A D
A B R A C A D A B R A
A C A D A B R A A B R
A D A B R A A B R A C
B R A A B R A C A D A
B R A C A D A B R A A
C A D A B R A A B R A
D A B R A A B R A C A
R A A B R A C A D A B
R A C A D A B R A A B

3. On trouve la ligne contenant le mot initial, et on retiens sont indice I

A A B R A C A D A B R
A B R A A B R A C A D
A B R A C A D A B R A  I=3
A C A D A B R A A B R
A D A B R A A B R A C
B R A A B R A C A D A
B R A C A D A B R A A
C A D A B R A A B R A
D A B R A A B R A C A
R A A B R A C A D A B
R A C A D A B R A A B

4. Pour finir cette transformée, nous devons avoir l'indice du mot initial et la dernière colone de la matrice :

A A B R A C A D A B R
A B R A A B R A C A D
A B R A C A D A B R A  I=3
A C A D A B R A A B R
A D A B R A A B R A C
B R A A B R A C A D A
B R A C A D A B R A A
C A D A B R A A B R A
D A B R A A B R A C A
R A A B R A C A D A B
R A C A D A B R A A B

Le résultat est donc 3RDARCAAAABB. On voit que dans cet exemple, quatre A se suivent ainsi que deux B. Il est facile d'imaginer que sur des séquences beaucoup plus grande, il y aura suffisament de motifs redondants pour que la compression soit bonne.

Algorithmes

À partir du document officiel, on peut établir plusieurs versions d'implémentations de la transformée de Burrows-Wheeler. Une première "naïve", en appliquant sans se poser de question la transformée. La seconde en se basant sur la partie 4 An efficient implementation de l'article officiel.

Implémentation naïve

grande matrice, mais limitation...

Implémentation avancée

... donc on fait autrement

Sources

• A block sorting lossless data compression algorithm
• Wikipedia EN
• A tutorial on Burrows-Wheeler indexing methods