What repetition is worth once the logarithm is gone

Two measures of repetition are quoted side by side in every account of compressed indexing: r, the number of runs in the Burrows–Wheeler transform, and z, the number of phrases in the Lempel–Ziv parse. Both are reported per character, both fall as a collection grows, and the fall is offered as evidence that the collection repeats.

The half of a fall that is the logarithm showed that on real prose most of that fall is not evidence of anything. Phrases per character on a collection of essays fell by a factor of 2.34 between eight thousand characters and a million — and a shuffle of the same characters, holding the length, the alphabet and the zeroth-order entropy exactly and destroying the arrangement, fell by 1.70. What the collection was actually worth was 1.37.

The reason is arithmetic rather than empirical. On a text with no structure at all, z/n is about 1/log_σ n: a greedy parse of a random string produces phrases of length about log_σ n, because that is how long a string has to be before its earlier occurrence stops being likely. So any text at all shows a falling phrase rate as it grows, and the fall is a logarithm.

That measurement was made on the case the structures are not for. This one is made on the case they are.

The axis has to be the arrangement #

There is a design decision here and getting it wrong produces a plate that says nothing.

Sweeping the total size of a repetitive collection at a fixed copy count grows the base along with everything else. The collection is sixteen copies at every point, so its repetitiveness is constant, and the only thing changing is the length — which means the phrase rate falls exactly as the control’s does and the plate reports a logarithm. That is a correct measurement of the wrong quantity, and it is what a naive size sweep on this cell produces.

Sweeping the copy count at a fixed base is the experiment. The base is two thousand and forty-eight characters throughout; the collection is two copies, then four, then eight, out to thirty-two. The alphabet does not move. The length does move, so the control is still necessary, and the control is what separates the two effects.

The result: the collection’s phrase rate falls by a factor of 4.71 and the control’s by 1.45. What the repetition is worth, after the logarithm is removed, is 3.24.

There is a second reason the copy-count axis is the right one, and it is about what a reader can do with the answer. A number attached to “this collection is sixteen copies of a base” is a number an engineer can act on: an archive of sixteen releases, a mirror set of sixteen hosts, a document with sixteen revisions. A number attached to “this collection is a million characters” is a number about a size, and sizes are the thing the control is removing. So the axis that isolates the effect is also the axis that carries the meaning.

The base length is held at two thousand and forty-eight characters throughout, which is short enough that the whole sweep fits in sixty-five thousand characters and long enough that the base itself is past the region where a parse is dominated by its own start-up. Both of those are choices and both would change the numbers slightly; neither changes the ordering, and the control is what makes that claim checkable rather than asserted.

Two ends of one measurement #

That number should be read against the 1.37 the same procedure produced on prose, and the comparison is the point rather than either figure alone.

On prose, the control accounted for 73% of the raw fall. On a collection of copies it accounts for 31%. The two collections are being measured with the same instrument, the same control and the same two-ended check, and they give answers a factor of two and a half apart in what the arrangement is worth.

That is what the distinction between repetitive and predictable is, stated numerically. Prose is predictable: its next character is guessable, its entropy is low, and a compressor exploiting that does well. It does not repeat: no long stretch of it occurs earlier verbatim, so a parse that copies from earlier text finds only short phrases and finds them for the arithmetic reason above. A collection of copies repeats, and the parse finds phrases hundreds of characters long.

The run count tells the same story with a sharper control. Runs per character on the shuffled text is 0.906 at two copies and 0.906 at thirty-two — flat to three decimal places, because the shuffle has destroyed every run longer than chance allows and the number of those does not depend on the length. So r’s fall of 3.40 has no logarithm in it at all; every bit of it is the arrangement.

That asymmetry between the two measures was found on prose too, and it is worth restating because it is the more useful half of both essays. The phrase count carries a size effect and the run count does not. A collection reporting a falling z/n as it grows may be reporting nothing. A collection reporting a falling r/n is reporting repetition.

The gap also explains a persistent confusion in how these two words are used. A text compressor’s ratio does not distinguish them: a good compressor exploits predictability and repetition alike, and a collection that is strongly one or the other will compress well either way. So “this compresses to eight per cent” is compatible with both, and choosing a structure on that basis is choosing without the information that decides.

