Burrows-Wheeler Transform
The Burrows-Wheeler transform (BWT) sorts all cyclic rotations of a text and takes the last column, clustering similar characters together to prepare the data for subsequent compression.
Purpose
It is a reversible transform that rewrites text into a more compressible form (similar characters clustered), and is the first stage of the bzip2 pipeline.
Mechanism
Build the matrix of all cyclic rotations of the text, sort the rows, and take the last column as the BWT output while recording the index of the original row. The inverse transform recovers the text via the LF mapping and that index.
Use cases
- Pre-transform in bzip2 compression
- Genome sequence analysis
- Full-text index construction