A result the size of its own noise

The order inside a tie sorted a text’s rotations by their first $k$ characters rather than by everything that follows, and found that at $k = 4$ the output clustered slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads and at no cost to undo. It said so carefully. It called the 1.2% “small enough to be an accident of the source”, and it left a measurement to settle the question — two vocabulary sources, one whose words are drawn independently and one whose next word depends on the last letter of the one before, with a prediction that the full context would win on the second and lose on the first.

That measurement is here, and it settles a different question first. The two sources agree, and neither of them shows the effect at all.

Sixteen draws of the same thing #

The quantity in question is a difference between two numbers that differ in the third decimal place, taken on one 8,192-symbol stream. The first thing to establish is what that difference does on a second stream.

The per-stream spread is 0.011 bits a symbol and the mean is 0.004. The reported result is one and a half standard deviations above the centre of the distribution it was drawn from, which is an ordinary place for a draw to be. Six of the sixteen streams have the opposite sign.

Where the spread comes from is worth a sentence, because it is not measurement error in the usual sense. Nothing here is noisy: given the stream, both numbers are exact to fifteen decimal places and reproduce on any machine. The variation is in the stream — 8,192 symbols is about two thousand words, and which words happen to fall next to each other decides how many rotations share each four-character context and how the emitted characters inside those groups happen to run. On average is not a number made the same distinction for quicksort’s comparison count, where six hundred runs give a distribution and the mean is the least interesting thing in it. Here the distribution is over sources rather than over seeds inside one algorithm, and the consequence is the same: a single number from it is a sample, and it has to be reported as one.

Sixteen is not an arbitrary number here. Five streams were tried first and they leave a standard error of half the effect, which is enough to say the effect was not found and not enough to say it is not there. Sixteen leave a quarter of it. The first of the sixteen seeds is the one SOURCES.english uses, so the earlier measurement is inside the set rather than beside it — it can be pointed at rather than argued about.

This is the shape of error the seeding rule here is written against, arriving from the direction it does not cover. Every figure here is drawn from a stated seed so that the numbers in a caption are the numbers on the page, and the adversary who knows the seed has already recorded what that costs in a different setting. The cost here is subtler: a fixed seed makes a measurement reproducible without making it a measurement. That 1.780 is exactly right and anybody can reproduce it. It is a property of that stream.

What the two sources were for #

The prediction had a mechanism behind it, and the mechanism is worth stating precisely because most of it survives. On text made of whole words, the four characters after a position are often the rest of a word, and the characters after those are the next word — which, in a source that draws each word independently, is chosen without reference to anything before it. Sorting a tied group by the following context is then sorting on a coin flip, and it scatters rotations that text order would have left adjacent.

If that is the whole story, the effect must weaken on a source whose next word depends on the previous one, because there the following context carries information about what precedes it.

The chain does a great deal to the text — a fifth off the transform’s own cost — so the two sources are genuinely different objects and the comparison is not empty. It does nothing to the tie rule. The advantage at $k = 4$ is +0.0038 on the independent source and +0.0064 on the chained one, both inside their own spread and both, if anything, in the direction the prediction said would reverse.

Building that second source took one wrong turn worth recording. The obvious construction is to bucket the words by their last letter and draw the next word from the bucket its predecessor’s last letter names. Five of these twenty-eight words end in e and every one of those ends in e, so that chain has an absorbing class: it produces “the here the here the table figure figure” and a zeroth-order entropy of 3.37 against the independent source’s 4.05. The two sources would then have differed in their letter statistics as well as in their word order, and no comparison between them could have attributed anything to either. Round-robin buckets keep every word reachable and leave the letter distribution where it was, while still cutting the choice of the next word from twenty-eight to about thirteen — one and a half bits of dependence, which is the thing being varied.

Where the context length does decide something #

The null at $k = 4$ is not a null everywhere. Swept over $k$, the curve has a decisive region and the decisive region is below four.

At $k = 2$ the full context is ahead by 0.303 bits a symbol on the independent source and 0.433 on the chained one, on sixteen streams out of sixteen, both sources. At $k = 3$ it is 0.096 and 0.146, again on every stream. At $k = 4$ it is nothing.

