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.
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.
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": [] }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": [] }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": [] }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": [] }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- A Block-sorting Lossless Data Compression Algorithm
Michael Burrows; David J. Wheeler (1994). Original research report SRC 124.