Outil appliquant l'algorithme de Burrows-Wheeler. La transformée de Burrows-Wheeler (BWT) est un algorithme qui maximise les répétitions de lettres dans un texte, ce qui est très utile en compression de données.
Transformée de Burrows-Wheeler - dCode
Catégorie(s) : Compression
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
Transformée de Burrows-Wheeler
Décompression par BWT
Compression avec BWT
Réponses aux Questions (FAQ)
Qu'est ce que la Transformée de Burrows-Wheeler ? (Définition)
La transformée de Burrows-Wheeler (BWT) est une technique de réorganisation/réarrangement des caractères d'un message texte. Principalement utilisée en compression de données, BWT est un traitement préalable qui a tendance à rapprocher les caractères identiques, cette proximité permet ensuite une compression accrue (par exemple par codage RLE).
Comment encoder avec BWT ? (Principe de chiffrement)
La première étape consiste à lister toutes les rotations du message (de la chaine de caractères).
Exemple :
| DECODE |
| EDECOD |
| DEDECO |
| ODEDEC |
| CODEDE |
| ECODED |
La seconde étape est de trier cette liste par ordre alphabétique.
Exemple :
| 1 | CODEDE |
|---|---|
| 2 | DECODE |
| 3 | DEDECO |
| 4 | ECODED |
| 5 | EDECOD |
| 6 | ODEDEC |
Le message chiffré est constitué des dernières lettres de chaque rotation. La clé associée est le rang trié du message original.
Exemple : Le message encodé est EEODDC. La clé est 2 (DECODE, le texte original, est sur la ligne 2 du tableau).
dCode n'accepte que les caractères ASCII (sans retour à la ligne)
Comment décoder par BWT ? (Principe de déchiffrement)
Le déchiffrement BWT nécessite de connaitre la clé et le message chiffré (et son nombre N de caractères).
Exemple : Soit le message EODC (4 caractères) et la clé 1
Etape A : initialiser un tableau vide avec N lignes et N colonnes.
Etape B : écrire le message chiffré dans la dernière colonne vide du tableau
Etape C : trier les lignes du tableau par ordre alphabétique
Répéter les étapes B et C autant de fois qu'il y a de lettres dans le message.
Exemple : Etat du tableau après chaque étape :
| A | B₁ | C₁ | B₂ | C₂ | B₃ | C₃ | B₄ | C₄ | ||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
Une fois l'algorithme terminé, le message clair est situé à la ligne du tableau correspondant à la clé.
Exemple : A la ligne 1, après le dernier passage de l'algorithme, il y a le message clair CODE
Pourquoi BWT est utilisé en compression de données?
Le message codé a tendance a avoir des suites de lettres identiques qui sont répétées, ce qui facilite leur compression (via des algorithmes comme Run Length Encoding - RLE).
Comment reconnaitre le chiffre BWT ?
Le message a un nombre important de caractères répétés et un indice de coincidence normal.
Le message est parfois surcodé avec un codage de type RLE.
Comment déchiffrer BWT sans clé ?
La clé est en fait peu importante pour du texte intelligible car lors du déchiffrement toutes les lignes du tableau final sont en fait des rotations du texte original.
dCode propose de calculer la clé la plus probable automatiquement.
Quelles sont les variantes du chiffre BWT ?
BWT peut être utilisé sans clé, mais dans ce cas, la connaissance d'un caractère unique du texte original et sa position est nécessaire, par exemple en informatique le caractère EOF pour le dernier.
Quelle est la complexité de l'algorithme BWT ?
Plusieurs implémentations sont possibles mais les meilleures sont en $ O(n) $ pour la durée et $ O(n \log \sigma) $ (voire mieux) pour la mémoire. Avec $ n $ la taille en entrée et $ \sigma $ la taille de l'alphabet.
Quand BWT a-t-il été inventé ?
Burrows-Wheeler Transform a été inventé en 1994 par Michael Burrows et David Wheeler
Code source
dCode se réserve la propriété du code source pour "Transformée de Burrows-Wheeler". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Transformée de Burrows-Wheeler", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les fonctions liées à "Transformée de Burrows-Wheeler" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les données, en téléchargement, script, ou les accès API à "Transformée de Burrows-Wheeler" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.
Citation
Le copier-coller de la page "Transformée de Burrows-Wheeler" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous citez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
Transformée de Burrows-Wheeler sur dCode.fr [site web en ligne], consulté le 03/12/2023,
- Décompression par BWT
- Compression avec BWT
- Qu'est ce que la Transformée de Burrows-Wheeler ? (Définition)
- Comment encoder avec BWT ? (Principe de chiffrement)
- Comment décoder par BWT ? (Principe de déchiffrement)
- Pourquoi BWT est utilisé en compression de données?
- Comment reconnaitre le chiffre BWT ?
- Comment déchiffrer BWT sans clé ?
- Quelles sont les variantes du chiffre BWT ?
- Quelle est la complexité de l'algorithme BWT ?
- Quand BWT a-t-il été inventé ?
