Tools that apply BurrowsWheeler algorithm. BurrowsWheeler transform (BWT) is an algorithm maximizing repeated letters in a text, which is useful in data compression.
Burrows–Wheeler Transform  dCode
Tag(s) : Compression, Algorithm
dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!
Sponsored ads
Tools that apply BurrowsWheeler algorithm. BurrowsWheeler transform (BWT) is an algorithm maximizing repeated letters in a text, which is useful in data compression.
BWT (Burrows Wheeler Transform) ciphering rearranges letters in the message and associate it a key.
The first step consists in listing all possible rotations the the message.
Example:
DECODE 
EDECOD 
DEDECO 
ODEDEC 
CODEDE 
ECODED 
The second step is sorting this list in alphabetical order.
Example:
1  CODEDE 

2  DECODE 
3  DEDECO 
4  ECODED 
5  EDECOD 
6  ODEDEC 
The ciphered message is constituted of the last letters of each rotation. The associated key is the rank of the original message in the list.
Example: The encrypted message is EEODDC. The key is 2 (DECODE, the original text, is on the line 2 if the table).
dCode ignores all characters other than letters and digits, replacing them by a dot .
Decryption requires to know the key and the ciphered message.
Example: The ciphetext EODC and the key 1
To decrypt, imagine an empty table, and repeat the following algorithm (A,B) as many times as the number of letter in the message:
A) Write the message in the first column of the table (shifting the others columns)
B) Sort the lines of the table by alphabetic order
Example:
A(1)  B(1)  A(2)  B(2)  A(3)  B(3)  A(4)  B(4)  








When finished, the plaintext is at the line number key of the table.
Example: At the row 1, after the last step of the algorithm, is the plain message: CODE
The encoded message tends to have identical sequences of letters that are repeated, which facilitates their compression (via algorithms like Run Length Encoding  RLE).
The ciphered message has a high number of repeated letters and a classic index of coincidence.
The message is sometimes overencrypted with a RLE encoding.
The key is not really important for intelligible text, because when decrypting, all lines of the table are in fact rotations of the original text.
BWT can be used without key, but in this case, a unique character of the original text and its position are needed, for instance in computer EOF character is used for last one.
Several implementations are possible but the best ones are in \( O(n) \) for the duration and \( O(n \log \sigma) \) (or even better) for the memory. With \( n \) the input size and \( \sigma \) the size of the alphabet.
In 1994 by Michael Burrows and David Wheeler
dCode retains ownership of the source code of the script Burrows–Wheeler Transform online. Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, Matlab, etc.) which dCode owns rights will not be given for free. To download the online Burrows–Wheeler Transform script for offline use on PC, iPhone or Android, ask for price quote on contact page !