Burrows–Wheeler transform

1 Burrows–Wheeler transform (BWT) basics

1.1 Definition and intuition

The Burrows–Wheeler transform is a reversible transformation that rearranges the characters of a finite string so that similar symbols tend to appear near one another in the output. Instead of attempting to shorten the string directly, it changes the arrangement in a way that makes the transformed data easier to compress with standard subsequent techniques.

A common intuitive picture is that the transform compares many “rotations” of the input and then emits a carefully chosen column from the sorted list of those rotations. Because sorting tends to align contexts that are similar, the resulting output often contains long runs and recurring patterns.

1.2 Reversibility and why it works

Reversibility is guaranteed by retaining or encoding enough information to reconstruct the original order. In practice, the encoder associates one special position in the transformed output with the end (or a unique marker) of the input. The inverse transform uses that marker to rebuild the original string character by character.

The key idea is that the sorted rotations impose a consistent relationship between two “views” of the data: one view is the first column of the sorted rotations (all leading characters), and the other view is the last column (the BWT output). By repeatedly stepping through this relationship, the decoder can recover the entire original sequence.

1.3 Relationship to sorting rotations

The BWT is typically presented as follows: take all cyclic rotations of the input string, sort these rotations lexicographically, and then form the transformed string by taking the last character from each sorted rotation. This procedure relies on the fact that lexicographic order groups rotations with similar suffix–prefix structure, which correlates with the way repeated contexts appear in text.

1.4 Computational considerations (high level)

Naively generating and sorting all rotations has high cost because the number of rotations grows with the length of the input. Implementations therefore use more efficient approaches based on suffix sorting or other ordering techniques to avoid materializing the full rotation matrix. At the same time, the transform is often applied in blocks: splitting input improves manageability and limits worst-case resource usage, though it may slightly reduce compression efficiency compared with transforming the entire stream.

2 Formal definition

2.1 Building the rotation matrix

Let $s$ be an input string of length $n$. Conceptually, one forms the set of all cyclic rotations of $s$. Each rotation shifts the start position while wrapping around to the end, producing $n$ distinct length-$n$ strings (some may coincide when the input has repeated patterns).

The rotation matrix is the $n \times n$ table whose rows are these rotations.

2.2 Sorting the rotations

The rows of the rotation matrix are sorted lexicographically under the alphabet order of the characters. If a unique end marker is used (as in the standard definition), it ensures that all rotations become distinct and that the sorted order is well-defined.

This sorting step is the core rearrangement performed by the transform.

2.3 Constructing the transformed string

After sorting, the BWT output is formed by taking, for each sorted row, the character that precedes the first character of that row in the original cyclic sense. Equivalently, one can view the output as the “last column” of the sorted rotation matrix (with the understanding that a marker may be included in the string, depending on the chosen convention).

2.4 Handling end-of-string markers

Because cyclic rotations alone do not uniquely determine where the original string ends, many formulations append a sentinel symbol $\$$ that is strictly smaller than all other characters and occurs exactly once. The transform is applied to $s\$$, and the sentinel’s position in the output is used to locate the original string during inversion.

Encoders may transmit the primary index (the row that corresponds to the original string) or transmit the sentinel position explicitly, depending on the chosen convention.

2.5 Edge cases (empty input, repeated characters)

For empty input, the transform reduces to the sentinel alone. For inputs with repeated characters, multiple rotations may be identical if no sentinel is used; the standard sentinel resolves ambiguity by making every rotation distinct. In practice, implementations rely on a consistent marker convention so that encoder and decoder agree on which position is treated as the unique terminator.

3 Inverse Burrows–Wheeler transform

3.1 Core idea (reconstruction from the last column)

Given the BWT output (typically the last column of the sorted rotations) and a marker location or primary index, the inverse transform reconstructs the original string by following the implicit links induced by sorting. Each reconstructed step determines the next character by mapping between occurrences in the last column and corresponding positions in the first column.

This process yields the original sequence exactly, provided the transform conventions match.

3.2 LF-mapping and its role

3.2.1 Mapping between rows and characters

A standard mechanism for inversion is LF-mapping (Last-to-First). It exploits the fact that in the sorted rotation table:

The first column contains the characters of the rotations’ leading positions.
The last column contains the characters of the rotations’ preceding positions (the BWT output).

For a given row $i$, the LF-mapping identifies which row $j$ corresponds to moving one step “forward” in the original rotation sequence. Concretely, it pairs the $k$-th occurrence of a character in the last column with the $k$-th occurrence of that character in the first column.

3.2.2 Iteration strategy for recovery

Once LF-mapping is available, the decoder starts from the row associated with the sentinel (or from the primary index), then repeatedly applies LF-mapping. Each application moves to the next row in the chain, revealing characters in reverse order (or forward order, depending on implementation details). After $n$ steps (where $n$ is the length without the sentinel, or including it depending on convention), the reconstruction completes.

