ExtendedSource checked

Burrows-Wheeler Transform

Reorders text so similar characters become easier to compress.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Compression
Difficulty: Advanced
Family: Transform Coding
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 5
Code example: Not ready
Visualization: Ready
Aliases: BWT

Overview

The Burrows-Wheeler Transform permutes a string into a form with longer runs of related symbols, making later compression more effective.

Core Concepts

reversible transformstring sequencetransform codingsymbol representationlossless decodingstream encoding

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use Burrows-Wheeler Transform when you need to sort rotations of the input.
Use it for text compression with inputs like string or byte sequence.
Use it when the data has repetition, predictable structure, or symbol frequency imbalance.
Use it when the Transform Coding tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when small inputs or already compressed data would make metadata larger than the savings.
Avoid it when the required output is not transformed sequence.

What It Does

Sorts rotations of the input
Produces a reversible transformed string

Use Cases

Text compression
Preprocessing before run-length coding
Substring indexing concepts

Inputs

String or byte sequence

Outputs

Transformed sequence
Original position marker

Key Formulas (1)

Last-column transform

output_[i] = last_character(sorted_{rotation i})

output[i] = last_character(sorted_rotation_i)

Builds the transformed text from the last column of the sorted rotation table.

Pseudocode

1.Create conceptual rotations of the input
2.Sort the rotations lexicographically
3.Take the last column of the sorted rotations
4.Record the original row position
5.Use the marker to reverse the transform later

Canonical Example

Input: text = 'AAAABBBCCDAA'
Output: compressed representation with repeated runs or shorter codes
Explanation: Burrows-Wheeler Transform: The algorithm replaces predictable or repeated structure with a more compact representation.

Implementation Notes

Keep the input contract explicit: String or byte sequence.
Use this step as the implementation spine: Create conceptual rotations of the input.
Then preserve the next state change: Sort the rotations lexicographically.
Decide whether indexes mean bytes, code units, characters, or tokens.
Keep encoder and decoder tests paired so every compressed sample round-trips exactly.

Common Pitfalls

Efficient implementations avoid explicitly materializing every rotation.
Indexing by bytes instead of characters can break text with multibyte characters.
Forgetting that the decoder needs the same model, dictionary, or metadata used by the encoder.
Returning transformed sequence without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show sorted rotations and the last column forming the transformed output.

Input:ABABABCABAB

Window:ABAB

Step 1 of 5: Create conceptual rotations of the input

bwt-matrix

Notes

Burrows-Wheeler Transform operates in O(n log n) time and O(n) space within the Transform Coding family. Key governing relation: output[i] = last_character(sorted_rotation_i). Often compared with Run-Length Encoding and Suffix Array Search.