Burrows-Wheeler Transform (BWT)

When you sort all cyclic rotations of a text, every rotation that shares the same suffix ends up adjacent. The last column — the character just before each sorted prefix — collects characters that all preceded the same context in the original text. Repeated patterns mean many rotations share a common suffix, so the same preceding character appears many times in a row in the last column. Those runs are what RLE and move-to-front encoding exploit. The transform is lossless because the first column F (sorted BWT) and last column L (the BWT itself) together encode a complete map — the LF-mapping — letting you reconstruct the original character by character from just these two columns and the key.

On its own, BWT makes text no smaller: the output has exactly the same length and the same characters, only in a different order. Its real job is to be a reversible preparation step that clusters identical characters together so the compressors that follow — move-to-front, run-length encoding, then Huffman or arithmetic coding — have an easy time. The takeaway: the win isn't BWT's output size, but how much more compressible that output becomes.

A compression idea quietly became a cornerstone of genomics. Wrapped in a structure called the FM-index, the BWT lets you search for a short DNA fragment inside a 3-billion-letter human genome while storing that genome in only a couple of gigabytes. Aligners like Bowtie and BWA — the Burrows-Wheeler Aligner — are built on it, so a 1994 compression trick now underpins how millions of sequencing reads are matched every day.