Burrows–Wheeler Transform

Cyclic Rotations and Context Clustering

Appending a unique end-of-block sentinel character $ ordered strictly before A guarantees that all N + 1 cyclic rotations of an N-character string are distinct. Sorting these rotations groups identical right-hand contexts together, causing their immediately preceding characters (located in the last column L) to form homogeneous runs suitable for downstream move-to-front and entropy coding.

Stable Occurrence Ranks and LF Mapping

In the sorted rotation matrix, the first column F contains all characters of L in sorted order. Because cyclic shifting by one position preserves the relative sorted order of identical characters, the k-th occurrence of symbol c in column L corresponds to the exact same text position as the k-th occurrence of symbol c in column F. This bijection defines the Last-to-First link LF(i), allowing the original string to be reconstructed right-to-left starting from row 0 (where F[0] = $).

Worked Example

Let us trace the Burrows–Wheeler Transform for the default input ABACABA:

1. Append the sentinel $ to obtain ABACABA$ of length 8.
2. Form all 8 cyclic rotations and sort them with $ < A < B < C:

   Row 0: $ABACABA (L = A)\n Row 1: A$ABACAB (L = B)\n Row 2: ABA$ABAC (L = C)\n Row 3: ABACABA(L =) -- Primary row 3\n Row 4: ACABA$AB (L = B)\n Row 5: BA$ABACA (L = A)\n Row 6: BACABA$A (L = A)\n Row 7: CABA$ABA (L = A)

3. Reading column L from top to bottom yields ABC$BAAA, and the unshifted rotation ABACABA$ sits at 0-based Primary row 3.
4. Following LF(i) backward from row 0 reconstructs ABACABA.

Experiment

Explore cyclic sorting and LF links interactively in https://riano.app/module/burrows-wheeler-transform:

1. Enter ABACABA in Text and verify that BWT last column is ABC$BAAA and Primary row is 3.
2. Step through LF row values 0, 1, 2, 3 to see each row highlight alongside its mapped predecessor row LF(i).
3. Set Text to BABABA to see how alternating characters rearrange into clustered runs ABBBAA$.

Limitations

The BWT itself is a length-preserving permutation rather than a compressor: without subsequent Move-to-Front (MTF) and run-length/entropy coding stages, the output occupies the same number of symbols plus the primary row index. This module limits inputs to 0..10 uppercase characters in A..C so the complete rotation matrix can be inspected directly.

Common Pitfalls

Breaking ties between equal characters in column L arbitrarily instead of preserving their top-to-bottom appearance rank destroys the LF bijection and corrupts the inverse transform.

References

The cyclic suffix sorting and LF-mapping specification used in this module follow standard algorithm references:

• Princeton University Algorithms, Part II: Burrows–Wheeler Data Compression Specification