3.3 Practical implementation details

Efficient inversion requires preprocessing the BWT output to support:

Counting character frequencies.
Determining, for each position in the last column, which occurrence number of that character it represents.
Computing prefix sums (cumulative counts) to locate the corresponding block of that character in the first column.

This enables LF-mapping lookups in constant or near-constant time per character.

3.4 Verifying correctness

Correctness can be checked by recomputing the BWT of the reconstructed string and confirming it matches the provided transformed data under the same marker convention. Another sanity check is to ensure that the sentinel (or its row index) is reachable and that the reconstruction length matches the expected input size.

4 Variants and enhancements

4.1 BWT with different primary index conventions

Some systems transmit a “primary index” indicating which sorted row corresponds to the original string (with sentinel). Others rely on the sentinel’s explicit location in the output. Conventions differ in whether indices are 0-based or 1-based, and whether the sentinel is included as part of the transformed length.

These differences do not change the fundamental transform but affect decoder setup. Encoder and decoder must agree exactly.

4.2 Block-based BWT

Because memory and time costs scale with input length, compressors commonly apply BWT to blocks rather than entire files. Each block receives its own marker and metadata (e.g., primary index). Block-based operation improves streaming behavior and limits worst-case resource usage, while potentially reducing cross-block pattern reuse and lowering compression ratio compared with a global transform.

4.3 BWT for multiple inputs/streams

In multi-stream settings (e.g., separate files or interleaved streams), BWT is typically applied independently per stream or per logical record. If combining streams into a shared transformation is desired, a careful framing strategy is required so that markers and boundaries remain unambiguous during inversion.

4.4 Suffix array and suffix-based variants

A common enhancement avoids the full rotation matrix by relating the BWT to suffix ordering. With a sentinel, cyclic rotations correspond closely to suffixes of the terminated string, enabling construction via suffix arrays or similar ordering structures. This can reduce the need for explicit rotation handling and improve performance on large inputs.

5 Building blocks commonly used with BWT

5.1 Move-to-front (MTF) transform

After BWT, the output often contains symbols grouped by context. The move-to-front transform leverages this by maintaining an ordered list (initially in alphabet order) and, for each input symbol, outputting the index of that symbol in the list, then moving it to the front. Frequently recurring symbols tend to receive small indices, which are advantageous for later entropy coding.

5.2 Run-length encoding (RLE)

When BWT produces long stretches of identical characters, run-length encoding compresses those stretches by replacing them with (symbol, run length) pairs. RLE is often applied either directly on the BWT output or on the MTF result, depending on which representation produces more regular runs for the particular data.

5.3 Entropy coding (overview level)

Entropy coding compresses data by assigning shorter codes to more probable symbols. In many BWT-based pipelines, the output of MTF and/or RLE becomes a stream of integers or symbols with skewed distributions, enabling effective entropy coding using schemes such as Huffman coding or arithmetic/range coding.

5.4 Putting it together in a compressor pipeline

A typical general-purpose workflow is:

Apply BWT to a block, producing the last-column string and an index/marker location.
Optionally apply MTF to transform symbols into small integers.
Optionally apply RLE to compress repeats.
Use entropy coding to finalize compression.

The BWT component primarily improves compressibility by restructuring the data; subsequent stages perform most of the bitrate reduction.

6 Applications beyond general-purpose compression

BWT is closely connected to suffix-based data structures used in indexing and pattern matching. Transform-based approaches can support efficient substring queries by enabling backward traversal of contexts. Even when not used directly for compression, BWT-like rearrangements can facilitate building index structures that leverage sorted order.

6.2 Bioinformatics and sequence data use cases

In computational biology, sequences (DNA, RNA, proteins) are often stored and queried at scale. BWT-based methods can be used to preprocess sequence collections so that repetitive local patterns become more compressible and amenable to efficient search. The transform’s reliance on ordering contexts makes it suitable for handling repeated motifs in biological strings.

6.3 Log and string data preprocessing

Structured text logs may include repeated templates and recurring tokens. Applying BWT (often blockwise) can reorganize such data so that follow-on encoders find more regularity, improving storage efficiency or downstream processing performance. Practical deployments typically tailor block size and preprocessing steps to the distribution of log formats.

7 Complexity and performance

7.1 Time complexity (conceptual)

Conceptually, generating and sorting all rotations would be $O(n^2)$ to build the rotation matrix and $O(n^2 \log n^2)$ for sorting, which is impractical for large $n$. Efficient implementations replace rotation handling with suffix ordering techniques, aiming for near $O(n \log n)$ behavior under common assumptions and algorithms.

7.2 Space complexity (conceptual)

Storing full rotation matrices requires $O(n^2)$ memory, so it is generally avoided. Practical methods focus on storing compact ordering structures (e.g., arrays representing suffix order) and temporary buffers proportional to $n$, aiming for manageable $O(n)$ or $O(n \log n)$ space depending on the construction approach.

