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 cela prendrait trop de place mémoire en plus d'être complètemement innéfficace, dû au grand nombre d'itérations sur la matrice.

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