Transformée de Burrows-Wheeler - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
La transformée de Burrows-Wheeler, couramment appelée BWT (pour Burrows-Wheeler Transform) est une technique utilisée en compression de données. Elle fut inventée par Michael Burrows et David Wheeler. Cette technique fut rendue publique en 1994, à la suite de travaux précédents de Wheeler en 1983. Il ne s'agit pas à proprement parler d'un algorithme de compression, car aucune réduction de taille n'est effectuée, mais bien d'une méthode de réorganisation des données : les probabilités pour que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte sont alors augmentées. Cette technique n'est pas d'usage très fréquent, mais l'on peut cependant remarquer qu'elle est présente dans le format bzip2 qui est actuellement l'un de ceux offrant un des meilleurs taux de compression. Elle a récemment fait l'objet de nombreuses utilisation en génomique, pour traiter des problèmes de comptage de mots (détection de répétitions), ou de recherche de mots avec erreurs (alignement de lectures courtes issues des nouvelles technologies de séquençage) dans les très grands textes que peuvent définir les génomes eucaryotes.
Fonctionnement
La transformée de Burrows-Wheeler ne compresse pas les données, elle se contente de les réorganiser de manière à obtenir un meilleur taux de compression.
Tout d'abord, la chaîne de caractères à coder doit être copiée dans un tableau carré en décalant la chaîne d'un caractère vers la droite à chaque nouvelle ligne. Ces lignes sont ensuite classées par ordre alphabétique. Nous savons que, grâce au décalage, chaque dernière lettre de chaque ligne précède la première lettre de la même ligne, sauf pour la ligne originale dont on notera la position. De plus, comme les lignes sont rangées par ordre alphabétique, on peut retrouver la première colonne du tableau grâce à la dernière colonne.
Prenons un exemple : supposons que la chaîne à coder soit « TEXTUEL ». On réalise tout d'abord le tableau. La première lettre est marquée ici en rouge pour améliorer la lecture du tableau.
Chaîne T E X T U E L L T E X T U E E L T E X T U U E L T E X T T U E L T E X X T U E L T E E X T U E L T
Puis l'on classe ces chaînes par ordre alphabétique :
Chaîne Position E L T E X T U 1 E X T U E L T 2 L T E X T U E 3 T E X T U E L 4 <- position du texte original T U E L T E X 5 U E L T E X T 6 X T U E L T E 7
Le texte codé est alors constitué de la dernière colonne précédée de la position du texte original, soit : « 4UTELXTE ». La position du texte original sert au décodage.
Cette transformation n'apporte aucun gain de compression immédiat, au contraire, car il est nécessaire de transmettre des informations supplémentaires pour le décodage. Cependant, pour un texte relativement long en langage naturel, qui contient plusieurs fois les mêmes mots, le texte codé comportera de nombreuses répétitions de caractères. Ainsi, Burrows et Wheeler recommandent d'utiliser ensuite un algorithme de type MTF qui, de par les répétitions de caractères, génèrera beaucoup de 0. Ceci assure avec un algorithme de type codage de Huffman un quotient de compression élevé.
Le décodage consiste à reconstruire le tableau complet à partir de sa dernière colonne (texte codé « UTELXTE ») à partir de laquelle on reconstruit la colonne « suivante », c’est-à-dire, par rotation, la première, dont on sait qu’elle est dans l’ordre alphabétique (« EELTTUX »). On colle alors la dernière colonne juste avant cette première colonne, puis on classe dans l’ordre alphabétique les paires obtenues pour construire les deux premières colonnes. On répète ensuite cette opération jusqu’à constituer le tableau complet dans lequel on retrouve le texte original par son numéro de ligne :
| Initiation | Tri | Collage | Tri | Collage | Tri |
|---|---|---|---|---|---|
U T E L X T E | E E L T T U X | UE TE EL LT XT TU EX | EL EX LT TE TU UE XT | UEL TEX ELT LTE XTU TUE EXT | ELT EXT LTE TEX TUE UEL XTU |
| Collage | Tri | Collage | Tri | Collage | Tri |
UELT TEXT ELTE LTEX XTUE TUEL EXTU | ELTE EXTU LTEX TEXT TUEL UELT XTUE | UELTE TEXTU ELTEX LTEXT XTUEL TUELT EXTUE | ELTEX EXTUE LTEXT TEXTU TUELT UELTE XTUEL | UELTEX TEXTUE ELTEXT LTEXTU XTUELT TUELTE EXTUEL | ELTEXT EXTUEL LTEXTU TEXTUE TUELTE UELTEX XTUELT |
| Collage | Tri | Sélection | |||
UELTEXT TEXTUEL ELTEXTU LTEXTUE XTUELTE TUELTEX EXTUELT | ELTEXTU EXTUELT LTEXTUE TEXTUEL TUELTEX UELTEXT XTUELTE | 1 2 3 <- 4 5 6 7 |
On retrouve bien le texte original à la ligne dont le numéro avait été transmis avec le texte codé.