The entropy that cannot see a copy is where the two came apart in this collection, and the measurement there was the sharp one: the Burrows–Wheeler transform is a permutation, so H₀ of the transform equals H₀ of the text to fifteen decimal places, and an index priced at n·H₀ therefore cannot shrink when a text is duplicated. That is the same fact this plate shows from the outside — the flat line among two falling ones — and it is the reason a compression ratio is not a structure-selection criterion.

Why the run count has no logarithm #

The reason is a one-line consequence of what a shuffle preserves.

A run of the transform is a stretch of positions that share a right context and agree in the character before them. On a random string over σ symbols, two adjacent rows of the sorted rotations agree in their preceding character with probability 1/σ, independently of n. So the expected number of runs is n(1 − 1/σ) plus lower-order terms, and r/n is 1 − 1/σ — a constant in n.

At σ = 22 that is 0.955, and the measured control sits at 0.906. The gap is the shuffle not being quite uniform: the character frequencies are the text’s, so collisions are more likely than 1/σ, and Σ pᵢ² is 0.094 rather than 0.045. Substituting the actual collision probability gives 0.906 exactly.

That is a small thing and it is the kind of small thing that makes a control trustworthy. A control whose value can be predicted from the collection’s own character frequencies, to three decimal places, is a control that is measuring what it claims to measure rather than an artefact of how it was built.

There is one more thing to extract from the run count’s flatness, and it is a small methodological win rather than a result. Because the control is predictable, it can be checked rather than merely computed: if a shuffled control’s runs per character comes out far from 1 − Σ pᵢ², something is wrong with the shuffle or with the transform. That is a self-test the control provides for free, and it is not available for the phrase count, whose control has no closed form worth relying on.

A control that can validate itself is worth more than one that cannot, and it is a reason to report both measures rather than one. The run count’s control checks the instrument; the phrase count’s control does the work.

What the fall is worth to a structure #

A factor of three in the phrase rate is not an abstraction; it is the size of an index.

A phrase index stores a length, a source and a literal per phrase, plus three permutations of the phrase boundaries — so its size is very nearly proportional to z. A run-length index stores heads and lengths and a handful of directories, so its size is very nearly proportional to r. Halve either and the structure halves.

Across the same sweep the run-length index goes from 18.5 bits a character to 3.4 and the phrase index from 9.4 to 1.6. The entropy-bounded index stays at 6.4 throughout, and the reason is the entropy that cannot see a copy: the transform is a permutation of the text, so its zeroth-order entropy is the text’s, and a structure priced at n·H₀ is blind to arrangement by construction. What is still proportional to n is where the same question was asked of the run-length structure, and found terms that follow the text’s length surviving inside a size that is supposed to follow the runs.

So the three structures sort themselves by which of the two properties they are built on. Two of them charge for arrangement and one charges for predictability, and a collection that is one and not the other will find them a factor of four apart.

The crossing between the flat line and the two falling ones is where this becomes a decision rather than a description. At one copy — an ordinary text with no duplication — the run-length index is 2.9 times the entropy-bounded one and the phrase index is 1.5 times it. Somewhere between one copy and four the two falling lines cross the flat one, and past that point every additional copy widens the gap.

The collection decides which index is small made that argument on one long text and it is unchanged by the document count. What this sweep adds is the control: the crossing is where it is because of the arrangement rather than because of the size, so it does not move as the archive grows unless the archive’s shape changes. An archive that doubles by adding two more releases keeps its crossing. One that doubles by adding unrelated material moves it.

The correction, applied backwards #

There is a use for this beyond describing a corpus, and it is the one that makes the control worth computing every time.

A published number of the form “this collection has z/n = 0.03” is not comparable to another collection’s 0.05 unless the two are the same size. Half the difference could be the logarithm. Computing the shuffled control for each and reporting the ratio makes the two comparable, and the computation costs one shuffle and one parse.

The same applies within a collection over time. An archive that grows will report a falling phrase rate whether or not the new material resembles the old, and a monitoring number that falls for arithmetic reasons is a monitoring number that cannot detect anything. The control removes exactly that.

The alphabet matters to the control and not to the collection, which is a further reason to compute it rather than remember it. On four symbols, log_σ n grows faster with n than it does on twenty-two, so the control falls further over the same sweep and the fraction of the raw curve it accounts for is larger. A rule of thumb calibrated on English will be wrong on DNA in the direction of overstating what the collection is worth.

