Table des matières:
- Définition - Que signifie la transformation Burrows-Wheeler (BWT)?
- Techopedia explique la transformation Burrows-Wheeler (BWT)
Définition - Que signifie la transformation 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 les mêmes éléments de données exacts 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. Il est donc utilisé dans de nombreux algorithmes de compression.
Techopedia explique la transformation 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 simple, 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 suivants illustrent l'algorithme:
- Créez une table qui contient des lignes qui représentent 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 "banana $" puis nous appliquons l'algorithme:
1. Créez un tableau avec des lignes représentant toutes les rotations possibles:
banane $
anana $ b
nana $ ba
ana $ ban
na $ bana
un banan $
$ banane
2. Triez les lignes par ordre alphabétique / lexicographique en fonction de la première colonne:
$ banane
un banan $
ana $ ban
anana $ b
banane $
nana $ ba
na $ bana
3.Retournez la dernière colonne en tant que 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 il doit y avoir des données supplémentaires 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 grandes que leur forme d'origine, mais 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.
