The transform that emits nothing

Every algorithm in this field so far has produced bits. This one produces characters — the same characters it was handed, rearranged — and it is the most effective single step in the phase.

What it does #

Write out every rotation of the text — for a text of $n$ characters, $n$ rotations, each $n$ long. Sort them. Take the last column.

For the-order-is-the-message that gives ereessrghhdmatt---eoise-◇, where ◇ is the end-of-text sentinel.

That is the whole transform. There is no arithmetic in it, nothing is compressed, and the output is a permutation of the input: the same multiset of characters in a different order.

Worked, on six characters #

banana with a sentinel # that sorts below every letter. The seven rotations, sorted:

0   #banana
1   a#banan
2   ana#ban
3   anana#b
4   banana#
5   na#bana
6   nana#ba

The last column, read downwards, is annb#aa.

Both ns have come together, and both are there because both are followed by a — rows 2 and 3 begin ana and anana, so they sort adjacently, and each carries its own preceding n at the end. The three as in rows 4, 5 and 6 are the same effect: everything preceded by a sorted into a block.

Six characters is too short for the effect to pay for anything, and it is long enough to show that the mechanism is a sort rather than a statistic.

Which means its entropy is unchanged, exactly #

The first thing to be careful about is the thing the figure asserts before it draws anything.

The zeroth-order entropy of a sequence is computed from its symbol frequencies. A permutation does not change symbol frequencies. So the entropy of the transform’s output is exactly the entropy of its input, and the gate holds the two to within $10^{-9}$ — on an 8,192-character text both are 3.898 bits per symbol.

By every measure this site had before, nothing happened.

A check that compared the wrong pair here would pass a transform that did nothing at all, which is why the assertion behind it compares the raw entropies for equality and then compares the move-to-front entropies for a fall. Getting that pair wrong is the natural mistake, and it would produce a figure showing an impressive drop that any permutation whatsoever would produce.

What did happen #

Sorting the rotations sorts each character by what follows it. The rotation beginning at position $i$ starts with the text from $i$ onwards, and ends with the character at $i-1$. So the last column holds, for each context in sorted order, the character that preceded it.

In English text the context the is preceded by a space almost every time. The context he is preceded by t almost every time. So the last column contains long runs of the same character, not because the text has runs but because the contexts were sorted and each context has a characteristic predecessor.

Measured on 8,192 characters of the site’s text source:

• Mean run length before: 1.01. After: 3.38.
• On an order-1 Markov stream: 1.02 becomes 3.93.
• On a stream that is one seventeen-character block repeated: 1.21 becomes 431.21.

That last number is the transform doing what it is for. A periodic stream has exactly seventeen distinct contexts, each with exactly one predecessor, so the sorted rotations group into seventeen enormous blocks of identical characters.

Turning runs into something a coder can use #

A run of identical characters is not, by itself, cheaper to code. A zeroth-order coder looks at each symbol independently and does not know or care that the previous one was the same.

Move-to-front converts local repetition into small numbers. Keep the alphabet as a list; to code a symbol, emit its current position in the list and then move it to the front. A run of one character emits its position once and then a string of zeroes. A character that has been seen recently emits a small index. One that has not emits a large one.

The output is a sequence of integers whose distribution is heavily skewed toward zero — and a skewed distribution is precisely what a zeroth-order coder is good at, which is the whole pipeline in one sentence.

On banana’s transform annb#aa that gives 1, 3, 0, 3, 3, 3, 0. On the untransformed banana# it gives 2, 2, 3, 1, 1, 1, 3. The first has three zeroes and the second has none, on seven characters.

At scale the difference is stark. Move-to-front on 8,192 characters of text produces zeroes at 1.3% of positions. The same pass after the transform produces them at 70.4%, and the mean run of the index sequence is 3.30.

Measured on the same 8,192 characters:

And the coder that actually runs on it, a Huffman coder over the move-to-front output: 4.209 bits per symbol before, 1.935 after.

Notice the first row. Move-to-front on untransformed text is worse than the text’s own entropy of 3.898 — 4.156 rather than 3.898 — because scrambling a stream into indices without first clustering it adds noise and removes nothing. The two steps only work together, and either one alone makes the file bigger.

The floor that moved, and the one that did not #

This is the third answer in the field to the same question, and it is the strangest of the three.

The context model of the model is the compressor lowers the floor by conditioning: it builds $\sigma^k$ tables and pays for them. The dictionary coder of the dictionary that builds itself lowers it by referring backwards: it pays $\log_2 w$ bits per token. Both change the model and leave the data alone.

