Search for a tool
Burrows–Wheeler Transform

Tools that apply Burrows-Wheeler algorithm. Burrows-Wheeler transform (BWT) is an algorithm maximizing repeated letters in a text, which is useful in data compression.

Results

Burrows–Wheeler Transform -

Tag(s) : Compression, Algorithm

Share
dCode and more

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!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Thanks to your feedback and relevant comments, dCode has developed the best 'Burrows–Wheeler Transform' tool, so feel free to write! Thank you!

Burrows–Wheeler Transform

BWT Compress

How to encrypt using BWT cipher?

BWT (Burrows Wheeler Transform) ciphering rearranges letters in the message and associate it a key.

The first step consists in listing all possible rotations of the message (of the character string).

Example:

 DECODE EDECOD DEDECO ODEDEC CODEDE ECODED

The second step is sorting this list in alphabetical order.

Example:

1 CODEDE DECODE DEDECO ECODED EDECOD 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 .

How to decrypt BWT cipher?

Decryption/Burrows Wheeler Inverse Transformation 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)
 E O D C
 C D E O
 EC OD DE CO
 CO DE EC OD
 ECO ODE DEC COD
 COD DEC ECO ODE
 ECOD ODEC DECO CODE
 CODE DECO ECOD ODEC

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

Why BWT is used in data-compression?

The encoded message tends to have identical sequences of letters that are repeated, which facilitates their compression (via algorithms like Run Length Encoding - RLE).

How to recognize BWT ciphertext?

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.

How to decipher BWT without key?

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.

What are the variants of the BWT cipher?

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.

What is the complexity of the BWT algorithm?

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.

When BWT have been invented?

In 1994 by Michael Burrows and David Wheeler

Source code

dCode retains ownership of the online 'Burrows–Wheeler Transform' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any 'Burrows–Wheeler Transform' algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any 'Burrows–Wheeler Transform' function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for 'Burrows–Wheeler Transform' will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.

Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Thanks to your feedback and relevant comments, dCode has developed the best 'Burrows–Wheeler Transform' tool, so feel free to write! Thank you!

Source : https://www.dcode.fr/burrows-wheeler-transform
© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.
Feedback