> bwt | transformer | compresser <
// Burrows-Wheeler Transform - transformation de texte réversible pour améliorer la compression
>> fonctionnalités
Entièrement réversible
Transformation sans perte qui peut être inversée exactement.
Regroupement de caractères
Regroupe les caractères similaires pour faciliter la compression par les étapes suivantes.
Cœur de bzip2
Base de nombreux algorithmes de compression inspirés de bzip2.
>> informations techniques
Comment fonctionne BWT
La transformée de Burrows-Wheeler génère toutes les rotations cycliques de la chaîne d entrée, les trie lexicographiquement et renvoie la dernière colonne de la matrice triée avec l indice de la chaîne originale. Cette transformation tend à regrouper les caractères similaires, ce qui les rend très efficaces pour la compression avec RLE, Move-to-Front ou d autres codeurs entropiques.
Exemple BWT
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
Pourquoi utiliser BWT
- Améliore la compressibilité des données
- Transformation entièrement réversible
- Regroupe les contextes similaires
- Base de l algorithme de compression bzip2
- Prétraitement efficace pour d autres codeurs
>> questions fréquentes
Qu est-ce que la transformée de Burrows-Wheeler ?
La transformée de Burrows-Wheeler (BWT) est un algorithme réversible qui réorganise une chaîne de caractères pour produire des séquences avec de longues séries de symboles identiques. Proposé par Michael Burrows et David Wheeler en 1994, il est utilisé comme étape de prétraitement dans des compresseurs comme bzip2 pour obtenir de meilleurs taux de compression.
Pourquoi BWT améliore-t-elle la compression ?
BWT regroupe les caractères qui apparaissent dans des contextes similaires, de sorte que de nombreuses occurrences d un même symbole se retrouvent côte à côte dans la sortie. Ces séries comprimées se traitent très bien avec la RLE, la transformée Move-to-Front ou des codeurs entropiques comme Huffman.
Qu est-ce que le marqueur EOF ?
Le marqueur EOF (fin de fichier), généralement le symbole '$' ou un autre caractère unique, garantit que toutes les rotations sont distinctes et permet de retrouver la position de la chaîne originale. Sans ce marqueur, certaines chaînes n auraient pas de représentation unique. Il est retiré pendant la transformation inverse.
BWT est-elle un algorithme de compression complet ?
Non. BWT n est pas un compresseur à elle seule, mais une transformation qui rend les données plus faciles à compresser. Elle est généralement combinée avec Move-to-Front, RLE et un codeur de Huffman dans des schémas comme bzip2.