BWT
BWT is the abbreviation for the Burrows-Wheeler transform, which rewrites text into a form where similar characters cluster together, and is the first stage of bzip2.
Purpose
It is a reversible preprocessing step that improves subsequent compression, clustering identical characters so RLE and entropy coding work better.
Mechanism
Build the sorted matrix of all cyclic rotations, take the last column, and record the original row number. The inverse transform recovers the original text from the last column and the row number via the LF mapping.
Use cases
- bzip2 compression
- Genome alignment
- Full-text indexing