Définition - Que signifie la transformation de Burrows-Wheeler (BWT)?
La transformation Burrows-Wheeler (BWT) est un algorithme qui prend des blocs de données, tels que des chaînes, et les réorganise en séries de caractères similaires. Après la transformation, le bloc de sortie contient exactement les mêmes éléments de données avant son démarrage, 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 facilite la compression de l'ordre des données résultant. Par conséquent, il est utilisé dans de nombreux algorithmes de compression.
Definir Tech explique la transformation de Burrows-Wheeler (BWT)
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 non publiée découverte par Wheeler en 1983, publiée dans leur article «A Block-sorting Lossless Data Compression Algorithm».
Dans le plus élémentaire, BWT prend un bloc de données tel qu'une chaîne, en ajoutant un caractère EOF, puis en triant toutes les rotations de cette chaîne dans l'ordre lexicographique. Le pseudocode ou les étapes suivantes illustrent l'algorithme:
- Créez une table qui contient des lignes représentant toutes les rotations possibles d'un incrément de la chaîne.
- Triez toutes les lignes par ordre alphabétique.
- Sortez la dernière colonne du tableau.
Par exemple: le mot «banane»; l'ajout d'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 $
anana $ b
nana $ ba
ana $ ban
na $ moi
une $ banane
$ banane
2. Triez les lignes par ordre alphabétique / lexicographique en fonction de la première colonne:
$ banane
une $ banane
ana $ ban
anana $ b
banane $
nana $ ba
na $ moi
3.Retournez 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 pour qu'une transformation inverse puisse être effectuée. Même si les données transformées résultantes sont plus grandes que leur forme d'origine, mais que leur caractéristique de compressibilité est multipliée par plusieurs, ce qui en fait essentiellement une méthode «gratuite» pour améliorer l'efficacité des méthodes de compression.