The repeats a context cannot see past

Where a context stops naming the letter before sorted the rotations of a text by their first $k$ characters and compared the result with the full Burrows–Wheeler transform, which sorts by all of them. A short sort loses only where a context of $k$ characters fails to decide the character before it. The share of such positions, counted in one pass inside words that go on past the context, predicted within a step the $k$ at which the sort stops losing, on four sources of five. The two word sources flattened at four characters, the corpus of essays at five, a source drawing words from a whole vocabulary at four. The corpus of technical writing flattened at about ten, where the share said six.

The page could not explain the exception. Its closing section proposed the quantity it had left out: information rather than ambiguity. For each $k$, the conditional entropy of the preceding character given the context can be estimated from the same single pass that counts the contexts. Its fall over contexts that cross a word boundary is what the next word says about the previous one, which might be what the technical corpus has more of. The section predicted that adding that fall to the share would move the technical corpus’s predicted crossing towards ten without moving the others. It named how the idea could fail: by bias, since an estimate of a conditional entropy from counts falls towards zero as contexts become unique.

It failed exactly that way. The repair for the bias works, and it shows that the information across a boundary is not what the technical corpus has. What it has is repetition.

An estimate that finds information where there is none #

The loss being explained is measured as the earlier page measured it: bits a symbol after move-to-front and an order-zero entropy, the cost the bits a coder emits showed a real coder approaches to within a few hundredths. Three estimates are computed for each $k$, over the same five sources and eight streams of 8,192 characters as before, and each is split into the positions whose context stays inside a word and those whose context spans a space. The plug-in estimate is the entropy of the predecessors actually seen after each context. The corrected estimate adds Miller and Madow’s allowance for the downward bias of an entropy counted from few observations. The adaptive estimate is the cost of predicting each predecessor, in text order, from the counts of that context seen so far: a coder that could actually be run, so its estimate can never be lower than the information there is.

The plate is drawn on the source where the answer is known in advance. Its words are drawn independently of one another, so the next word says nothing about the previous one. Past the length of a word, a longer context cannot tell a sort anything more about the letter before it, and the sweep agrees: it is flat from four characters. Over those same boundary-spanning contexts, the plug-in estimate falls from 0.849 bits a symbol at four characters to 0.466 at eight, as if the extra characters had told it a third of a bit, and to nothing by twenty-four. None of that fall is information. It is contexts becoming unique: a context seen once has one predecessor, and the plug-in entropy of one observation is zero. At twelve characters most contexts on this source are seen once, and the estimate reads that as certainty.

The correction for unseen predecessors barely moves it, because the correction is for contexts seen a few times and these are seen once. The adaptive coder goes the other way: a context seen once costs its whole alphabet to predict, so the coder’s estimate climbs past four bits as contexts become unique. The truth lies between the two, and neither curve shows where. The fall the proposal asked for cannot be read off any of them, because on the one source where it is known to be zero, all three report it as large.

A text’s own twin as the control #

The bias comes from contexts becoming unique, and that depends on how much the text repeats, not on what its word order means. So a control that repeats in the same way but has no word order is a way to cancel it. Every stream has one: the same words, shuffled into a random order. The shuffled twin keeps every word, every letter inside a word, and so nearly the same unique contexts. It loses whatever one word says about the next. The plug-in estimate of the twin less that of the text is what the order of the words adds, with the bias shared by both.

On both independent-word sources the twin difference is zero to within 0.002 bits a symbol at every length; the bias has cancelled. On the three sources whose word order means something, it measures that meaning. On the chained source, where each word is chosen by the last letter of the one before, the order is worth 0.241 bits a symbol at four characters. On the technical corpus it is worth 0.110, and on the essays 0.071.

Every one of those peaks is at four characters, and on every source most of the information has arrived by five. That is the prediction’s main claim failing. The chained source carries the most word-order information of all, more than twice the technical corpus’s, and its sort flattens at four characters, because the information arrives inside the first few characters of the next word — which is where a context of four already reaches. Information that arrives early cannot delay the crossing. The technical corpus’s order information peaks at the same length as the essays’ and has the same shape, a third larger. Nothing in it says ten.

Where the twin turns negative #

Past eight characters the difference changes sign on the two corpora, and the reason is the clue to everything else.

At four characters the word order leaves less unknown about the letter before a context than a shuffle does. Past eight it leaves more. On the essays the written text’s estimate is 0.037 bits a symbol at twelve characters, against the twin’s 0.015. The written text repeats itself in ways a shuffle destroys — a phrase, a name, a construction — so its long contexts recur, each time after different letters, and stay ambiguous. The twin’s long contexts are new combinations of words that each occur once, and they become unique sooner. So the twin difference past a word does not measure prediction. It measures repetition, with the opposite sign. The transform that emits nothing found that the Burrows–Wheeler transform changes no count of characters, only their order, and that everything it gains comes from what the order lets the next stage see. A repeat is order at its most extreme, and a count of predecessors cannot see it.

On this plate the two corpora are all but the same curve past a word. At eight, twelve and sixteen characters their estimates as written differ by at most 0.008 bits a symbol, and their twins agree more closely still. Whatever makes the technical corpus’s sort lose until ten characters, the conditional entropy of the letter before a context does not see it — not through the plug-in count, not through the correction, not through the twin. The model is the compressor found five correct entropies for one stream at five model orders. This is the same caution from the other side: the order-$k$ entropy of the predecessor is a property of the text, and here it is the same for two texts whose transforms behave differently.

Repetition longer than any word #

