Que signifie la transformation de Burrows-Wheeler ?
La transformée de Burrows-Wheeler (BWT) est un algorithme qui prend
blocs de données, tels que des chaînes, et les réorganise en séries de données similaires.
personnages. Après la transformation, le bloc de sortie contient exactement le même
éléments de données avant qu'il ne commence, mais diffère dans l'ordre. La nature de
l'algorithme a tendance à placer des caractères similaires les uns à côté des autres, ce qui rend le
l'ordre des données résultant est plus facile à compresser. Il est donc utilisé dans de nombreuses compressions
algorithmes.
Weendoz explique la transformation Burrows-Wheeler
L'algorithme de transformation de Burrows-Wheeler est un algorithme relativement nouveau inventé en 1994 par Michael Burrows et David Wheeler et basé sur une transformation inédite découverte par Wheeler en 1983, publiée dans leur article « A Block-sorting Lossless Data Compression Algorithm ».
Dans la forme la plus élémentaire, BWT prend un bloc de données tel qu'une chaîne, ajoute un caractère EOF, puis trie toutes les rotations de cette chaîne dans un ordre lexicographique. Le pseudocode ou les étapes suivantes illustrent l'algorithme :
- Créez un tableau contenant des lignes représentant toutes les rotations possibles d'un incrément de la chaîne.
- Triez toutes les lignes par ordre alphabétique.
- Affiche la dernière colonne du tableau.
Par exemple : le mot « banane » ; ajouter un caractère EOF le transforme en « banane$ » puis on applique l'algorithme :
1. Créez un tableau avec des lignes représentant toutes les rotations possibles :
banane$
ananas$b
nana$ba
ana$ban
na$bana
une $banane
$banane
2. Triez les lignes par ordre alphabétique/lexicographique en fonction de la première colonne :
$banane
une $banane
ana$ban
ananas$b
banane$
nana$ba
na$bana
3.Renvoyer la dernière colonne comme sortie BWT : annb$aa
La chaîne résultante est plus facile à compresser car les caractères répétés sont regroupés les uns à côté des autres. Mais des données supplémentaires doivent être stockées avec les données transformées afin qu'une transformation inverse puisse être effectuée. Même si les données transformées résultantes sont plus volumineuses que leur forme originale, leurs caractéristiques de compressibilité sont multipliées par plusieurs, ce qui en fait essentiellement une méthode « gratuite » pour améliorer l’efficacité des méthodes de compression.