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) -> 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 
    num = matrice.index(word)

    # On renvoie l'indice et la dernière colone de la matrice
    return str(num), "".join([row[-1] for row in matrice])

Application inverse :

def invert_BTW(transformed: str) -> str:
    """Unapply Burrows-Wheeler transform for `word`"""
    index, word = int(transformed[0]), transformed[1:]
    matrice = [ [] for _ in range(len(word))]

    for _ in range(len(matrice)):
        # insert word in first column
        for i,row in enumerate(matrice):
            row.insert(0, word[i])
        # Sort alphabetically
        matrice = sorted(matrice, key=lambda row: "".join(row))

    return "".join(matrice[index-1])

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