GenerateRandomSearch

Burrows-Wheeler Transform Tool

The Burrows-Wheeler transform looks like it must destroy information. It sorts every rotation of your text and keeps only the last column — and yet the original can be reconstructed exactly, from that column and a single row number. It compresses nothing by itself; what it does is cluster identical characters together, which is what makes the coder that follows it so effective. This shows the sorted rotations, the transform, and the round trip that proves nothing was lost.

What this generator does

Sorts every rotation of your text and takes the last column, recording which row held the original. For inputs up to 24 characters it shows the full sorted rotation table so the transform can be read off directly. It then decodes the result and compares it against your input character by character before displaying anything.

How to use this tool

  1. Type or paste some text — repeated words show the effect best.
  2. Read the transform and the row number that identifies your original.
  3. Look at the sorted rotations table for short inputs to see where the last column comes from.
  4. Compare the longest run of one character before and after.

Understanding the controls

Your text
Between 4 and 200 characters. Text with repeated words demonstrates the clustering effect far better than random characters.

Common use cases

  • Understanding the step at the heart of bzip2 compression
  • Teaching an invertible transform whose invertibility is genuinely surprising
  • Producing worked examples with the rotations table visible
  • Checking a Burrows-Wheeler implementation against known output
  • Showing why clustering characters helps the coder that comes next

How this generator works

Decoding is the interesting half. The first column of the rotation matrix is just the last column sorted, and pairing each character with its occurrence number gives an exact correspondence between the two columns. Following that mapping from the recorded row rebuilds the original one character at a time. The check confirms three things: the round trip is exact, the length is unchanged, and the output is a permutation of the input.

Randomness and fairness

No randomness at all. The transform is fully determined by the text you enter, so the same input always produces the same output.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

  • Up to 200 characters, which keeps the rotation sort instant in a browser.
  • The rotation table is only shown for inputs of 24 characters or fewer, above which it stops being readable.
  • This is the transform alone — it is not a compressor, and the output is exactly as long as the input.
  • No end-of-string sentinel is used; the row index serves that purpose instead.

Privacy and your data

Your text is transformed entirely in your browser and never sent anywhere. Analytics records only that the tool ran and how many characters were involved, never the text itself.

Related generators