01 What is the Burrows-Wheeler Transformation?

Burrows–Wheeler transform – Wikipedia

The Burrows-Wheeler Transformation (BWT) is a method that is used in data compression techniques such as bzip2, but does not perform any data compression itself.

The transformation was developed by Michael Burrows and David Wheeler in 1994.

BWT generates an equally large block of data (output) from a block of data (input) plus a small piece of additional information (an index). The output is a permutation of the input, i.e. the character frequency of input and output is the same, only the order can change.

Since the output contains the same characters more frequently than the input, it is generally easier to compress.

From the output data and the index, the input data can be recovered, i.e. the transformation can be reversed.