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

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 $N\times N$, avec $N=$ 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

Sources

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