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, ce qui aide à la compression avec l'encoding d'Huffman.
Principe de fonctionnement
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éral).
Prenons le mot ABRACADABRA. Voici les étapes à suivre :
1. On créer la matrice des rotations
ABRACADABRA BRACADABRAA RACADABRAAB ACADABRAABR CADABRAABRA ADABRAABRAC DABRAABRACA ABRAABRACAD BRAABRACADA RAABRACADAB AABRACADABR
2. On trie les lignes suivant un certain ordre. Ici, par ordre alphabétique
AABRACADABR ABRAABRACAD ABRACADABRA ACADABRAABR ADABRAABRAC BRAABRACADA BRACADABRAA CADABRAABRA DABRAABRACA RAABRACADAB RACADABRAAB
3. On trouve la ligne contenant le mot initial, et on retiens sont indice I
AABRACADABR ABRAABRACAD ABRACADABRA I=3 ACADABRAABR ADABRAABRAC BRAABRACADA BRACADABRAA CADABRAABRA DABRAABRACA RAABRACADAB RACADABRAAB
4. Pour finir cette transformée, nous devons avoir l'indice du mot initial et la dernière colone de la matrice :
AABRACADABR ABRAABRACAD ABRACADABRA I=3 ACADABRAABR ADABRAABRAC BRAABRACADA BRACADABRAA CADABRAABRA DABRAABRACA RAABRACADAB RACADABRAAB
Le résultat est donc 3RDARCAAAABB. On voit que dans cette 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 motif redondant pour que la compression soit bonne.
Algorithmes
variations d'algorithme...
Implémentation naïve
grande matrice, mais limitation...
Implémentation avancé
... donc on fait autrement