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.
L'inverse de la transformée
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
Algorithmes Python
Application :
def BTW(word: str) -> Tuple[int, str]:
"""Applique la transformée de Burrows-Wheeler sur `word`"""
# On construit la matrice de rotation en utilsant les listes en compréhensions
matrice = [word[i:] + word[:i] for i in range(len(word))]
# On trie (ici, en suivant l'ordre de la table ASCII)
matrice = sorted(matrice)
# On récupère l'indice de la chaine de départ
index = matrice.index(word)
# On renvoie l'indice et la dernière colone de la matrice
return index, "".join([row[-1] for row in matrice])
Application inverse :
def invert_BTW(index: int, transformed: str) -> str:
"""Applique l'inverse de la transformée de Burrows-Wheeler en fonction de `index` et `transformed`"""
# On initialise la matrice avec 'nombre de lignes = len(transformed)'
matrice = [ [] for _ in range(len(transformed))]
# Pour chaque caractère (ou colone)
for _ in range(len(matrice)):
# On insert le mot `transformed` sur la première colone
for i,row in enumerate(matrice):
row.insert(0, word[i])
# Et on tri les lignes avec la même fonction que précédemment
matrice = sorted(matrice, key=lambda row: "".join(row))
# On retourne la ligne de la matrice qui nous intéresse, grâce à l'indice de départ
return "".join(matrice[index])
Limitations
Le problème de cette algorithme, c'est qu'à chaque fois nous construisons une matrice de taille , avec taille des données passées à la transformée (e.g. : ABRACADABRA -> Matrice 11,11). Cela n'est pas un problème pour des mots, mais pour des fichiers de plusieurs gigaoctets...
Implémentation avancée
... donc on fait autrement