The order inside a tie

What a reordering costs to undo set two permutations side by side and priced them in full. Sorting a text’s characters clusters them perfectly and costs the text’s whole floor to undo. The Burrows–Wheeler transform clusters less and costs nothing. It ended with a prediction about the range between them. Sort the rotations by their first $k$ characters instead of by everything that follows, and a shorter context should leave ties. The ties should be exactly what the inverse is missing, so the cost to undo should grow as $k$ falls until at $k = 0$ it is the whole multinomial. If so, the sort and the transform would be one family with one parameter, buying clustering with side information at a stated exchange rate.

The family exists and the parameter is real. The prediction about side information is wrong. It is wrong for a reason that argument could not see, because it treated one decision as if there were only one way to make it.

Two rules for a tie #

Sort the rotations by their first $k$ characters and many of them compare equal. What happens to the equal ones has to be decided, and there are two natural rules.

Keep ties in text order. Rotations whose first $k$ characters agree stay in the order they have in the text. This is what any stable sort does without being asked. At $k$ larger than the longest repeated substring no two rotations tie, and the output is the Burrows–Wheeler transform exactly.

Order ties by the symbol they emit. Inside each tied group, arrange the rotations so the characters in the output column come out sorted. That is the rule that clusters hardest, because a tied group becomes a run of each symbol it holds. At $k = 0$ every rotation ties, and the output is the sorted characters, the sort whose cost to undo was the text’s whole floor.

So the sort and the transform are not the two ends of one parameter. They sit at different corners of a square with two sides. The transform is a long context with ties kept in text order. The sort is no context with ties ordered by symbol. The prediction ran along the diagonal between them and so changed both at once.

Every string, both rules, every context #

Whether a permutation costs something to undo is a counting question: how many inputs share each output. At eight characters over three letters there are 6,561 strings, and each one can be put through both rules at every $k$.

Kept in text order, the limited sort gives every string its own output at every $k$, including $k = 0$. That holds whether the context is zero characters, one, or two. A shorter context leaves more ties, and the ties cost nothing, because their order is information the output still carries.

Why this should be so is less obvious than for the full transform. What a reordering costs to undo explained that transform’s inverse by a walk: each row’s predecessor is found because sorting by the whole following context is consistent from one row to the next. With a limited context that consistency fails, since a rotation one character earlier shares only part of the context. An inverse has to rebuild the contexts first and walk afterwards. The limited-context sort with stable ties is known as Schindler’s transform, and an inverse of that kind has been published since the late 1990s. The enumeration does not rely on that argument. It counts outputs, and every string has its own.

Ordered by symbol, the cost to undo is real, and at $k = 0$ it is the sort’s cost exactly. At $k = 0$ the mean is 8.016 bits, exactly the sort’s figure from the earlier enumeration, because it is the sort. At $k = 1$ it falls to 2.438, at $k = 2$ to 0.236, and by $k = 4$ it is gone at this length, because four characters of context are enough to make almost every rotation of an eight-character string unique. The pale bars show a quantity that is easy to confuse with the measured one: the number of ways the characters inside each tied group could have been arranged. At $k = 0$ that is 11.186 bits against 8.016 measured. The arrangements a tie hides overstate what an inverse lacks, because most arrangements are not the output of any text.

So the prediction was right about one corner of the square and wrong about the rest. A tie costs side information only when its order is thrown away, and a shorter context costs nothing unless its ties are ordered by the symbol they emit.

What the context buys #

If every $k$ is free to undo under text-order ties, the question left is what each $k$ gives a coder. On 8,192 symbols of text built from a fixed vocabulary, the output at each $k$ goes through move-to-front and is charged at its zeroth-order entropy, the same pipeline the ledger used.

Three things in that curve were not predicted.

At $k = 0$ the limited sort is not the sort at all. With nothing to compare every rotation ties, text order keeps them where they are, and the output is the text shifted by one character. It costs 4.155 bits a symbol after move-to-front, essentially the untransformed text’s figure from the earlier ledger. The sorted characters only appear under the other tie rule. “Sorting with no context gives the sort” joined two separate choices into one.

