ALGORITHME BWT

La transformée de Burrows-Wheeler, couramment appelée BWT est une technique de tri de données utilisée par des logiciels de compression de donnée. Elle fut inventée par Michael Burrows et David Wheeler. Cette technique fut rendue publique en 1994, suite à de précédents travaux 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 très utilisée, mais l'on peut cependant remarquer qu'elle est présente dans le format bzip2 qui est actuellement l'un des formats offrant le plus grand quotient de compression. 

Comme nous l'avons dit, la transformée de Burrows-Wheeler ne compresse pas les données, elle se contente de les réorganiser de manière à obtenir un plus petit 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 premier exemple. Supposons que la chaîne à coder soit « ALGOPT ». On réalise tout d'abord le tableau de 5 lignes (nombre de lettre). Toutes les lettres sont décalées vers la droite. Une fois terminé cette opération, on trie par ordre alphabétique.



Pour la décompression, il est nécessaire de garder en mémoire la position de la chaîne originale. Le texte codé est donc : « 1TLAGOP »

Prenons un second exemple : « TEXTE ».

La position de la chaîne originale est ici 4. Le texte codé est donc la dernière colonne, soit : « 4TTXEE »

Le lien suivant présente la méthode pour réaliser le tranformé inverse de BWT: Decoding BWT

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, Burrows et Wheeler recommandent ensuite d'utiliser un algorithme de type MTF. Ainsi, la chaîne possédant de nombreuses répétitions de caractères contiendra beaucoup de 0. Ceci assure avec un algorithme de type codage de Huffman un quotient de compression élevé.