Burrows–Wheeler transform - Wikipedia
burrows-wheelerdata-compressionstring-algorithmsbioinformatics
Abstraction: Reversible string permutation preprocessing step for lossless compression
Key points:
- BWT rearranges a string into runs of similar characters by sorting all circular rotations lexicographically and taking the last column; O(n) time and space via suffix arrays
- Invented by David Wheeler in 1983, published with Michael Burrows in 1994; their paper included the BSLDCA compression algorithm using BWT + move-to-front + Huffman/arithmetic coding
- Used in bzip2 for file compression; alignment tools Bowtie, BWA, and SOAP2 use BWT to reduce memory requirements for DNA sequence alignment against reference genomes
- A bijective variant exists that produces a unique transform without needing an EOF marker, based on factoring input into Lyndon words via the Chen–Fox–Lyndon theorem
- The transform is reversible: given only the last column, the first column can be recovered by sorting, and successive columns rebuilt iteratively
- Applied to image compression (outperforming JPEG and JPEG 2000 on medical images) and sequence prediction using the FM-index structure
Connections: Bzip2 · Bowtie · Data Compression · String Algorithms · Suffix Arrays
Source: http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform