Burrows-Wheeler transform: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Sort cyclic rotations and extract their final column. A unique terminal dollar sign makes the original row unambiguous. The transform itself is not compression.

List cyclic rotations, sort them lexicographically, and extract the last column. Record the row containing the original input. Similar contexts group characters together without removing any information.

Open the 3D visualization

Burrows-Wheeler transform example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Burrows-Wheeler transform

Understanding the reversible block-sorting stage used before entropy coding in compression pipelines.

Choosing an alternative

BWT preserves length and is not a compressor by itself. The inverse uses occurrence ranks rather than storing every rotation.

Worked example: input and state changes

Example input

banana$

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Build all cyclic rotations.

    State at this checkpoint
    {
      "values": [
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a"
      ],
      "active": [],
      "kind": "matrix",
      "columns": 7,
      "result": 0,
      "output": []
    }
  2. Step 2: Insert rotation 2 in lexicographic order.

    State at this checkpoint
    {
      "values": [
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a"
      ],
      "active": [
        14,
        15,
        16,
        17,
        18,
        19,
        20
      ],
      "kind": "matrix",
      "columns": 7,
      "result": 0,
      "output": []
    }
  3. Step 4: Insert rotation 4 in lexicographic order.

    State at this checkpoint
    {
      "values": [
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a"
      ],
      "active": [
        21,
        22,
        23,
        24,
        25,
        26,
        27
      ],
      "kind": "matrix",
      "columns": 7,
      "result": 0,
      "output": []
    }
  4. Step 5: Insert rotation 5 in lexicographic order.

    State at this checkpoint
    {
      "values": [
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a"
      ],
      "active": [
        0,
        1,
        2,
        3,
        4,
        5,
        6
      ],
      "kind": "matrix",
      "columns": 7,
      "result": 0,
      "output": []
    }
  5. Step 7: Last column annb$aa; original row 4.

    State at this checkpoint
    {
      "values": [
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "n",
        "a",
        "$",
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$",
        "b",
        "a"
      ],
      "active": [
        6,
        13,
        20,
        27,
        34,
        41,
        48
      ],
      "kind": "matrix",
      "columns": 7,
      "result": 4,
      "output": [
        97,
        110,
        110,
        98,
        36,
        97,
        97
      ]
    }

Expected final state

Last column annb$aa; original row 4.

Complexity and input bounds

Family: Strings. Time complexity: O(n^3) bounded rotation insertion sort.

Implementation detail: The WebGL matrix shows all rotations and each insertion into sorted order. Inputs have at most twelve symbols including $. The portable teaching implementation uses direct O(n^3) rotation insertion sort, not a production suffix-array constructor.

Space complexity: O(n) rotation offsets in portable downloads; Python sorting keys and displayed rotation matrices use O(n^2). Recorded frames use additional space.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..11 lowercase letters followed by a single $; $ alone is also valid.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Keep the primary row and use the same alphabet order. The playground requires exactly one dollar sentinel at the end, with lowercase letters before it.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
1
2
3
4
5
6
7
8
// Input n 0..12, ASCII lowercase codes 97..122 followed by one terminal $ (36); n=0 is supported and returns 0 without output. Writes n last-column codes and returns the zero-based original row. Output capacity at least n. Portable versions explicitly insertion-sort cyclic rotations, O(n^3) worst case, O(n) scratch space; Python uses built-in sorting of rotation keys. This is the reversible transform stage, not a compressor. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(text, n, output) {
    let order = Array(256).fill(0); let key = 0; let j = 0; let k = 0; let left = 0; let right = 0; let greater = 0; let primary = 0;
    for (let i = 0; i < n; i++) { order[i] = i; }
    for (let i = 1; i < n; i++) { key = order[i]; j = i-1; while (j >= 0) { k = 0; greater = 0; while (k < n) { left = text[(order[j]+k)%n]; right = text[(key+k)%n]; if (left != right) { if (left > right) { greater = 1; } break; } k++; } if (greater == 0) { break; } order[j+1] = order[j]; j--; } order[j+1] = key; }
    for (let i = 0; i < n; i++) { output[i] = text[(order[i]+n-1)%n]; if (order[i] == 0) { primary = i; } }
    return primary;
}

Source

Original block-sorting research report. These views demonstrate only the reversible transform and inverse under a terminal-sentinel convention, not the complete compression pipeline described in the report.