So the question the previous page asked — how long a context does a transform need? — has a sharp answer, and the answer is not the one either page was looking for. It needs four characters on this source, and the fourth character is the one that matters; the fifth and everything after it change the output without changing what the output costs.

The shape of that curve is the same shape the dictionary that builds itself found when it swept LZSS’s window: a steep region where the parameter is buying something real, then a flat one, and past the flat region the sweep is measuring the source rather than the algorithm. The difference is that there the flat region eventually turned down — widening the window past 4,096 made the compressor worse, because the offsets cost more than the matches saved. Nothing here turns down, because a longer context costs the sort reads and costs the output nothing.

Why four #

The tie rule arranges the rotations inside a group that shares a context. Whether that arrangement can change anything depends on whether the group holds more than one distinct emitted character, and that is decidable.

Four characters inside a word of mean length 4.16 name the word. Naming the word names the character before it, because in a vocabulary of twenty-eight words no two share a four-character substring at the same offset often enough to matter. A group whose context stays inside a word therefore holds one distinct emitted character, and no ordering of it can break a run. The collapse from 34% to 0.014% happens in two steps, at exactly the lengths a mean word of 4.16 predicts.

The arithmetic behind “name the word” is worth performing rather than taking on trust. Twenty-eight words with a mean length of 4.16 give about 2,000 word-starts in an 8,192-character stream and roughly 90 distinct four-character substrings that lie wholly inside a word. Those 90 contexts cover 2,241 rotations — a mean group of twenty-five — and every one of those groups emits a single distinct character. A group of twenty-five rotations that the tie rule may arrange in any of 25! ways, all of which produce the same output. That is the sense in which the reach collapses while the room does not.

What is left for the tie rule to decide is the groups whose context reaches a space. There, the characters after the context really are the next word, and there really is a choice to make. The two rules make it differently and arrive within three breaks of each other out of 2,197 — which is the measurement the whole prediction reduces to, and it is a measurement of nothing.

The two curves separate two quantities that are easy to run together. The tie rule’s room — how many rotations it is arranging — falls steadily and is still substantial at $k = 8$, where the largest group holds sixty-eight rotations. Its reach — how many of those it can actually change the cost of — collapses at $k = 4$. A group of sixty-eight rotations all emitting the same character is a group the tie rule has complete freedom over and no effect on.

That is the general form of the result, and it is not about words. A tie rule matters exactly where the context fails to determine the character before it. On a word source that is at word boundaries; on a source with a different structure it would be somewhere else, and the length at which it stops mattering would be that structure’s own scale rather than 4.16.

And across vocabularies #

One more parameter was worth moving, because an early version of this page moved it by accident. A first attempt used a thirty-eight word vocabulary instead of SOURCES.english’s twenty-eight, and on a single stream the 0.022-bit win became a 0.018-bit loss with nothing else changed — a swing larger than the effect. That is either a real dependence on the vocabulary or the same sampling noise seen twice.

It is the noise. Across a sevenfold range of vocabulary, over which the transform’s own cost rises by 57% and the tie rule’s room falls by a factor of fifteen, the difference between the two rules stays within half a hundredth of a bit of zero and never reaches two standard deviations from it. The sign agrees with the mean on between seven and ten of sixteen streams at every size, which is what a coin does.

What the earlier page got right #

It would be easy to read this as a page that overturns the one before it, and that is not what happened. The page before this one made two claims and the smaller one was wrong.

The larger claim was about the cost to undo, and it stands untouched. Sorting the rotations by their first $k$ characters with ties kept in text order is injective at every $k$ — every string of eight characters over three letters keeps its own output — so the family between the sort and the transform costs nothing to invert, and the prediction that a shorter context would leave ties for the inverse to pay for was wrong for a reason that had nothing to do with sampling. What a reordering costs to undo priced the two ends of that family exactly, and the finding that the cost lives in the tie rule rather than in the context length is a statement about all strings, established by enumeration rather than by measurement on a stream.

The smaller claim was that a four-character context also clusters better. That one was a single draw, and it is the one that does not survive.

