BWT

BWT stands for Burrows–Wheeler transform, a reversible data transformation introduced by Michael Burrows and David Wheeler in 1994. It rearranges a string into a form that tends to group identical characters together, making the data more amenable to entropy coding and compression.

The transform operates on a string s of length n that includes a unique end-of-string symbol (often denoted by $) that is lexicographically smaller than all other symbols. All cyclic rotations of s are formed, these rotations are sorted lexicographically, and the last column of the sorted matrix is collected as the transformed string L. The first column F is simply the sorted first characters of the sorted rotations. The end-of-string symbol ensures the process is invertible.

Inverting the transform is possible using the last-to-first (LF) mapping, which links characters in L to their corresponding positions in F. Starting from the position of the terminator, one can reconstruct the original string by repeatedly applying LF. With appropriate data structures, the inversion runs in linear time.

Usage in compression and indexing: The BWT itself does not compress data; it tends to produce runs of identical characters, which can be encoded efficiently with move-to-front transforms and Huffman or arithmetic coding. It is a core preprocessing step in the bzip2 compressor. In bioinformatics, the BWT underpins the FM-index, enabling fast substring queries on large genomes with modest memory usage, by supporting backward search that scans the pattern from right to left.

Variants and notes: BWT can be applied to alphabets of various sizes, and while it is invertible with a terminator, the output depends on the chosen terminator. Related topics include FM-index and bzip2.