Transform coding: invert every state transition

A reversible transform can rearrange a message into a form that a later coder models better. BWT preserves the byte histogram exactly. It does not guarantee long runs on every input, and its primary index adds information to the serialized representation.

Construct a small BWT by hand

For BANANA, sort the cyclic rotations lexicographically by bytes:

Sorted row	Start offset	Rotation	Last byte
0	5	ABANAN	N
1	3	ANABAN	N
2	1	ANANAB	B
3	0	BANANA	A
4	4	NABANA	A
5	2	NANABA	A

The last column is NNBAAA; the original row is 3, so output is (NNBAAA,3). No sentinel byte is added in this exercise. All 256 byte values remain usable as data. A different primary row selects a rotation, so the last column alone is insufficient.

The exercise permits naive rotation comparison at n<=512. Comparing two rows can inspect n bytes; sorting n row offsets therefore takes O(n² log n) worst-case time with O(n) auxiliary offsets. Materializing every rotation instead takes O(n²) storage. Equal rotations of periodic input need not have a unique row identity; any row containing the original byte sequence reconstructs it. Empty input has last column empty and primary=0.

Invert with stable occurrence ranks

The first column F is L's bytes sorted. Match the first occurrence of each byte in L to the first occurrence in F, the second to the second, and so on. Define:

occ[i]   = number of L[i] bytes strictly before position i
start[b] = number of bytes strictly smaller than b
LF[i]    = start[L[i]] + occ[i]

For L=NNBAAA, F=AAABNN, occurrence ranks are [0,1,0,0,1,2], starts are A=0, B=3, N=4, and LF=[4,5,3,0,1,2]. Set row=primary. For output positions n-1 down to 0, write L[row], then row=LF[row].

Starting at row 3 gives row sequence 3,0,4,1,5,2, letters A,N,A,N,A,B written backward, and therefore BANANA. Matching occurrences stably is essential: matching only equal byte values would leave the repeated A and N edges ambiguous. Build counts and starts in O(n+256); inversion then takes O(n), with O(n+256) auxiliary storage.

MTF turns repetitions into ranks

The exercise initializes a list containing bytes 0..255. For each byte, emit its current index and move it to the front, preserving the order of all other bytes. The decoder retrieves that same index and makes the same move.

Apply MTF to NNBAAA (ASCII N=78, B=66, A=65):

Byte	Rank before move	List prefix afterward
N	78	N,0,1,...
N	0	N,0,1,...
B	67	B,N,0,1,...
A	67	A,B,N,0,1,...
A	0	A,B,N,0,1,...
A	0	A,B,N,0,1,...

The ranks are [78,0,67,67,0,0]. A frequent byte is not automatically rank zero: zero means it is the current front element, which occurs immediately after an identical byte. An array implementation searches/shifts at most 256 entries per byte, so O(256n) work is O(n) for this fixed alphabet.

Zero-run coding and the exact pipeline boundary

Replace each maximal run of k zeros with -k, leaving positive indices unchanged. The previous ranks become [78,-1,67,67,-2]. Decode in reverse order: expand negatives, then invert MTF. A negative integer is a run marker, not a byte or an MTF index. This representation is reversible because original MTF indices are nonnegative.

The named PipelineEncode exercise performs MTF then RLE only. BWT is a separate exercise returning its own primary index. To combine all three, the caller must keep that index and invert RLE, MTF, then BWT. Neither an integer slice nor a transform alone is a complete compressed byte format: an integer coder and framing still have to be selected.

Reconstruct it

1. With toy MTF list [A,B,C], encode CACA.
2. RLE-encode [0,0,4,0,5,0,0,0].
3. Does BWT lower zero-order byte entropy?

Model answers

1. Ranks [2,1,1,1]; after the first two moves the list alternates between [C,A,B] and [A,C,B].
2. [-2,4,-1,5,-3].
3. No: counts are unchanged. It rearranges context so later stages can use locality more effectively.

See Burrows and Wheeler's original report for the block-sorting construction. The byte-alphabet, no-sentinel, and integer-run conventions here follow this pack's interfaces.