Introduction
The Burrows-Wheeler Transform is a reversible permutation of a string that groups similar characters together. It is not encryption and it does not compress data on its own, but it is the first stage of bzip2 and a key building block in many bioinformatics aligners. Run BWT on "banana" and you get "nnbaaa" plus a row index. That clustered output is what makes the following move-to-front and RLE stages in bzip2 effective. This tool computes the forward and inverse Burrows-Wheeler Transform in your browser. No data leaves your device.
What this tool does
- Computes the forward Burrows-Wheeler Transform of any input text, returning the transformed last column and the row index of the original string.
- Computes the inverse transform, reconstructing the original text from the BWT output and the row index.
- Appends a NUL marker internally so the inverse is unique even for inputs that would otherwise be ambiguous.
- Handles Unicode input by operating on UTF-16 code units, matching JavaScript string semantics.
- Updates in real time as you type or switch between encode and decode modes.
- Runs entirely client-side with no network requests.
How this tool works
In encode mode, the tool appends a NUL byte (\u0000) to your input as an end-of-stream marker, builds all rotations of the resulting string, sorts them lexicographically, and reads off the last column. The position of the original (unrotated) string in the sorted matrix is the row index, which you need to invert the transform. The output shows the transformed string on the first line and the row index on the second.
In decode mode, you paste the transformed string and enter the row index. The tool sorts the transformed string to get the first column, builds the next-vector that maps rows in the first column to rows in the last column, and follows that vector to reconstruct the original string. The NUL marker is stripped at the end. Use the Swap button to flip between modes.
How the Burrows-Wheeler Transform works
The Burrows-Wheeler Transform was described by Michael Burrows and David Wheeler in 1994 in a DEC Systems Research Center technical report. It is a block-sorting transform: it takes a block of text, forms every cyclic rotation, sorts those rotations, and outputs the last column of the sorted matrix.
The reason it clusters characters is that sorting rotations groups together rows that start with the same context. If the input has many occurrences of "the", all rotations starting just before "the" land next to each other in the sorted matrix, so the last column will have a run of "e" characters in that region. Those runs are what downstream stages exploit.
The inverse works because the first column is just the sorted last column, and there is a permutation (the LF-mapping, implemented here as the next-vector) that links positions in the first column to positions in the last column. Starting from the row index and following that permutation n times reconstructs the original string. The row index is required because the transform is a permutation of rows, and you need to know which row was the original.
bzip2 uses BWT followed by move-to-front coding and Huffman coding. The bzip2 format documentation describes the full pipeline. BWT is also used in bowtie2 and BWA for short-read alignment in genomics, where it enables fast lookup of substrings in a reference genome via the FM-index.
How to use this tool
- Select mode: Encode or Decode.
- For encoding: type or paste text. The output shows the transformed string and the row index you need to invert it.
- For decoding: paste the BWT output string and enter the row index from the encode step.
- Use the Swap button to switch between modes.
- Copy the result with the Copy button.
Real-world examples
Reproducing the classic banana example
The textbook example is "banana". Encode it and you get the transformed last column and a row index. The output clusters the repeated 'a' and 'n' characters, which is exactly what makes BWT useful as a pre-compression step. Decode with the same row index to recover "banana" exactly.
Pre-compression stage for bzip2-style pipelines
A developer building a custom compressor wants to verify their BWT implementation before wiring it into move-to-front and RLE stages. They encode a sample of English text, observe that repeated words produce long runs of the same character in the output, and confirm the inverse recovers the input exactly. This validates the BWT stage before they add the downstream coders.
Bioinformatics substring lookup
A bioinformatics student is learning how the FM-index enables fast read alignment in tools like bowtie2. They encode a short reference sequence, inspect the BWT output, and manually walk through the LF-mapping to find where a short query substring would align. The tool makes the forward and inverse steps concrete without needing a full aligner.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Burrows-Wheeler Transform | O(n log n) sort, reversible | bzip2, bioinformatics aligners |
| Move-to-Front | O(n), often paired with BWT | bzip2 stage after BWT |
| Run-Length Encoding | O(n), lossless | Post-BWT in bzip2, fax machines |
| LZ77 / LZSS | O(n), sliding window | DEFLATE, gzip, zlib |
Limitations or considerations
The forward transform builds all n rotations and sorts them, which is O(n log n) in time and O(n) in memory. For very large inputs (megabytes of text) this becomes slow in a browser because the sort compares rotations character by character. Production implementations like bzip2 use a suffix-array construction that is O(n) or O(n log n) with a small constant. This tool uses a NUL marker to guarantee a unique inverse; if your input already contains NUL bytes, the inverse may not match because the marker is no longer unique. For typical text input this is not a problem.
Frequently asked questions
Is the Burrows-Wheeler Transform compression?
No. BWT is a reversible permutation that does not change the size of the data. It rearranges the bytes so that downstream stages like move-to-front and run-length encoding can compress more effectively. bzip2 chains BWT, MTF, and Huffman coding together.
Why do I need a row index to decode?
The transform outputs the last column of the sorted rotation matrix. Many different input strings could produce the same last column, so the row index tells the decoder which row of the matrix was the original unrotated string. Without it, the inverse is ambiguous for some inputs.
Why does the tool append a NUL byte?
The NUL byte acts as a unique end-of-stream marker so the inverse transform is unambiguous. Without a unique marker, some inputs have multiple valid inverses. bzip2 uses a similar sentinel approach. The marker is stripped from the decoded output.
How is BWT used in bioinformatics?
Short-read aligners like bowtie2 and BWA build an FM-index from the BWT of a reference genome. The FM-index lets them find substring matches in O(m) time where m is the query length, without scanning the reference. This is what makes whole-genome alignment feasible for millions of short reads.
Conclusion
The Burrows-Wheeler Transform is a reversible block-sorting step that clusters similar characters, making it the foundation of bzip2 and many bioinformatics aligners. This tool computes the forward and inverse transform in your browser. For the full bzip2 pipeline, pair it with the RLE Encoder. For other compression formats, try the Gzip, Brotli, or Zstandard tools.