Burrows–Wheeler Transform

The Burrows-Wheeler transform (BWT) is a technique for rearranging/reordering characters in a text message. Mainly used in data compression, BWT tends to bring identical characters closer together, this property is used as a pre-processing that then allows for further compression (e.g. by RLE coding).

Step 1: list all possible rotations of the message (of the character string).

Step 2: sort this list in alphabetic/lexicographic order.

Step 3: Extract the last characters of each line/rotation. The encrypted message consists of these letters/characters.

In the original version of the article describing BWT, a numeric key is associated with this message. This key value is the rank of the original message once the list is sorted.

In practice, it is common for the string to end with a special character like null (00) or ETX (End of Text) or EOF (End of File). This additional character/byte allows you to do without a key because it indicates the end of the message. It is often represented by the $ character.

Decryption/Burrows Wheeler Inverse Transformation requires to know the key and the ciphered message (with N characters).

Step A: initialize an empty array with N rows and N columns.

Step B: write the encrypted message in the last empty column of the table

Step C: sort the rows of the table in alphabetical order

Repeat steps B and C as many times as there are letters in the message.

Once the algorithm is completed, the plaintext is at the row number key of the table.

If the text was encoded with a special character at the end (like null or EOF), then the key is not needed, because the original message (among all the rotations) is the one with this special character at the end.

The key is actually unimportant for intelligible text because when decrypting all the lines of the final table are actually rotations of the original text.

If a special character, such as null or EOF, has been added to the end of the text before encoding, it is not necessary to use a key to decode. The original message can be identified directly: it is the one, among all possible rotations, that ends with this special character.

dCode offers to calculate the most probable key automatically when the text is in English.

The BWT key is calculated automatically and cannot be chosen.

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.

BWT can be used without a key, but in this case, a unique character of the original text and its position are needed, such as EOF character or null placed in last position.

Several implementations are possible but the best ones are in O(n) for the duration and O(n log(σ) (or even better) for the memory. With n the input size and σ the size of the alphabet.

Burrows-Wheeler Transform was invented in 1994 by Michael Burrows and David Wheeler