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, Algorithme
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 ? Ecrire à dCode !
Un encodage ou chiffrement par la transformée de Burrows-Wheeler (BWT) réorganise les lettres du message et y associe une clé.
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 ne conserve que les lettres et les chiffres, les autres caractères sont substitués par un point .
Le déchiffrement BWT nécessite de connaitre la clé et le message chiffré.
Exemple : Soit le message EODC et la clé 1
Pour déchiffrer, imaginer un tableau vide et répéter l'algorithme (A,B) suivant autant de fois qu'il y a de lettres dans le message.
A) Ecrire le message chiffré dans la premiere colonne du tableau (en décalant les autres colonnes)
B) Trier les lignes du tableau par ordre alphabétique
Exemple :
A(1) | B(1) | A(2) | B(2) | A(3) | B(3) | A(4) | B(4) | ||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
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
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).
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.
La clé est en fait peu important pour du texte intelligible car lors du déchiffrement toutes les lignes du tableau final sont en fait des rotations du texte original.
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.
Plusieurs implémentations sont possibles mais les meilleurs 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.
En 1994 par Michael Burrows et David Wheeler
dCode se réserve la propriété du code source de l'outil 'Transformée de Burrows-Wheeler' en ligne. Sauf code licence open source explicite (indiqué CC / Creative Commons / gratuit), tout algorithme pour 'Transformée de Burrows-Wheeler', applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toute fonction liée à 'Transformée de Burrows-Wheeler' (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codé en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) aucune donnée, téléchargement, script, copier-coller, ou accès API à 'Transformée de Burrows-Wheeler' ne sera cédé gratuitement, idem pour un usage hors ligne, PC, tablette, appli iPhone ou Android ! dCode est gratuit est en ligne.
Rendez-vous sur notre communauté Discord dCode pour participer au forum d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !
Grâce à vos remarques, réponses et commentaires pertinents, dCode peut développer le meilleur outil 'Transformée de Burrows-Wheeler', alors écrivez-nous c'est gratuit ! Merci !