Transformée de Burrows-Wheeler

La transformée de Burrows-Wheeler (BWT) est une technique de réorganisation/réarrangement des caractères d'un message texte. Principalement utilisée en compression de données, BWT a tendance à rapprocher les caractères identiques, cette propriété est utilisée comme un pré-traitement qui permet ensuite une compression accrue (par exemple par codage RLE).

Etape 1 : lister toutes les rotations du message (décalage cyclique de la chaine de caractères)

Etape 2 : trier la liste par ordre alphabétique/lexicographique

Etape 3 : extraire les derniers caractères de chaque ligne/rotation. Le message chiffré est constitué de ces lettres/caractères.

Dans la version originale de l'article décrivant BWT, une clé numérique est associée à ce message. Cette valeur clé est le rang du message original une fois la liste triée.

En pratique, il est courant que la chaine se termine par un caractère spécial comme null (00) ou ETX (End of Text) ou EOF (End of File). Ce caractère/octet additionnel permet de se passer de clé car il indique la fin du message. Il est souvent représenté par le caractère $.

Le décodage BWT nécessite de connaitre le message chiffré (ayant N caractères) et éventuellement un nombre clé.

Etape A : initialiser un tableau vide avec N lignes et N colonnes.

Etape B : écrire le message chiffré dans la dernière colonne vide du tableau

Etape C : trier les lignes du tableau par ordre alphabétique

Répéter les étapes B et C autant de fois qu'il y a de lettres dans le message.

Une fois l'algorithme terminé, le message clair est situé à la ligne du tableau correspondant à la clé.

Si le texte a été codé avec un caractère spécial à la fin (comme null ou EOF), alors la clé n'est pas nécessaire, car le message original (parmi toutes les rotations) est celui possédant ce caractère spécial à la fin.

La clé est en fait peu importante pour du texte intelligible car lors du déchiffrement toutes les lignes du tableau final sont en fait des rotations du texte original.

Si un caractère spécial, comme null ou EOF, a été ajouté à la fin du texte avant le codage, il n'est pas nécessaire d'utiliser une clé pour décoder. Le message original peut être identifié directement : c'est celui, parmi toutes les rotations possibles, qui se termine par ce caractère spécial.

dCode propose de calculer la clé la plus probable automatiquement quand le texte est en Français.

La clé BWT est calculée automatiquement et ne peut pas être choisie.

Le message codé a tendance a avoir des suites de lettres identiques qui sont répétées, ce qui facilite leur compression (via des algorithmes comme Run Length Encoding - RLE).

Le message a un nombre important de caractères répétés et un indice de coincidence normal.

Le message est parfois surcodé avec un codage de type RLE.

BWT peut être utilisé sans clé, mais dans ce cas, la connaissance d'un caractère unique du texte original et sa position est nécessaire, comme le caractère EOF ou null placé en dernière position.

Plusieurs implémentations sont possibles mais les meilleures sont en O(n) pour la durée et O(n log(σ) (voire mieux) pour la mémoire. Avec n la taille en entrée et σ la taille de l'alphabet.

Burrows-Wheeler Transform a été inventé en 1994 par Michael Burrows et David Wheeler