Why does taking the last column of a string's lexicographically sorted rotations cluster repeated characters together?

seniornice to knowfreq 28%

answer

sort by what comes after
last column holds the preceding character
same context, same predecessor
reversible with a row index or terminator
block-sized sort, never streaming

basics

~20 s

Each rotation's last character is the one that cyclically precedes its first, so sorting rotations groups them by the text that follows. Characters sharing a following context therefore land next to each other in that last column.

solid answer

~40 s

Write out every rotation of the string, sort them lexicographically, and read down the final character of each. Because a rotation's last character is the one immediately before its first character in the original string, sorting by the rotation — that is, by what follows — brings together the characters that precede similar text. Take banana$, with $ sorting first: the seven sorted rotations end in a, n, n, b, $, a, a, so the transform's output is annb$aa. The ns cluster because in this string almost every a is preceded by an n. The result is a permutation of the input, exactly the same length, with equal symbols pulled into runs. It is fully reversible given the index of the original row, or a unique terminator that identifies it.

Write out every rotation of the string, sort them lexicographically, and read down the final character of each. Because a rotation's last character is the one immediately **before** its first character in the original string, sorting by the rotation — that is, by what follows — brings together the characters that precede similar text. Take `banana$`, with `$` sorting first: the seven sorted rotations end in `a, n, n, b, $, a, a`, so the transform's output is `annb$aa`. The `n`s cluster because in this string almost every `a` is preceded by an `n`. The result is a permutation of the input, exactly the same length, with equal symbols pulled into runs. It is fully reversible given the index of the original row, or a unique terminator that identifies it.

code

pseudocode · 9 lines

pseudocode

rotations = empty list
for i = 0 to length(s) - 1:
    rotations.append(rotate_left(s, i))
sort(rotations)              # lexicographic; terminator sorts first

last_column = empty string
for each r in rotations:
    last_column = last_column + r[length(s) - 1]
emit(last_column)

go deeper

for a junior

Recall the shape only: rotate a block every possible way, sort those rotations, and keep the last character of each. The result is the same length as the input and can be turned back into it.

for a middle

Explain why the last character of a rotation is the one preceding its first, and therefore why sorting by following context pulls equal predecessors together into runs.

for a senior

Show the operating consequences: a whole block must be buffered before anything is emitted, memory and latency scale with block size, and the inverse requires the original row index or a unique terminator.

for a principal

Frame block size as the real decision. It sets how far contextual redundancy can reach, and trades compression against memory footprint and first-byte latency in a streaming system.

The construction

The Burrows-Wheeler transform of a block is built in three steps:

Form every cyclic rotation of the block — for a block of length n there are n of them.
Sort the rotations lexicographically.
Emit the last character of each sorted rotation, read top to bottom.

The output has exactly n characters and is a permutation of the input. Nothing has been removed.

Worked on a short word

Take banana$, appending a terminator that sorts before every letter. The seven rotations, sorted, with their first character (F) and last (L):

Sorted rotation	F	L
`$banana`	`$`	`a`
`a$banan`	`a`	`n`
`ana$ban`	`a`	`n`
`anana$b`	`a`	`b`
`banana$`	`b`	`$`
`na$bana`	`n`	`a`
`nana$ba`	`n`	`a`

Reading L down the table gives annb$aa. The input had its two ns apart and its three as apart; the output has nn adjacent and aa adjacent. Note also what column F is: the input's characters in sorted order, $aaabnn. F and L are the two columns worth keeping straight — the sorted characters and the transform's actual output.

Why clustering happens

In a cyclic rotation, the character at the end is the character that sits immediately before the one at the start. Sorting the rotations therefore orders them by the context that follows each of those characters. Rows whose text begins the same way sit together, and their last characters are the characters that preceded that same text.

So the clustering is a statement about the source, not a trick of the sort: where a language or a payload repeatedly puts the same character in front of the same context, those characters end up adjacent. In banana$, the rows beginning a are the contexts a$..., ana$..., anana$..., and two of the three are preceded by n, so nn appears. In prose, the rows beginning he are overwhelmingly preceded by t, and the output carries a long run of t.

What the inverse needs

The last column alone is not quite enough: many blocks share a last column, so the decoder must know which sorted row was the original string. Two equivalent devices are used:

append a unique terminator that occurs exactly once, so the original row is the one ending in it; or
store the row index of the original alongside the output.

Given that, the inverse is mechanical: the first column is just the last column sorted, and repeatedly stepping from a character in one column to its counterpart in the other walks the original string out backwards. Correctly implemented it is exact — the transform is lossless, not an approximation.

What it costs

It is block-based, not streaming. Every rotation must exist before any can be sorted, so the encoder buffers a whole block and emits nothing until it is done. That is latency the pipeline must budget for.
Memory scales with the block. A naive implementation materialising n rotations of length n is quadratic in space and is never used; practical implementations sort suffixes with the rotations represented implicitly.
Block size bounds the prize. Context redundancy that spans more than one block cannot be exploited, so larger blocks compress better and cost more memory and more latency — the central tuning knob of the whole scheme.

What comes next

Clustering on its own saves nothing; the output is the same length as the input. The clusters are fed to a move-to-front stage, which emits the position of each symbol in a list it keeps reordering, then promotes that symbol to the front. Starting from [$, a, b, n], the output annb$aa becomes the indices 1, 3, 0, 3, 3, 3, 0 — every repeat of the immediately preceding symbol emits a 0. On a long block, the runs the transform created turn into long stretches of zeros, and that heavily skewed stream is what the entropy coder at the end of the pipeline finally turns into fewer bits.

