Burrows–Wheeler transform

For an N-character block, conceptually sort its N cyclic rotations and take their last column L. Also retain I, the row containing the original block. The matrix explains the transformation without requiring N-squared character storage.

The report transforms abraca into caraab with original-row index1, numbered from zero. This version returns (L,I), not L alone. Sentinel-based conventions need their own symbol and reconstruction rules.

References: [1]

Sorting L gives the first column F because both are permutations of the block. Pairing successive occurrences of each character in the two columns builds predecessor links; following them from I reconstructs the original.

The correspondence follows sorted rotations, not a guess from frequency counts. Frequencies alone cannot recover original order; the ordered last column and row information carry the necessary structure.

References: [1]

Sorting brings rotations with similar following contexts together, potentially clustering predecessor characters in L. The report applies move-to-front and statistical coding afterward; savings belong to that complete pipeline.

Block boundaries, the row index and coding metadata count toward output size. Larger blocks can also increase sorting, memory and latency. Evaluation must cover the representation and implementation rather than only a visually repetitive last column.

References: [1]