Both claims sit inside a larger one that these pages have been building since the model is the compressor: the entropy of a text is a property of a decision about how much context to condition on, rather than a property of the text. The transform is that decision made implicitly — sorting by the whole following context is conditioning on all of it — and the family between the sort and the transform is that decision made with a dial. What this page adds is that the dial has a stop. Past four characters on these sources it moves nothing, and the reason it moves nothing is that the context has already determined the thing the transform is arranging.

The difference between those two claims is the difference between the two instruments the earlier page used, and it is worth naming. An enumeration over every string of a length is a statement about the object. A measurement on a stream is a statement about a stream, and becomes a statement about the source only with a count of streams beside it. Fitting a class to measurements made the same distinction for complexity classes, where a fit across three orders of magnitude is a claim that can fail and a single measured point is not.

What is settled and what is not #

Settled, over sixteen streams of 8,192 symbols on each of two sources: at two characters of context the full transform beats the limited sort by 0.303 and 0.433 bits a symbol, and at three by 0.096 and 0.146, on every stream of both. At four characters and above the difference is +0.0038 ± 0.011 and +0.0064 ± 0.011, with the sign agreeing with the mean on ten and twelve streams of sixteen. The single stream that reported +0.0218 is inside that distribution at one and a half standard deviations.

Settled, by counting: from $k = 4$ upwards, 0.014% and then none of the run breaks either rule makes lie inside groups whose context stays within a word, against 34% at $k = 2$. The two rules differ by three breaks in 2,197 at $k = 4$.

Settled, across six vocabularies from eight to fifty-six words, over which the transform’s own cost rises 57%: the difference stays between +0.0001 and +0.0051 and never reaches two standard deviations from zero.

Not settled:

Longer streams. Every measurement here is 8,192 symbols. The spread of the difference should fall as the stream lengthens, and if the mean is genuinely +0.004 rather than zero, a long enough stream would separate it. Nothing here says whether 0.004 is a small real effect or a small null; it says the reported 0.022 is neither.

Real text. These sources are word lists with a stated grammar, which is what makes the boundary argument checkable — the position of every word boundary is known. A real corpus has a word-length distribution rather than a mean, punctuation, and long-range structure, and the sharp collapse at four characters would presumably become a soft one over a range.

Other tie rules. Two rules are compared here and the earlier pages compared a third, sorting a tied group by the symbol it emits. That one is not free to undo and is priced elsewhere; whether any rule that is free to undo beats text order by more than noise is untested, and the space of such rules is not small.

The reads. The four-character sort reads 63% of the characters the full sort reads, and that number is not in question. If the two outputs cost the same, that saving is the whole of the case for the limited sort — and it is a case about construction cost, which is the axis the transform that emits nothing did not measure and this page has not either.

The coder. Every cost here is the zeroth-order entropy of the move-to-front output, which is the measure every page here has used and is a floor rather than a coder’s bill. The bits a coder emits measured the gap between that floor and what a Huffman coder and an arithmetic coder actually spend, and a difference of 0.004 bits a symbol is well inside the first of those gaps. A comparison taken at the coder rather than at the floor might not have the same sign, and nothing here says which way it would go.

Still open: the length at which a context names its own predecessor #

The result that survives is a rule about when a tie rule can matter at all: it matters exactly where the context fails to determine the character before it. On these sources that length is the mean word, and the collapse is sharp because every word is drawn from a short list.

That suggests a quantity computable from a source rather than measured on it. For a given $k$, the share of positions whose $k$-character context is followed by more than one distinct preceding character is a property of the text — one pass to compute, no sorting, no coder — and the argument here says the tie rule’s whole reach is that share. If it is, then the context length a transform needs is readable off a text directly, and the sweep over $k$ that every page here has run is unnecessary.

The measurement that follows computes that share for each $k$ on both sources here, on the frozen corpora, and on a source with a deliberately broad word-length distribution; sets it against the run-break counts measured above; and asks whether the $k$ at which the share crosses a stated threshold predicts the $k$ at which the sweep’s curve flattens. The prediction is that it does on the word sources, where the share falls off a cliff, and that on a corpus with a broad length distribution both the share and the curve decay smoothly and the “context a transform needs” stops being a single number — which would explain why the question has an answer here and does not in general.