burrows-wheeler-transform · shipping · also BWT, Block-sorting transform

Burrows-Wheeler transform

The Burrows-Wheeler transform reversibly reorders a block's symbols using sorted cyclic rotations to expose context-dependent repetition.

Transformation: Sort a block's cyclic rotations and take their last column. The 1994 construction also records the original row index so the block can be recovered. That column alone does not identify which rotation was the original input. [1]

Indexing convention: A unique terminator smaller than every ordinary symbol anchors an FM-index text. In the constructed banana$ example, sorted suffixes start at 6, 5, 3, 1, 0, 4, 2 and the last column is annb$aa. The terminator is part of this representation, not a byte that can silently replace an input symbol. [2] [4]

Compression: The last column preserves symbol counts and length; rearrangement alone saves no symbols. Compression comes from subsequent coding that exploits the new locality, with transform metadata included in stored size. [1]

Navigation: LF mapping pairs each occurrence in the last column with the same-ranked occurrence in the sorted first column. In the terminated example it moves one text position backward and enables inversion; adding rank support and position samples enables indexed search. [1] [3]

Relations

related
FM-index, Lossless compression, Run-length encoding, r-index, Prefix-free parsing, Move-to-front transform, Prediction by partial matching

Limitations

  • The example accepts lowercase ASCII with a reserved terminator; general byte streams need an explicit alphabet and terminator representation. [4]

Citations

  1. Burrows and Wheeler: A Block-sorting Lossless Data Compression Algorithm, SRC Report 124 (1994), sections 1-2 and 4.2 (accessed 2026-11-17)
  2. Ferragina and Manzini: Opportunistic Data Structures with Applications, FOCS 2000 author draft, sections 2-3 (accessed 2026-11-17)
  3. Ferragina and Manzini: Indexing Compressed Text, JACM 52(4), 552-581 (2005), sections 3.1 and 3.3 (accessed 2026-11-17)
  4. Hesela: exact BWT search and text-position versus row-sampling example, executable model and observations (accessed 2026-11-17)
Sources & caveats
  • The original report uses a primary-row index; the indexing papers use a unique terminator. These are distinct reversible representations, not interchangeable file formats.
  • The report's historical compression timings are not reused as contemporary performance claims. No paper code or figures are redistributed.

JSON: /data/terms/burrows-wheeler-transform.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Burrows-Wheeler transform. Hesela. 2026-11-17. https://hesela.dev/terms/burrows-wheeler-transform/