There is a version of this correction that applies to a claim rather than to a number, and it is the one worth carrying out of this field. The sentence “compressed indexes get relatively better on large collections” is true and is mostly a logarithm. The sentence “compressed indexes get relatively better on collections with more redundancy in them” is true and is the arrangement. The first is often offered as evidence for the second, and this pair of sweeps is what separating them looks like.

A million characters of the same thing is the other half of the pair, and reading the two together gives the calibration: on prose at a million characters the arrangement is worth 1.37, and on sixteen copies of a two-thousand-character base it is worth 3.24. Those are the two ends of the range a real archive sits in, and a collection can be placed inside it with one shuffle and two parses.

What a shuffle does and does not hold #

The control’s whole authority rests on what it preserves, so it is worth being exact.

A uniform shuffle of a text holds the length exactly, the alphabet exactly, and every character’s frequency exactly — therefore the zeroth-order entropy exactly. It destroys every higher-order structure: the conditional entropies, the runs, the phrases, and any repetition at any scale.

What that means for a two-ended check is that anything surviving the shuffle is a property of n, σ and H₀ alone, and anything the shuffle destroys is arrangement. The check therefore has two halves and both are necessary. The control must move, or the comparison is against a constant and proves nothing about the instrument. And the control’s movement must account for less than the raw curve, or the collection is worth nothing beyond its own character frequencies.

Prose passes the first half and barely passes the second. This cell passes both comfortably. A text that failed the second — a raw curve fully explained by its control — would be a text whose falling phrase rate is an artefact, and reporting it as evidence of repetition would be reporting a logarithm.

One limitation of the shuffle is worth naming because it bounds what the control can claim. A uniform shuffle destroys all arrangement, so what survives it is arithmetic — but the converse does not follow. Something destroyed by the shuffle is not necessarily repetition in the sense a structure exploits; it could be any higher-order structure at all, including the kind of local predictability a Markov model captures and a copy-based parse does not.

So the control separates arithmetic from arrangement and does not separate the two kinds of arrangement. Doing that needs a second control — a text generated from the collection’s own conditional distributions, which holds the local structure and destroys the long-range copies. What the generated collection was right about built that control for a different purpose and it would work here; it is not applied in this sweep, and the consequence is that 3.24 is an upper bound on what the copying is worth rather than an exact figure for it.

Where the two measures disagree about a collection #

One last comparison is worth drawing, because it is the case where the two measures give different advice and a reader has to choose.

Across this sweep r/n falls by 3.40 and z/n by 4.71, so the phrase count falls further — but 1.45 of the phrase count’s fall is the logarithm and none of the run count’s is. Corrected, the two are 3.40 and 3.24: the same number to within five per cent.

That agreement is not automatic and it is the useful part. The two measures are computed by entirely different machinery, count entirely different objects, and are usually quoted as though one implied the other. On this collection they agree about how much the arrangement is worth, once the arithmetic is taken out of the one that carries it. On prose they did not: r/n fell by 1.39 with a flat control and z/n by 1.37 after correction, which also agreed — and the raw figures, 1.39 and 2.34, did not.

So the corrected numbers agree on both collections and the raw numbers agree on neither. That is about as strong an argument for computing the control as this collection is going to produce, and it arrived as a consistency check rather than as the thing being looked for.

The one quantity that neither measure predicts is the one one copy per document is one occurrence per document is about. A collection can fall by a factor of three in both measures and leave its occurrences-per-document exactly where it started, because that number is a property of the base rather than of the copying. Three measures of a collection, two of which agree after correction and one of which is independent of both.

The convention this settles #

The rule this collection now follows is one sentence and it has been arrived at twice from opposite directions.

A sweep whose axis is size draws a control, and the check is two-ended. The control holds n, σ and H₀ and destroys the arrangement; it must move, and its movement must account for most or little of the raw curve, and which of those it is is the finding.

On prose the answer was “most”, and the honest headline became 1.37 rather than 2.34. Here the answer is “little”, and the honest headline is 3.24 rather than 4.71 — a smaller correction, on a larger number, in a case where the raw figure would not have been badly wrong.

That the correction is small here is exactly why it had to be computed. A convention that only gets applied when the answer is expected to change is not a convention; it is a rationalisation with a procedure attached. The two sweeps together are the evidence that the procedure is worth its cost, and the cost is one shuffle.