7.3 Trade-offs: block size vs. compression ratio

Larger blocks improve the chance that BWT captures longer-range structure, which can increase compression effectiveness. Smaller blocks reduce memory usage and latency but may reduce the ability to group patterns that span block boundaries. Many systems choose block sizes to balance these competing factors and to fit specific hardware constraints.

7.4 Impact of alphabet size and input redundancy

If the alphabet is large, symbol frequency distribution can be flatter, which may reduce the effectiveness of subsequent transforms like MTF or RLE. Conversely, highly redundant inputs often benefit more because BWT tends to cluster similar contexts, producing longer runs or stronger symbol locality for entropy coding to exploit.

8 Implementation guidance

8.1 Data structures used in practice

Common data structures include:

Suffix arrays or suffix-array-like representations for ordering.
Arrays of integers for symbol ranks, prefix sums, and occurrence positions.
Buffers for the transformed output and for tracking the primary index.

Efficient inversion typically relies on arrays that encode cumulative counts and occurrence ranks.

8.2 Choosing algorithms for rotation/suffix ordering

Implementers choose among suffix array construction algorithms (or other ordering strategies) based on input size, memory availability, and expected speed. The objective is to produce the last column corresponding to the sorted rotations without explicitly storing them. For decoding, the choice often centers on fast LF-mapping construction and cache-friendly array layouts.

8.3 Memory and streaming constraints

Because BWT inversion needs the transformed block and auxiliary arrays, the approach is usually block-based rather than fully streaming at the character level. Systems designed for low memory typically:

Limit block size.
Use compact integer types when safe.
Reuse buffers between blocks.
Avoid storing unnecessary intermediate representations beyond what is needed for decoding.

8.4 Testing and benchmarking methodology

Testing should cover:

Small strings with known outputs to validate marker/index handling.
Randomized round-trip tests (encode then decode) across varying alphabets and distributions.
Degenerate cases: all identical characters, alternating patterns, and empty input.

Benchmarking should separate transform time from entropy coding time, and should measure both throughput and peak memory for realistic block sizes.

9 Worked example

9.1 Step-by-step transformation walkthrough

Consider an input string $s=\text{"banana"}$. Append a sentinel $\$ $ that is lexicographically smaller than any other character to obtain $\text{"banana\$"}$. All cyclic rotations of this terminated string are generated, sorted lexicographically, and the last character from each sorted rotation is collected to form the BWT output. The encoder also records which sorted row corresponds to the original string (or equivalently the sentinel’s row position), which is necessary for inversion.

(Exact intermediate tables depend on the sentinel and ordering convention used, but the method is the same: enumerate rotations, sort, then take the last column.)

9.2 Step-by-step inverse transformation walkthrough

Given the BWT output and the recorded primary index (or sentinel row), the decoder constructs:

The first column by sorting the BWT output characters.
Occurrence ranks for each position (e.g., the 3rd occurrence of a given character).
LF-mapping that links each last-column position to the corresponding first-column position.

Starting from the sentinel row and applying LF-mapping repeatedly reconstructs the original terminated string in reverse order, after which the sentinel is removed to yield the original input.

9.3 Interpreting intermediate outputs

During inversion, intermediate artifacts such as:

the computed first column,
the occurrence rank arrays,
and the LF-mapping transitions

provide diagnostics. If reconstruction fails to terminate correctly or yields the wrong multiset of characters, it usually indicates a mismatch in marker convention or an error in the occurrence rank pairing logic.

10 Common pitfalls and troubleshooting

10.1 Off-by-one and marker handling

A frequent issue is inconsistent handling of the sentinel in terms of inclusion/exclusion in lengths, or differences between 0-based and 1-based index conventions for the primary index. Another common mistake is treating the sentinel as a normal character during reconstruction rather than using it to anchor the LF-mapping traversal.

10.2 Ambiguities with repeated characters

If a sentinel is omitted or not unique, repeated patterns can cause multiple rotations to be identical, which can break the one-to-one correspondence required for inversion. Even with a sentinel, incorrect character ordering (e.g., wrong sentinel rank relative to the alphabet) can also cause repeated-character ambiguity.

10.3 Mismatched conventions between encoder/decoder

Encoder/decoder mismatches may include:

Different sentinel symbols or different ordering of the sentinel relative to other characters.
Different definitions of the primary index (which row is chosen, and whether the index refers to the terminated string or the raw input).
Different treatment of block boundaries and how metadata is stored.

Ensuring both sides follow the same specification prevents most real-world interoperability failures.

10.4 Incorrect inverse mapping logic

Inverse errors typically arise from:

Computing occurrence ranks incorrectly (e.g., counting from the wrong side).
Building prefix sums with the wrong character ordering.
Off-by-one errors in mapping from a cumulative count range to an exact position.

Debugging strategies include verifying that LF-mapping is a permutation over rows and that the reconstructed output is a permutation (with the sentinel) of the original terminated string.