Inverse Burrows-Wheeler transform: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Match the rank of each final-column character to its occurrence in the sorted first column, then follow LF links backward.

For each final-column character, count smaller characters and earlier equal occurrences to obtain its stable first-column position. Follow these LF links from the primary row, filling the original text backward.

Open the 3D visualization

Inverse 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 Inverse Burrows-Wheeler transform

Reversing the sentinel-based BWT without materializing the entire rotation matrix.

Choosing an alternative

The forward view sorts explicit rotations. This inverse constructs LF ranks in O(n^2) time and reconstructs the block in O(n) time.

Worked example: input and state changes

Example input

annb$aa | 4

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: Final column, sorted first column, LF ranks, and reconstructed text.

    State at this checkpoint
    {
      "values": [
        "a",
        "n",
        "n",
        "b",
        "$",
        "a",
        "a",
        "$",
        "a",
        "a",
        "a",
        "b",
        "n",
        "n",
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        -1,
        "",
        "",
        "",
        "",
        "",
        "",
        ""
      ],
      "active": [],
      "kind": "matrix",
      "columns": 7,
      "result": 0,
      "output": []
    }
  2. Step 4: Map character b occurrence 0 to first-column row 4.

    State at this checkpoint
    {
      "values": [
        "a",
        "n",
        "n",
        "b",
        "$",
        "a",
        "a",
        "$",
        "a",
        "a",
        "a",
        "b",
        "n",
        "n",
        1,
        5,
        6,
        4,
        -1,
        -1,
        -1,
        "",
        "",
        "",
        "",
        "",
        "",
        ""
      ],
      "active": [
        3,
        17
      ],
      "kind": "matrix",
      "columns": 7,
      "result": 0,
      "output": []
    }
  3. Step 8: Recover position 6 and follow LF.

    State at this checkpoint
    {
      "values": [
        "a",
        "n",
        "n",
        "b",
        "$",
        "a",
        "a",
        "$",
        "a",
        "a",
        "a",
        "b",
        "n",
        "n",
        1,
        5,
        6,
        4,
        0,
        2,
        3,
        "",
        "",
        "",
        "",
        "",
        "",
        "$"
      ],
      "active": [
        4,
        18,
        27
      ],
      "kind": "matrix",
      "columns": 7,
      "result": 0,
      "output": []
    }
  4. Step 11: Recover position 3 and follow LF.

    State at this checkpoint
    {
      "values": [
        "a",
        "n",
        "n",
        "b",
        "$",
        "a",
        "a",
        "$",
        "a",
        "a",
        "a",
        "b",
        "n",
        "n",
        1,
        5,
        6,
        4,
        0,
        2,
        3,
        "",
        "",
        "",
        "a",
        "n",
        "a",
        "$"
      ],
      "active": [
        5,
        19,
        24
      ],
      "kind": "matrix",
      "columns": 7,
      "result": 0,
      "output": []
    }
  5. Step 15: Reconstructed banana$.

    State at this checkpoint
    {
      "values": [
        "a",
        "n",
        "n",
        "b",
        "$",
        "a",
        "a",
        "$",
        "a",
        "a",
        "a",
        "b",
        "n",
        "n",
        1,
        5,
        6,
        4,
        0,
        2,
        3,
        "b",
        "a",
        "n",
        "a",
        "n",
        "a",
        "$"
      ],
      "active": [],
      "kind": "matrix",
      "columns": 7,
      "result": 7,
      "output": [
        98,
        97,
        110,
        97,
        110,
        97,
        36
      ]
    }

Expected final state

Reconstructed banana$.

Complexity and input bounds

Family: Strings. Time complexity: O(n^2) rank construction; O(n) reconstruction.

Implementation detail: Four matrix rows show last column, sorted first column, LF mapping and reconstructed text. Downloads support an empty block, return -1 on invalid input and decoded length on success. Output is unspecified on an error.

Space complexity: O(n) auxiliary ranks, visited flags and output, plus saved animation frames.

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.

Final column: 1..12 lowercase letters/$ with one $ | original row (zero based). Invalid LF cycles are rejected.

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

Equal characters must retain occurrence order. The primary row must point to the unique final-column dollar sign. Reject a cycle that revisits a row before visiting all rows.

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
 9
10
11
12
// Last column n 0..12, ASCII lowercase codes plus exactly one $ (36), original-row primary. Returns decoded length n or -1 for invalid alphabet, primary, sentinel count or LF cycle. Empty column accepts primary 0. Writes n codes; output is unspecified on error. Output capacity at least n. Reconstructs by stable occurrence-rank LF mapping, O(n^2) construction and O(n) reconstruction, O(n) scratch. Only the terminal-sentinel BWT convention is supported. 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(last, n, primary, output) {
    if (n == 0) { if (primary == 0) { return 0; } return -1; }
    if (n < 0 || n > 12 || primary < 0 || primary >= n) { return -1; }
    let dollars = 0; let before = 0; let rank = 0; let row = primary; let lf = Array(256).fill(0); let seen = Array(256).fill(0);
    for (let i = 0; i < n; i++) { if (last[i] == 36) { dollars++; } else { if (last[i] < 97 || last[i] > 122) { return -1; } } }
    if (dollars != 1 || last[primary] != 36) { return -1; }
    for (let i = 0; i < n; i++) { before = 0; rank = 0; for (let j = 0; j < n; j++) { if (last[j] < last[i]) { before++; } if (j < i && last[j] == last[i]) { rank++; } } lf[i] = before+rank; }
    for (let i = n-1; i >= 0; i--) { if (seen[row] != 0) { return -1; } seen[row] = 1; output[i] = last[row]; row = lf[row]; }
    if (row != primary || output[n-1] != 36) { return -1; }
    return n;
}

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.