The transform changes the data and leaves the model alone. It hands a plain zeroth-order coder — the weakest model in the field — a stream that a plain zeroth-order coder can compress well, and it does so by putting the stream’s order-$k$ structure into a form that order-0 statistics can see.

That is the sense in which it is a sorting result rather than a coding one. The information was always there; it was distributed across the stream in a way that a symbol-frequency count integrates away, and sorting the contexts gathers it into one place.

And the transform has no order parameter. A context model must be told $k$, and the previous essay showed how badly that choice can go — too shallow and it finds nothing, too deep and the estimate collapses. The transform is conditioned on every context length at once, because the sort is over whole rotations, and it needs no parameter and no table.

The step between, which is where the runs are actually spent #

bzip2 puts one more stage between move-to-front and the entropy coder, and it is the one the numbers above quietly leave on the table.

After the transform and move-to-front, 70.4% of the output is zero. A zeroth-order coder gives zero a code of one bit — it cannot give it less, for exactly the reason the optimal code that is beaten sets out — and a symbol occurring 70.4% of the time is worth 0.506 bits. So a Huffman coder over this stream is overcharging on seven symbols in ten.

Run-length encoding the zeroes fixes it, and it is the same escape as blocking: replacing a run of $k$ zeroes with a single token costs one code word instead of $k$, which is a whole number of bits spread over $k$ symbols rather than one bit each. bzip2 uses a two-symbol run-length code for exactly this and it is worth several per cent.

The pipeline measured here is the transform, move-to-front and a Huffman coder over the result, and it stops there. The run-length stage is stated as absent rather than omitted quietly, because the 1.935 bits per symbol on this page is a number for a three-stage pipeline and bzip2 is a four-stage one.

The inverse is the proof #

A permutation is only useful if it can be undone, and undoing this one is not obvious. The output is a single column; the sorted rotation matrix that produced it was never stored, and storing it would cost $n^2$.

It can be undone, from the last column and one integer, and the mechanism is worth stating because it is the reason the transform exists rather than being a curiosity.

The first column of the sorted matrix is the last column sorted — the same multiset, in order. So both columns are available from the output alone. And each row of the matrix is a rotation, so the character in the last column immediately precedes the character in the first column of the same row.

That gives a mapping from each position in the last column to the row where that character appears in the first, and following it backwards reconstructs the text one character at a time. inverseBwt in The inverse implemented here does exactly this, in linear time, with one counting pass.

Every figure in this essay is drawn only after the inverse has been checked. assertEveryCoderRoundTrips transforms a stream, inverts it, and requires the result to equal the input character for character, because a transform that does not invert is a lossy compressor and nobody said so.

The sentinel, and a mistake worth recording #

The transform needs a character that terminates the text and sorts below everything else, so that the rotation starting at position 0 is identifiable. The implementation uses a NUL byte, and checks that the input does not already contain one — a sentinel that collides silently produces a transform that does not invert, and the inverse is what proves the transform.

The first version of this file wrote that sentinel as a literal NUL in the source. It was the correct character and the file was correct, and it was also no longer a text file: grep, file and every editor treated the source as binary, the comparison in bwt was against a character nobody could see, and the entropy of the sentinel-terminated stream came out fractionally different from the entropy of the stream, which is how it was found — an assertion demanding two entropies be equal to $10^{-9}$ failed by 0.0015.

It is written as an escape now, with the reason in a docstring above the constant, and the incident is here because it is the kind of defect that survives every gate a site has. Nothing about the built output was wrong. The source had simply stopped being readable by the tools that read source.

The block size, which is the parameter it does have #

The transform is described above as having no order parameter, and that is true and is not the same as having no parameter.

Sorting every rotation of a text costs a sort over $n$ strings, and the inverse needs the whole block in hand. Neither is affordable on a stream of arbitrary length, so every implementation cuts the input into blocks and transforms each independently. bzip2’s digit flag is exactly that dial — a hundred kilobytes at its lowest setting and nine hundred at its highest — and it is the parameter the transform was said not to have, wearing different clothes.

What it decides is which repetitions the transform can see. Sorting rotations gathers a context with its predecessors only if those occurrences are in the same block, so a phrase recurring half a megabyte later is, at the smallest setting, in a different sort entirely and contributes nothing. The transform is conditioned on every context length at once and on no distance beyond the block, which is the honest statement and is the same shape of limit an entropy that cannot see a copy has, arriving from a completely different direction.