Of the technical corpus’s positions, 6.5% begin a twenty-four-character string that occurs again in the same stream of 8,192 characters, against 0.8% of the essays’. At thirty-two characters it is 4.6% against 0.3%. The earlier page found that the essays repeat word pairs more than the technical corpus does. That still holds — at twelve characters and below the two are within a factor of two. Past two words the difference opens to a factor of eight and then fifteen. The technical corpus is writing about programs, and it quotes them: identifiers, calls, error messages and whole lines recur, word for word, far longer than any phrase an essay repeats.

A repeat share alone cannot be the whole story, and the word sources say why. The chained source repeats a quarter of its sixteen-character strings, more than the technical corpus, because its words come from a short list and follow one another by rule; its sort does not lose anything past four characters. A repeat costs a short sort only if the letter before it is left ambiguous by the short context and named by the long one — only if the repeat is a copy of something longer. That can be counted too, in the same pass. Of the technical corpus’s positions, 0.87% have a context ambiguous at eight characters that a repeated twenty-four-character context resolves to a single predecessor. On the chained source it is 0.26%, on the essays 0.06%, on independent words 0.02%, and on the broad vocabulary none. That count separates the technical corpus from all four others by a factor of three or more, where the plain repeat share did not.

A long repeat that is a copy is exactly what a sort by $k$ characters cannot use. Take a twenty-four-character string that occurs twice. Its rotations share their first $k$ characters with every other occurrence of the same $k$ characters. The full transform sorts by all twenty-four and puts the two copies’ predecessors side by side, where move-to-front codes the second almost for nothing. A sort by $k$ breaks the tie by position and scatters them among the other occurrences of their first $k$ characters. The order inside a tie found that the order of rotations within a tied context can matter as much as the sort itself; for a copied string it is the whole difference. The loss is paid at every $k$ shorter than the repeat, and it stops only when $k$ is long enough to separate the repeat from everything else. The dictionary that builds itself measured a coder whose whole model is that the next stretch of text appeared before, and that is the model the technical corpus rewards.

Stream by stream #

A share averaged over eight streams could hide a coincidence, so the claim is tested where it would fail: each stream on its own.

Across the technical corpus’s eight streams, the share of positions in a repeated sixteen-character string and the sort’s loss at eight characters correlate at 0.98. The stream where 28% of positions repeat loses 0.043 bits a symbol. The one at 17% loses 0.018, the two near 10% lose 0.010 and 0.004, and the two near 5% lose nothing. The corpus’s loss at eight characters is not a property of technical writing spread evenly through it. It is concentrated in the streams that quote code, in proportion to how much they quote. The earlier page reported the technical corpus’s spread between streams as larger than its mean. This is what the spread was.

The essays’ streams all sit between 1.6% and 6.6% and show no clear relation; at those shares nothing is lost to relate to. A result the size of its own noise found that a difference between two orderings of rotations could be smaller than the spread between streams of the same source. Here the spread between streams was itself the signal. It just needed the right quantity measured beside it.

So the prediction fails, and the failure is informative. The information across a word boundary is real, and the twin measures it cleanly, but it arrives too early to move any crossing. The one-pass quantity that does track the technical corpus’s late crossing is not an entropy at all. It is a count of long repeats that are copies — a context that recurs at twenty-four characters, always after the same letter, where eight characters left that letter open. The same pass that counts contexts can make it, by keeping for each long context how often it occurs and whether its predecessors agree. Whether that count predicts the crossing on other texts, rather than separating one corpus from four, is a claim for a text with planted copies to test.

What was and was not established #

One corpus of technical writing. The repeats are the technical corpus’s own: text about programs, with code quoted in it and all punctuation removed. A technical corpus without quoted code would have fewer of them, and nothing here says the result is about technical writing rather than about quotation.

Correlation across eight streams. The per-stream relation is strong, and it is a correlation across eight streams of one corpus, not a controlled experiment. The controlled version would plant repeats of a stated length into a stream of the essays and measure the sort’s loss as the planted share grows.

The twin cancels the bias only where the two texts repeat alike. Shuffling words preserves the words and destroys phrases, so past a word the twin repeats less than the text, and its difference measures that. At four and five characters, where the word-order information is, a context lies within one or two words, and a text and its twin repeat such short strings far more alike than they repeat whole phrases; the difference there is mostly information, and the independent sources, where it is zero, show the residue of the bias is small.

Eight streams of 8,192 characters. Every estimate, share and excess is at the earlier page’s size. What a reordering costs to undo priced the information a sorted order hides, and a stream long enough to hold a whole program’s text would hold more of it. A longer stream has fewer unique contexts at every $k$, so the plug-in bias moves to longer contexts, and more repeats fall inside a stream, so the repeat share grows. Both move the curves; neither is measured here.

Still open: a sort that finds the repeats before it sorts #

The sort by $k$ characters loses where a string longer than $k$ recurs, and the full transform wins there by sorting as deep as each repeat requires. There is a structure between them: sort by $k$ characters, and deepen the sort only inside the ranges where a long repeat has been detected. Detection is the one-pass count this page ends on. A context whose count exceeds one at length $2k$ marks a range worth deepening, and everything else stays at $k$.

The measurement that follows builds that sort. It deepens a range only when its contexts repeat at twice the current length, and continues until no range does. It compares the bits a symbol and the characters compared against the sort by $k$ and against the full transform, on the technical streams sorted by their share of long repeats. The prediction is that it matches the full transform’s bits on every stream while comparing far fewer characters. On streams with few long repeats it should be almost the sort by $k$, and on the most repetitive it should pay for the repeats and nothing else. It could fail if deepening one range reorders its neighbours — two repeats sharing a prefix but differing further on — so that the ranges cannot be deepened independently. That would make the cost of a repeat depend on what else repeats beside it, which is the structure a suffix array is built to handle and a context sort was built to avoid.