The guide
Why sorting every rotation of a text puts its equal letters side by side
The Burrows-Wheeler transform sorts all rotations of a text and keeps the last column. That is only a reshuffle until a marker or an index is added, and a bijective form can do without both.
- NNBAAA the one last column of all 6 rotations of BANANA
- 6 or 7 row index of ^BANANA$ in the table order or in code points
- 67 to 53 runs of equal letters in a 67 letter text, before and after
- 3000 of 3000 seeded random strings recovered by both inverses
- 1092 of 1092 short strings the bijective form tells apart
Read the full guide Fold the guide
Take the six letters BANANA and write down all six of their rotations: BANANA, ANANAB, NANABA, ANABAN, NABANA and ABANAN. Sort them as a dictionary would and read down the last letter of each row. The answer is NNBAAA. Rotate the starting word first and the answer does not change: every one of the six rotations gives NNBAAA. Six letters went in as six runs of one letter, and NNBAAA is three runs, NN, B and AAA. That small gain is the whole idea of the Burrows-Wheeler transform.
Sorting brings the neighbours together
A circular shift moves the final entry to the front and slides the others along, and repeating it brings the original back after n steps. Wikipedia describes the transform as building a matrix whose rows are the circular shifts of the input text, sorted in lexicographic order, and then taking the final column of that matrix. Lexicographic order is dictionary order: compare the first letters, and when they tie compare the second letters, and so on. A word that is a prefix of another comes first.
The comparison has to look at the whole rotation. A sort that stops at the first character puts the three rows that begin with A in an arbitrary order, and the last column is then arbitrary too. The tool sorts complete rotations and says in words which character order it used.
Why do equal letters end up together? A row of the sorted matrix starts somewhere in the text, and its last letter is the letter that sits just before that starting place. Rows are sorted by what follows the starting place, so every row that starts with the same few letters sits in one block, and the last letters of that block are all letters that came just before the same context.
Wikipedia uses an English sentence to show it. Rows that start with the letters he and a space sit together, and their last letters are mostly t, because the word the is common. The page’s sentence THE.MAN.AND.THE.DOG.WAITED.AT.THE.STATION.FOR.THE.TRAIN.TO.THE.CITY has 67 characters and gives a last column with a run of five H and a run of five T.
I counted the runs of equal characters on both sides. The input has 67 runs, because no two neighbouring characters are equal. The output has 53. The longest run grows from 1 to 5. Going from 67 to 53 is a modest gain on a text this short, and the page itself says the transform needs fairly long samples, a few kilobytes at least, of suitable data such as ordinary text, before the effect is large.
A reshuffle until something marks the start
On its own the transform is only a reordering. The output holds exactly the letters of the input, and Wikipedia points out that all circular permutations of a string have the same transform. That is the BANANA result above, and the tool shows it for any text you type. Given NNBAAA alone, there is no way to say which of the six rotations you started from.
Two cures exist. One is to return the row index of the original along with the output, which is the approach of the original paper according to Wikipedia. The other is to add a special end-of-text character before sorting. Either one tells the decoder which row to read.
Add a $ that sorts before every other character to BANANA and the last column becomes ANNB$AA. The row that ends with the marker is the original, and no index needs to travel. The Wikipedia page on suffix arrays adds the reason this form is popular: when the string ends in a smallest end character, the order of the sorted rotations equals the order of the suffixes, so a suffix array gives the transform directly, and suffix arrays can be built in linear time.
The marker has a price. Wikipedia notes that enlarging the alphabet by the end character makes later compression steps awkward. An index has a price as well, a number that has to be stored beside the text. Neither is free, which is part of why a third way exists.
The order of the characters is part of the answer too. Wikipedia’s worked example is ^BANANA$. Its table sorts the letters first, then ^, then $. The last column is BNN^AA$A and the 0-based row index of the original is 6. Many programmers would instead sort by character code. In ASCII the $ sign has a smaller code than the capital letters and the ^ sign has a larger one, so the same text gives ANNB^AA$ and the index is 7.
Both outputs are correct for their order, and the row index of the original is 6 or 7 depending only on that choice. They are different strings for the same input, and a table that does not say which order it used cannot be reproduced. That is why the tool has a switch for the order and prints, beside the result, what the other order would have given. It is also why the index can be read wrongly: read row 7 of the source table’s matrix and the inverse returns the rotation that starts with $, not the text that starts with ^.
Getting the text back
The simple inverse is the one in the Wikipedia pseudocode. Write the last column down, put a copy of it in front of the table, sort the rows, and repeat until the rows are as long as the text. The row that ends with the marker is the original, or the row at the stored index. It works because the first column of the sorted table is the letters in sorted order, so the last and first columns together list every pair of neighbouring letters, and each new round extends the pairs by one letter.
A faster inverse needs no table. In the sorted matrix, the first time a letter appears in the first column is the same occurrence of that letter as the first time it appears in the last column, and likewise for the second time, the third and so on. Equal letters keep their order when the rows are sorted, which is the property that Wikipedia’s page on sorting algorithms calls stability. Start at the original row, read its first letter, jump to the row the link points to, and repeat. One pass of linear length reads the whole text.
That second method is my own derivation, not a statement from the Wikipedia page, so the tool tests it rather than quoting it. A Python 3.13 script generated 3000 seeded random strings over the letters A, B and N and the dollar sign, each between 1 and 14 characters long, in both character orders. The table method recovered 3000 of 3000 of them. The tool repeats the same test with both inverses in its own self-check, and both recovered every string there too.
Without a marker: the bijective form
Wikipedia describes a bijective version in which the transformed string identifies the original uniquely, and the two strings have the same length and the same characters in a different order. Kufleitner’s paper on bijective variants of the transform, which credits the construction to Scott, proves its correctness. Nothing is added and no index is kept.
The construction factors the text into Lyndon words. A Lyndon word is a nonempty string that is strictly smaller than all of its rotations, and the Chen-Fox-Lyndon theorem says every string splits in exactly one way into a non-increasing sequence of them. Duval’s algorithm finds the split in linear time and constant space. Then the rotations of all the words are sorted by comparing their infinite repetitions, and the last character of each rotation is the output.
In the order of the Wikipedia table, ^BANANA splits into ^, B, AN, AN and A, and the output is ANNBAA^. The page’s longer example SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES splits, in plain character code order, into the five words S, IX, .MIXED.PIXIES.SIFT.SIXTY.PIXIE, .DUST and .BOXES. The output STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT has eight runs holding 18 characters, as the page says.
Comparing infinite strings needs a stopping rule. The Fine and Wilf theorem says a word with two periods that is at least their sum minus their greatest common divisor long also has the greatest common divisor as a period. Two repeating words with periods p and q that agree on that many letters therefore agree forever, and p plus q is at most twice the text length. The tool cuts every comparison at twice the length plus 2, a margin I chose, and says so on the page.
As a check I generated every string of length 1 to 6 over three letters with Python’s itertools. There are 1092 of them, and the bijective form gave 1092 of 1092 different outputs, each a permutation of its input and each inverted back to the input. That is a brute-force test over a small set, not a proof for all lengths.
What it does for a compressor
Run-length encoding stores a run of equal values as one value and a count, and Wikipedia notes that it is most efficient on data with many runs. The move-to-front transform replaces each symbol by its place in a list of recently used symbols, so that long sequences of identical symbols become zeros. Both steps are helped by the long runs that the transform creates.
That is how bzip2 uses it. According to Wikipedia the program compresses blocks of between 100 and 900 kilobytes, applies the transform to turn recurring sequences into strings of identical letters, and follows it with move-to-front coding and Huffman coding. The transform alone does not compress anything. The output has the same length as the input.
This page leaves out everything after the transform. It does no move-to-front, run-length or entropy coding, no bzip2 file format and no suffix-array construction for large inputs. Its own sort handles texts up to 2000 printable characters, and the heavy work runs in a Web Worker, which MDN describes as a background thread separate from the main one, so the page stays responsive. Numbers are formatted with the browser’s Intl.NumberFormat.
Try it in this order. Load BANANA with a row index and see NNBAAA. Switch to the added marker and see ANNB$AA. Load ^BANANA$ in both orders and watch the index move from 6 to 7. Load the THE.MAN text and read the run count fall. Then switch on the bijective form and see that nothing was added.
Sources
Every source consulted for this guide. Links checked November 11, 2026.
- Burrows-Wheeler transform - Wikipedia Wikipedia (CC BY-SA 4.0)
- Lyndon word - Wikipedia Wikipedia (CC BY-SA 4.0)
- Monoid factorisation - Wikipedia Wikipedia (CC BY-SA 4.0)
- Suffix array - Wikipedia Wikipedia (CC BY-SA 4.0)
- Run-length encoding - Wikipedia Wikipedia (CC BY-SA 4.0)
- Move-to-front transform - Wikipedia Wikipedia (CC BY-SA 4.0)
- Bzip2 - Wikipedia Wikipedia (CC BY-SA 4.0)
- Lexicographic order - Wikipedia Wikipedia (CC BY-SA 4.0)
- Circular shift - Wikipedia Wikipedia (CC BY-SA 4.0)
- Fine and Wilf's theorem - Wikipedia Wikipedia (CC BY-SA 4.0)
- Sorting algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
- On Bijective Variants of the Burrows-Wheeler Transform arXiv, Manfred Kufleitner (arXiv non-exclusive distribution licence)
- Web Workers API - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
- Intl.NumberFormat - JavaScript | MDN MDN Web Docs (CC BY-SA 2.5 or later)
- itertools - Functions creating iterators for efficient looping - Python 3.13 documentation Python Software Foundation (PSF License Version 2)