Local decodability of the Burrows-Wheeler transform
Sandip Sinha, Omri Weinstein · 2019
The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a reversible preprocessing step that rearranges an n-letter string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings, and is the basis of the bzip compression program. Alas, the decoding process of BWT is inherently sequential and requires Ω(n) time even to retrieve a single character.