## The construction The Burrows-Wheeler transform of a block is built in three steps: 1. Form every **cyclic rotation** of the block — for a block of length n there are n of them. 2. **Sort** the rotations lexicographically. 3. Emit the **last character of each sorted rotation**, read top to bottom. The output has exactly n characters and is a permutation of the input. Nothing has been removed. ## Worked on a short word Take `banana$`, appending a terminator that sorts before every letter. The seven rotations, sorted, with their first character (F) and last (L): | Sorted rotation | F | L | |---|---|---| | `$banana` | `$` | `a` | | `a$banan` | `a` | `n` | | `ana$ban` | `a` | `n` | | `anana$b` | `a` | `b` | | `banana$` | `b` | `$` | | `na$bana` | `n` | `a` | | `nana$ba` | `n` | `a` | Reading L down the table gives **`annb$aa`**. The input had its two `n`s apart and its three `a`s apart; the output has `nn` adjacent and `aa` adjacent. Note also what column F is: the input's characters in sorted order, `$aaabnn`. F and L are the two columns worth keeping straight — the sorted characters and the transform's actual output. ## Why clustering happens In a cyclic rotation, the character at the end is the character that sits immediately before the one at the start. Sorting the rotations therefore orders them by **the context that follows** each of those characters. Rows whose text begins the same way sit together, and their last characters are the characters that preceded that same text. So the clustering is a statement about the source, not a trick of the sort: **where a language or a payload repeatedly puts the same character in front of the same context, those characters end up adjacent.** In `banana$`, the rows beginning `a` are the contexts `a$...`, `ana$...`, `anana$...`, and two of the three are preceded by `n`, so `nn` appears. In prose, the rows beginning `he ` are overwhelmingly preceded by `t`, and the output carries a long run of `t`. ## What the inverse needs The last column alone is not quite enough: many blocks share a last column, so the decoder must know **which sorted row was the original string**. Two equivalent devices are used: - append a **unique terminator** that occurs exactly once, so the original row is the one ending in it; or - store the **row index** of the original alongside the output. Given that, the inverse is mechanical: the first column is just the last column sorted, and repeatedly stepping from a character in one column to its counterpart in the other walks the original string out backwards. Correctly implemented it is exact — the transform is lossless, not an approximation. ## What it costs - **It is block-based, not streaming.** Every rotation must exist before any can be sorted, so the encoder buffers a whole block and emits nothing until it is done. That is latency the pipeline must budget for. - **Memory scales with the block.** A naive implementation materialising n rotations of length n is quadratic in space and is never used; practical implementations sort suffixes with the rotations represented implicitly. - **Block size bounds the prize.** Context redundancy that spans more than one block cannot be exploited, so larger blocks compress better and cost more memory and more latency — the central tuning knob of the whole scheme. ## What comes next Clustering on its own saves nothing; the output is the same length as the input. The clusters are fed to a **move-to-front** stage, which emits the position of each symbol in a list it keeps reordering, then promotes that symbol to the front. Starting from `[$, a, b, n]`, the output `annb$aa` becomes the indices `1, 3, 0, 3, 3, 3, 0` — every repeat of the immediately preceding symbol emits a `0`. On a long block, the runs the transform created turn into long stretches of zeros, and that heavily skewed stream is what the entropy coder at the end of the pipeline finally turns into fewer bits.

What does the inverse transform need beyond the last column itself?
It needs to know which sorted row was the original block — carried either as a stored row index or as a terminator that occurs exactly once. With that, the first column is the last column sorted, and stepping between the two columns reconstructs the block one character at a time, backwards.
How does move-to-front convert those clusters into something a coder likes?
It keeps a list of the alphabet, emits each symbol's position in it, then moves that symbol to the front. A symbol repeating the previous one emits 0. Starting from the list in sorted order, the output `annb$aa` becomes `1, 3, 0, 3, 3, 3, 0`, and on a long block the clusters become long stretches of zeros.
Why does the block size dominate this scheme's tuning?
Only redundancy within one block can be exploited, since rotations never cross a block boundary. Larger blocks reach further context and compress better, at the cost of memory proportional to the block and of latency, because nothing is emitted until the whole block has been sorted.
Why is a naive implementation that materialises every rotation never used?
Storing n rotations of length n costs space quadratic in the block size, which is prohibitive at any useful block. Practical implementations sort suffixes of the block with the rotations represented implicitly by their starting offsets, comparing characters on demand rather than copying whole strings.

Write one index card per position, each card carrying the text that follows that position on its face and the single character just before it on its back. File the cards alphabetically by their faces, then read only the backs: characters that guarded the same context now sit in a stack together.

saying these in an interview costs you the question

Thinks the transform sorts the characters themselves into the output.
Says the transform is lossy because it reorders the block.
Forgets the inverse needs the original row index or a unique terminator.
Believes it can run as a streaming filter without buffering a block.
Claims the output is smaller than the input it consumed.
Assumes it helps regardless of whether contexts repeat in the data.

Why does taking the last column of a string's lexicographically sorted rotations cluster repeated characters together?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

The construction

Worked on a short word

Why clustering happens

What the inverse needs

What it costs

What comes next

▾common follow-ups4 questions

▾analogy~20 s

▾red flags6 flags

The construction

Worked on a short word

Why clustering happens

What the inverse needs

What it costs

What comes next

answer

go deeper