The curve falls fast and then stops. Two characters of context take the cost from 4.155 to 2.100, and four take it to 1.780. Past four, nothing improves. The mean run length says the same thing: 1.01 at $k = 0$, 3.43 at $k = 4$, and 3.38 for the full transform.

The stopping point is partly a property of the source and partly a property of the coder, and the two can be separated. The character a row emits is predicted by the context after it. So the relevant floor is the conditional entropy of a character given the $k$ characters that follow it, which is the ordinary order-$k$ entropy of the text read backwards. On this source that is 2.246 bits a symbol for one character of context, 1.167 for two, 0.948 for three and 0.850 for four. The transform’s curve has the same shape, a steep fall that flattens by three or four characters. It sits between 0.69 and 0.93 bits above the floor at every one of those $k$, and that gap is the price of move-to-front followed by a zeroth-order code. The model is the compressor describes that pipeline as a model in its own right, and a poor one for this purpose. Past four characters the conditional entropy keeps falling, to 0.470 at eight, but by then most eight-character contexts have occurred only once. An estimate built on contexts seen once has learned nothing, and the transform’s flat curve is the more honest reading of how much longer contexts help.

Four characters beat the full transform. At $k = 4$ the output costs 1.780 bits a symbol against the full transform’s 1.802, and the gap closes steadily as $k$ grows: 1.782, 1.793, 1.797, 1.802. A longer context breaks each four-character tie by what comes later in the text. On this source, that later order evidently separates occurrences whose preceding characters had been lined up by text order. The difference is 1.2%, it is measured on one source, and the measurement says nothing about why. The last section takes that question up.

The symbol-ordered line is there as a warning. Its stream is always cheaper, from 0.037 bits a symbol at $k = 0$ to 1.566 at $k = 8$, and a table reporting streams alone would rank it first at every $k$. What a reordering costs to undo was written to catch exactly that. At $k = 0$ the side information brings the total back to 3.924 bits a symbol, near the text’s floor. At $k = 1$ the arrangements hidden in the ties are enough to undo it, since a group’s size is the count of its first character and the decoder can read that from the output. The total there is 2.343 bits a symbol, worse than two characters of context kept in text order, which reach 2.100 with nothing to send.

Two sources, two different answers #

The vocabulary source has structure at several lengths: letters within words, and words within a grammar. Two simpler sources show what the curve looks like when that structure is removed.

The Markov chain makes each symbol depend on the one before it and on nothing earlier. The context that predicts a character is the character after it in rotation order, which is one character. So one character of context gets within 0.4% of the full transform, and the next 54 characters contribute nothing measurable. The context a transform needs is the order of the source, not the length of its longest repeat. On this chain the two differ by a factor of 55.

The uniform source is the control, and it behaves as it must. No context helps, the transform costs what the text costs, and the one line that appears to save something is the symbol-ordered stream, which is the sort again under another name. The model is the compressor makes the general point: a transform can only rearrange structure that a model could have used, and on a source with none there is nothing to rearrange.

What a shorter sort saves #

The reason anyone wanted a shorter context is cost. The transform that emits nothing priced the block sort as the transform’s expensive step, and a sort that compares at most $k$ characters cannot read more than $k$ characters a comparison. The sort used here is a merge sort that counts every character it reads, so the saving can be set directly against the clustering lost.

The saving is real and smaller than the phrase “a shorter context” suggests. On the vocabulary source the full sort reads 730,822 characters. Four characters of context read 461,156 of them, 63%, and give a slightly better result. Most comparisons between rotations were already settled within a few characters, so a limit rarely cuts one short. The expensive comparisons are the rare ones between rotations inside long repeats, and a limit removes only those.

On the Markov chain the saving is much larger, because the full sort pays for accidental repeats of up to 54 characters that carry no information about the source. One character of context reads 14% of the full sort’s characters and gives up 0.4% of the clustering. In this model that is where a limited context earns its place. A comparison count is not a running time, and one run, four counts, four answers is the page about how far apart those can be. A real block sort uses suffix-sorting algorithms whose cost is not a count of pairwise character reads. The measurement prices the comparison model, not a production compressor.

