Where a context stops naming the letter before

The Burrows–Wheeler transform sorts every rotation of a text and outputs the character before each, in sorted order. The transform that emits nothing showed why that helps a coder: rotations that begin alike are usually preceded by the same character, so the output comes in runs, and a move-to-front pass turns runs into small numbers that the bits a coder emits could price. What a reordering costs to undo showed that the transform’s sort is what makes it invertible, which is why a sort by only $k$ characters needs its tie rule to be one a decoder can repeat. The order inside a tie sorted rotations only by their first $k$ characters, breaking ties by position, and asked how much of the transform’s benefit survives. A result the size of its own noise swept $k$ over sixteen streams of two word sources and found that the short sort’s win at four characters had been one stream’s noise. It also found something sharper. From four characters up, every run break either tie rule made was at a word boundary, and nothing above four characters decided anything at all.

Its closing section turned that into a quantity. A tie rule can reorder the output only among rotations whose first $k$ characters are the same, and it can change a run only where those rotations are preceded by different characters. So for each $k$, the share of positions whose $k$-character context is preceded, somewhere in the text, by more than one distinct character is the tie rule’s whole reach. That share can be computed in one pass, with a hash of each context and no sorting and no coder. The section predicted that the $k$ at which this share falls under a threshold would predict the $k$ at which the sweep’s curve flattens, which would make the sweep over $k$ unnecessary. It predicted that on word sources the share would fall off a cliff at the mean word length, and that on a text with a broad spread of word lengths both the share and the curve would decay smoothly.

The share can be computed exactly and quickly. As proposed, it predicts the flattening badly. The way it fails says which part of it to count, and counted that way it predicts well.

The share as proposed #

The measurement uses five sources, eight streams of 8,192 characters each. Two are the earlier pages’ word sources: words from a short fixed list drawn independently, and a chain in which the next word depends on the last letter of the one before. The third draws words independently from the whole vocabulary of the collection’s fixed corpus of essays, 2,424 distinct words of three letters and more, the broad spread of lengths the prediction asked for — a mean word of 7.1 letters against the short lists’ 4.2. The last two are slices of the two fixed corpora themselves, lower-cased to letters and single spaces — the twelve essays and the eight source modules a corpus that was not generated introduced as the collection’s text that no model wrote. They are the sources the proposal’s claim is really about, since a rule read off a text is worth having only if it holds on text nobody designed. For every stream and every $k$ the share is computed cyclically, with the transform’s own sentinel.

On words drawn independently, 37% of positions are still ambiguous at four characters, and the share does not fall under 5% until sixteen. The earlier page found nothing above four characters decided anything on the same source. So by the proposed measure the tie rule has a large reach for another twelve characters, and the sweep says the reach is worth nothing. The share falls smoothly on every source, with no cliff at the mean word length, even on the synthetic ones.

The reason is in what the ambiguous positions are. At four characters on a word source, a typical ambiguous context is a word’s last letters and the space after it, or a space and the first letters of the next word. The character before it is the letter before those last letters, or the last letter of the previous word. Different occurrences of the context are preceded by different characters, so the context is ambiguous. But nothing that follows the context says which character that was. After the space comes the next word, and on this source the next word is drawn independently of the one before. A longer context adds characters from a word that carries no information about the ambiguity. The tie rule can reorder those positions freely, and every order it can choose is as good as every other.

So the share measures where a tie rule could reorder the output, and the sweep measures where reordering changes the output’s runs. On text whose words are independent they part ways at every word boundary.

The part that more context can resolve #

The ambiguity that a longer context can resolve is ambiguity inside a word that goes on past the context. If the context is the middle of a word, the rest of the word follows it, and different words sharing that middle continue differently and are preceded by different letters. “ati” is preceded by n in nation and r in ratio, and the character after “ati” — o in both, then n against a space — eventually tells them apart. That is the only kind of position where sorting by more characters can put equal predecessors next to each other.

Counted only inside continuing words, the share falls under 1% at four characters on independent words, at five on the corpus of essays, and at six on the broad vocabulary and the technical corpus. On the synthetic word sources it reaches exactly zero at four, because no word in their short list has an ambiguous four-letter stretch that continues. On the corpora it falls fast and smoothly, by a factor of three to five a character from three characters on.

This is the quantity the proposal was reaching for. It needs the same single pass as the share it refines, plus one character of look-ahead to see whether the word continues past each context, and it is a property of the text read directly.

The sweep it has to predict #

The comparison needs the sweep itself: for each source and $k$, the bits a symbol after move-to-front of the context sort’s output, less those of the full transform’s.

On four sources the curve behaves as the earlier page found for its two. The excess falls by a factor of three or four a character up to four or five, and then sits within a hundredth of a bit of zero, inside its own spread across streams. On the corpus of essays it is +0.015 at four characters and +0.002 at five. On the broad vocabulary it is +0.010 at four and +0.001 at five. On both word sources it reaches the noise at four.

The technical corpus is different in two ways. Its excess declines slowly, +0.032 at four and +0.010 at eight, and its spread across slices is huge — 0.035 at five characters, larger than the mean. In some slices a context reaching into the next word evidently does say something about the letter before it, and in others it does not; the slices differ from each other far more than any two streams of a synthetic source. Averaged over eight slices, the curve cannot place its flattening more precisely than somewhere between five and twelve characters.

Where each measure crosses #

Counted inside continuing words, the share crosses within one step of where the sweep flattens on four of the five sources; the share as proposed crosses three to six steps late on every one. On the two word sources both the refined share and the sweep say four. On the corpus of essays both say five. On the broad vocabulary the sweep says four, sitting at exactly a hundredth of a bit there, and the refined share says six, the curve’s value at five being a thousandth. The technical corpus is the exception, and the direction of the exception is informative. There the refined share says six and the sweep says about ten: on that text the next word carries some information about the previous one, and ambiguity spanning a word boundary can be resolved by a longer context too.

