Model order — where it appears
Named by 6 essays across 2 fields — each of them below, with the objects they name alongside it.
The model is the compressor
One stream of 32,768 symbols has an entropy of 3.886 bits per symbol, and 2.243, and 1.186, and 0.991, and 0.909. All five numbers are correct, all five are floors, and nothing about the data changed between them. The only thing that changed is how many preceding symbols the model was allowed to look at — which makes the entropy of a file a property of a decision rather than a property of a file.
The order inside a tie
Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.
A result the size of its own noise
Sorting rotations by their first four characters beat the full Burrows–Wheeler transform by 0.022 bits a symbol. On sixteen streams of the same source the mean difference is 0.004 with a standard deviation of 0.011, and the short context is ahead on ten of them. The 1.2% was one draw. What survives is sharper than the result it replaces: from four characters upwards, every run break either rule makes is at a word boundary, and nothing above four characters decides anything at all.
Where a context stops naming the letter before
A sort of rotations by their first k characters matters only where those k characters fail to decide the character before them, and that share of positions can be counted in one pass with no sorting. It was proposed as a replacement for sweeping k. Counted as proposed, it misses by a factor of four: on a stream of independent words 37% of positions are still ambiguous at four characters, where the sweep has already gone flat. Counted only where the context sits inside a word that goes on past it — the one place more context can still help — it lands within a step of the sweep on four sources of five.
The repeats a context cannot see past
Sorting rotations by their first k characters stops losing to the full Burrows–Wheeler transform at four or five characters on four sources and at about ten on a corpus of technical writing. The count proposed to explain the exception — how much a context spanning a word boundary says about the letter before it — cannot be read off its own estimate, which falls on words drawn independently where there is nothing to find. Measured against each text's own shuffled twin, the information the word order carries is real, but it has all arrived by four or five characters, and at eight, twelve and sixteen the two corpora are indistinguishable. What does separate them is repetition. Stream by stream, the share of positions inside a repeated sixteen-character string predicts the technical corpus's loss with a correlation of 0.98.
The deepening the sort was already doing
A sort of rotations by their first k characters loses to the full Burrows–Wheeler transform where a longer string repeats, and a sort deepened only inside the ranges where contexts repeat was proposed to recover those bits at a fraction of the transform's reading. It recovers the bits: on sixteen streams every one lands within 0.006 bits a symbol of the transform, and the most repetitive goes from 0.129 bits worse to 0.001. It reads more characters than the transform, not fewer — 74.5 a symbol against 69.4 on technical writing — because a comparison sort of rotations already reads deep only where rotations agree. The transform was the adaptive sort. The characters a sort by k characters saves are exactly the ones the repeats needed.
Named alongside it
The objects these essays reach for when they reach for this one.
Context modelEntropyBits per symbolBurrows-wheeler transformHonest limitMeasurement designMove to frontCorpusPredictionEstimator biasInvertibilityPermutation