What the runs are worth elsewhere #

Coding is one use of the transform, and not the one that kept it alive. The index that is the text and the essays after it use the transform’s output as a searchable index. That use asks for more than clustering, and the difference shows where a limited context stops being a substitute.

A search over the full transform works backwards through a pattern one character at a time. Each step narrows a range of rows, and it can do that because the rows are sorted by their entire following text: every row that begins with the pattern’s last $j$ characters sits in one contiguous block, for every $j$. Under a limited context that holds only while $j \le k$. Past $k$ characters, rows that share a longer prefix are ordered by text position, not by what follows, so they no longer form a block, and the narrowing step has nothing to narrow. A four-character context supports searches for patterns of up to four characters and no further. That follows from the ordering and was not measured here.

The runs themselves transfer better. The index that stores the runs sized an index by the number of runs in the transform’s output rather than by its entropy. On the vocabulary source the full transform has 2,427 runs. A context of four characters has 2,387, and six and eight give 2,396 and 2,405. So the limited sort’s slightly better clustering is also slightly fewer runs. A run-length index built on it would be slightly smaller, and could not answer the one question an index is built for once a pattern runs past four characters. For a compressor that never searches, the limited context gives up nothing on this source. For an index, the long context is the point.

The comparison count has a similar limit. The suffix array in the index that is the text was built by a method that examines no characters pairwise at all, so the 730,822 reads above are what a comparison sort pays, not what the fastest construction pays. A limited context saves reads within that model. Whether it saves time against a suffix-sorting algorithm is a different measurement.

What is settled and what is not #

Settled by enumeration: at eight characters over three letters, the limited sort with ties kept in text order gives every string its own output at every context length from zero to nine. Ordering ties by symbol collapses 6,561 strings to 45 outputs at $k = 0$, which is the sort, and the side information falls to nothing by $k = 4$. The arrangements hidden in ties are always at least the measured side information, and at $k = 0$ they overstate it by more than three bits.

Settled by measurement on 8,192 symbols: four characters of context match the full transform on a vocabulary source, and beat it by 1.2%. One character matches it on an order-1 source. Nothing helps on a uniform source. The limited sort becomes the full transform exactly at 24, 55 and 9 characters on the three sources.

Not settled:

Injectivity at other lengths. Every string was checked at length eight, and a second enumeration at length seven agrees. The general inverse is a published result, not a measurement here.

The symbol rule’s side information at realistic sizes. At 8,192 symbols the only numbers available are the arrangements hidden in ties, which are sufficient at $k \le 1$ and an upper bound on what is lost. Enumeration shows they can overstate the true cost by a factor of two or more. Where exactly the symbol rule’s total lands at $k = 2$ and above is not known here.

The coder. Every stream is charged at order zero after move-to-front, the same pipeline the earlier measurements of the transform used. A different second stage would rank the contexts differently, and the 1.2% advantage of four characters on the vocabulary source is well within the range such a change could move.

Still open: why four characters beat everything that follows #

A limited context beating the full transform on the vocabulary source is the one result here that should not have happened, and its size, 1.2%, is small enough to be an accident of the source. What differs between the two outputs is only the order inside ties at $k = 4$. Text order puts them by position. The full context puts them by the text that follows the four shared characters.

On a source made of whole words, the four characters after a position are often the rest of a word. The characters after that are the next word, chosen by a grammar that is independent of the character before the context. Sorting by the next word may therefore scatter occurrences whose preceding characters would have run together in text order. The prediction is that the effect depends on the word-length distribution, and that it disappears on a source whose long-range structure depends on the preceding character.

The measurement that follows builds two variants of the vocabulary source: one with words chosen independently of their neighbours, and one where the next word depends on the last letter of the previous one. It sweeps $k$ on both and measures, inside each four-character tied group, how many run breaks each tie rule creates. If the explanation holds, the full context wins on the second source and loses on the first, and the crossing point is the average word length. That would tie the context a transform needs to a measurable property of the source rather than to a constant.