So the prediction’s structure was right and its quantity was one step too coarse. A one-pass count of a text does predict where a sort by context stops needing more context, but only the part of the count where more context can be informative. The prediction’s second half fails outright. On a broad spread of word lengths the refined share does decay smoothly, a factor of three a character, but the curve does not: on the broad vocabulary it has fallen to a thousandth of a bit by five characters, as sharply as on the short word lists.

What the one pass saves #

The point of the proposal was economy, and the refined share keeps it. The sweep behind the curve plate sorts the rotations of every stream at twelve context lengths, runs move-to-front on each output and measures its entropy: for five sources and eight streams, 480 sorts of 8,192 rotations. The shares come from one pass per stream and context length, hashing each context and remembering the first character seen before it. The refined share adds a look at the character after each context. On a slice of the corpus of essays at eight characters, the pass takes about a quarter of the time of one context sort, 0.8 milliseconds against 3.5, and the sweep also needs a move-to-front pass and an entropy for every sort. The share needs no coder and no inverse.

It also answers a question the sweep answers only indirectly. The sweep says at what $k$ the bits stop falling. The share says why: at that $k$ the contexts inside words have become unique, and what ambiguity remains spans word boundaries, where it is resolved only if the next word is predictable. That is an account of the text, not of the transform. The model is the compressor found one stream with five correct entropies at five model orders, and the refined share is a way of reading off a text which model order its letters stop needing. Its words’ internal structure is exhausted within about one word length, and whatever is left is the structure between words.

The technical corpus has more of that between-word structure than the other sources, and the obvious explanation for it does not survive a count. Repeated phrases would do it: a phrase that recurs is a context crossing a word boundary that is always preceded by the same letter. But the essays repeat word pairs more than the technical corpus does. Of the essays’ word pairs, 31.5% belong to pairs that occur five times or more, and of the technical corpus’s, 27.4%. The technical corpus is writing about programs, and its most frequent pairs include fragments of code — throw new, new error, export function — alongside the ordinary is the and and the. Whether it is those fragments, or longer repeats that a count of pairs cannot see, is not established here. The dictionary that builds itself measures the other obvious candidate, a coder whose whole model is whether a stretch of text has been seen before, and a comparison of what such a coder finds in the two corpora is the natural way to settle it.

Where the ambiguity is #

At five characters almost all the ambiguity on every source spans a word boundary: 20% to 37% of positions, against at most 3% inside a continuing word. The sweep’s excess beside each bar is near zero for every source but the technical corpus, whose boundary-spanning ambiguity is no larger than the others’ and whose excess is ten times theirs. The size of the ambiguity across a boundary says nothing about its cost. What decides the cost is whether the next word carries information about the previous one, and that is a property of the text’s word sequence, not of its letters.

The chained word source is the check. Its next word is chosen from a third of the vocabulary set by the previous word’s last letter. That is exactly the kind of cross-boundary dependence that should make boundary-spanning ambiguity matter. Its excess at five to ten characters is +0.004, +0.004, +0.002 and +0.002 bits a symbol, with spreads across streams of 0.01. The dependence is real and the resolution it buys is below what eight streams can see: the next word says only which third of the vocabulary the previous word’s last letter selects, and the move-to-front coder spends little on that.

What was measured and what was not #

Eight streams of 8,192 characters a source. The earlier page used sixteen streams of its two sources; this one uses eight of five. On the synthetic sources the spreads match the earlier page’s, about 0.01 to 0.015 bits a symbol at four characters. On the corpora the slices are more varied than any stream of a synthetic source, and the technical corpus’s crossing is correspondingly uncertain.

Thresholds chosen, not fitted. The crossings use a hundredth of a bit a symbol for the sweep, 1% for the refined share and 5% for the share as proposed. They were set before the curves were read, and the comparison is between where each falls rather than whether a particular threshold matches. A threshold of 5% on the refined share would cross a step earlier everywhere, and one of 1% on the full share would cross a step or two later.

Lower-cased letters and spaces. The corpora are reduced to the word sources’ alphabet so the five sources are comparable. Real text keeps punctuation and case, which add ambiguity at word boundaries and, through capitals after full stops, a little information across them.

The word boundary is taken from the text. “Inside a continuing word” uses the space character. That is exact for these sources. For text without spaces — code with identifiers joined by underscores, or languages written without them — the refined share needs some other notion of where a context stops being informative.

Still open: the information across a boundary, counted #

The refined share failed on the one source where the next word depends on the previous one, and the chained source showed the same dependence at a size too small to measure. What the refined share leaves out is not ambiguity but information: how much a context that crosses a word boundary says about the letter before it. That too is a property of the text, and it can be estimated from counts.

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 from $k$ to $k+1$ is the information the extra character adds. Its fall across boundary-spanning contexts alone is the information the next word carries about the previous one. The measurement that follows computes that fall on the five sources, with a correction for the estimate’s downward bias in contexts seen only a few times. It asks whether adding the boundary-spanning information to the refined share moves the technical corpus’s predicted crossing from six towards the sweep’s ten, without moving the others. The prediction is that it does, because whatever makes the technical corpus’s boundary-spanning contexts informative must show up as contexts seen many times with the same predecessor, which is what the conditional entropy counts. It could fail by bias: the plug-in estimate of a conditional entropy falls towards zero as contexts become unique, which is the same over-reading of long contexts that made the proposed share cross late, now in a different quantity.