That gives the dial its whole character. On a document whose repetitions are local — ordinary prose, where the useful contexts are a few characters long — the block size barely matters past a certain point, because the contexts being gathered recur constantly. On a collection of near-identical documents it matters enormously, because the repetitions are exactly the ones that span the whole input, and a block boundary between two copies of a passage hides the fact that they are copies.

Three costs move with it and they do not move together. Compression improves, with diminishing returns that depend on the data. Memory rises linearly, on both sides — the decompressor needs a block’s worth too, which is why the setting is recorded in the file. And the sort’s cost rises faster than linearly, which is where the slowness the last section attributes to the block sort actually lives.

There is one gain from small blocks that has nothing to do with any of that: independent blocks can be compressed and decompressed in parallel, and a format built on a single enormous block cannot be. That is a real reason to choose a smaller setting than the ratio alone would justify, and it is a property of the format rather than of the transform.

What move-to-front throws away #

One more thing is named rather than measured, because the pipeline here stops before it.

Move-to-front replaces each symbol by its recency rank, and a rank is not a symbol. After the pass, the coder sees a stream of small integers and can no longer tell which character produced any of them — so it cannot exploit anything about which symbols are involved, only about how recently they were seen. A run of t and a run of e produce the same sequence of zeroes.

That is a real loss and it is deliberate: the whole point is to convert an ordering property into a frequency property that a zeroth-order coder can price. But it means the pipeline discards structure the transform had just gathered, one stage after gathering it.

The compressors that do best on transformed data skip the pass entirely and code the transform’s output directly under a model conditioned on the recent symbols — which keeps the identities and prices the runs at the same time. They are a few per cent better than the three-stage pipeline measured here and they are not built in this collection, so the number on this page is a number for the pipeline described and not for the best known use of the transform.

Where this actually ships #

bzip2 is this pipeline: block sort, move-to-front, run-length encode, Huffman. It compresses better than gzip on text by 10–15% and is slower in both directions, and the slower part is the block sort, which is the suffix-array construction of the index that is the text under another name.

That is the connection this phase was built to make. The text index and the compressor are the same object read two ways. Sorting all the suffixes of a text gives a structure that answers substring queries; sorting all the rotations — which differs only in wrapping — gives a permutation whose zeroth-order statistics carry the text’s higher-order structure. One sort, two entirely different uses, and the algorithm that makes both practical is the same one.

Three more rotations, sorted #

The construction is a definition and the picture is the definition performed, so it costs nothing to perform it on the words every account of this transform uses.

And the standard worked example is worth drawing last, because its runs are long enough that the whole argument can be read off the last column without measuring anything.

The FM-index, in one paragraph #

The mapping that inverts the transform — from a position in the last column to the corresponding position in the first — is called the LF mapping, and it does something the inverse does not need.

Applied to a pattern rather than to the text, it walks backwards through the pattern’s characters and narrows a range of the suffix array at each step, without the suffix array being present. So a structure holding the transform’s output plus a few rank tables answers exactly the queries the index that is the text answers, in space proportional to the compressed text rather than to $4n$ bytes on top of it.

That is the FM-index, and it is why the transform’s afterlife is in indexing rather than in compression. A structure that is simultaneously the compressed file and the search index is a strange object, and it is what makes it possible to align short reads against a three-billion-base genome on a laptop.

It is also why bzip2 lost. Zstandard reaches similar ratios at a fraction of the cost by pairing a dictionary coder with a fast entropy coder, and the block sort’s $O(n \log n)$ with a large constant is exactly the wrong shape for a compressor that has to run on every HTTP response. The transform is not obsolete — it is the core of the FM-index, which is how genome aligners search billions of bases in compressed space — but it moved from compression into indexing, which given where it came from is a return rather than a departure.

What the field has, now that it is finished #

Two halves that turned out to be one.

The string half asks how few characters a search can examine, and its answers run from the naive scan’s 520,256 down to Horspool’s 2,985 and then to an index that answers in 91. The compression half asks how few bits a stream needs, and its answers run from 3.937 down to 2.113 and then to 1.935 by a route that spends no bits at all.

The object underneath both is the same: a text repeats, and every algorithm in the field is a different way of finding where. KMP finds where the pattern repeats inside itself. Horspool finds where it cannot possibly. The suffix array finds every repeat at once. The context model, the dictionary and the transform each price the repeats they find, and the three prices differ because the three notions of “where” differ.

That is a field rather than a list, and it is the test the phase set for itself before any of it was written.