The half of a fall that is the logarithm

Here is a sentence that is true, checkable, and almost entirely misleading.

Phrases per character on a real collection of essays fall from 0.253 to 0.108 as the collection grows from eight thousand characters to a million — so a larger collection of real prose is more than twice as repetitive, per character, as a small one.

Every number in it is measured. The conclusion is worth about a fifth of what it claims.

What a shuffle keeps #

The control is one line: take the collection, permute its characters, measure it again.

That is a violent thing to do to a text and a very gentle thing to do to its statistics. A shuffle holds the length exactly. It holds the alphabet exactly — the same 115 symbols, each occurring the same number of times. It therefore holds the zeroth-order entropy exactly, at 4.41 bits a symbol, which is the quantity a compressor with no memory is bounded by.

What it destroys is order, and order is the only thing the two measures of repetition are supposed to be about. Repetition is not entropy is the whole reason this field counts runs and phrases rather than bits per symbol: a text and its shuffle have the same entropy and one of them is a hundred copies of a sentence.

So the shuffle is the right control. Anything that survives it is a property of the alphabet and the size, and anything that does not is the arrangement.

The shuffle’s phrase count per character falls from 0.4508 to 0.2648.

Why the control moves #

It moves because the measure has a logarithm in it, and nothing in the definition of a phrase says so.

A phrase in this parse is the longest string starting here that has occurred earlier — the construction is the phrases a text copies from itself, and its whole point is that it counts copies rather than symbols. In a text with no structure at all, the longest previously-seen string starting at a given position is about log_σ n characters long: there are σ^k strings of length k, so once n exceeds σ^k every one of them has probably occurred, and matches get longer as the text gets longer for reasons of counting rather than of content.

That makes z ≈ n / log_σ n on a random text, so z/n ≈ 1/log_σ n — a falling curve on any text at all, structure or no structure. Over the range on the plate, log_σ n goes from about 2.2 to about 2.9, which predicts a fall of a factor of 1.3; the measured control falls by 1.70, because the real alphabet is skewed and the effective σ is smaller than 115.

The point is not the exact coefficient. It is that the axis of the sweep is inside the measure.

Divide one by the other and the real effect is 1.37 over two orders of magnitude. A real collection of essays does repeat itself more as more of it arrives — the vocabulary saturates, the same phrases return, and a longer prefix of the collection is genuinely a better dictionary for its own next essay. That is a finding. It is not a factor of 2.34.

The other measure does not need this #

The instructive part is that the same treatment applied to r says something completely different.

The transform of a random string is a random string, and a random string over a large alphabet has a run boundary at nearly every position no matter how long it is. There is no logarithm in r/n to move, so the control is a horizontal line and the measured fall of 1.39 is the collection, all of it.

Two measures, quoted side by side in every account of compressed indexing, described in the same breath as measures of repetitiveness, and one of them carries a size effect that swamps the signal while the other does not. Nothing in either definition indicates which. The only way to find out is to shuffle.

It matters because both numbers are load-bearing. An index with z in its size is built on the phrase count and a function with r pieces on the run count, and a claim that a structure is proportional to a measure inherits whatever that measure is proportional to. A self-index quoted as O(z log n) on a collection whose z/n has a logarithm in it is quoted against a quantity that shrinks per character as the collection grows — which flatters the structure at large sizes for a reason that has nothing to do with the structure.

Why this is in the taught-wrongly field #

Because the error is not in the arithmetic and cannot be caught by checking it.

Every number on these plates is exact. The parse is verified to produce back the text it parsed, phrase for phrase; the transform’s run count is checked against a second construction; the check must reject is the habit that keeps both honest. A reader auditing this work would find nothing wrong, because there is nothing wrong until a rate is quoted and the rate has a hidden argument.

That is the general shape and it is worth naming: a per-unit quantity is only a rate if the unit does not appear inside it.

Comparisons per element is a rate for insertion sort and is not one for merge sort, because the second has a log n in it and the first does not. Cache misses per access is a rate at one working-set size. Bits per character out of a compressor is a rate only if the compressor’s model is fixed, which is exactly what a compressor’s model is not — compression is prediction, and a predictor that has read more is a different predictor.

The measurements this collection published on the first frozen corpus are all of this shape. They were taken at one size, they are correct at that size, and several were phrased as though they held per character.

What the control does not fix #

Two things, and both are limits on this page rather than on the method.

A shuffle is the most violent control available. It destroys every scale of structure at once: the letter pairs, the words, the sentences, the documents. What is left over is therefore the sum of everything the arrangement buys, with no way to say which scale it came from. A gentler control — shuffle the sentences within each document, or shuffle the documents and keep their contents — would separate them, and the difference between those curves is what would say whether the phrase count is seeing repeated words or repeated passages.

That family of partial shuffles is a sweep of one parameter and it is not drawn here.

And the control has to be the same object. A common alternative is to compare against text drawn from a model — a Markov chain fitted to the collection, or a generator with a divergence dial. Those are useful and they are not controls, because they differ from the collection in every respect at once.

The dial that has no setting is the long version: the generator’s two measures ask for settings a factor of 1.40 apart, and the reason is the shape of its edits rather than their number. A model that is wrong in a known way is still a model. A shuffle is the same data.

The same distinction decides what what the generated collection was right about could conclude. A quantity that transfers from the model to the real collection is one the model gets right because of arithmetic they share — the count of windows spanning a join is (m − 1)(d − 1) on both, exactly. A quantity that does not transfer is one the model determines by a parameter somebody chose. Neither is settled by comparing the two collections; it is settled by knowing which part of each number is a property of the definition.

Reading the plates the other way #

If the control eats most of the fall, what is the honest headline?

Real prose repeats itself, and the effect is small and grows. At eight thousand characters the collection’s parse is 1.78 times shorter than a shuffle’s; at a million it is 2.45 times shorter. Both numbers are worth having, and neither of them is what a per-character rate reports.

The runs measure is the one to quote when the question is about arrangement, because it needs no correction on this axis. That is a specific, actionable difference between two numbers usually treated as interchangeable, and it fell out of drawing a control that took an afternoon.

Neither number is entropy, and this is a third demonstration of it. The measure that cannot see the alphabet makes the point from one side — a phrase count says nothing about how wide a symbol is — and the entropy that cannot see a copy from the other. What this page adds is that r and z do not agree with each other about what the axis of a size sweep does, so they cannot both be measuring the one property the word “repetitiveness” names.

And the size a number was taken at belongs beside the number. Not as provenance, as a parameter. Every quoted r/n and z/n on this site now carries the length it was measured on, for the same reason every bound here carries the model it was proved in: a guarantee names its model, and a measurement names its n.

What the sweep says about the structures built on these numbers #

There is a practical consequence, and it lands on the sizes rather than on the prose.

Every compressed index in this collection is quoted in one of the two measures. An index larger than what it indexes is the starting point — a suffix array is n⌈log₂ n⌉ bits and the text is n⌈log₂ σ⌉ — and everything after it is an argument about replacing that with something proportional to r or to z. Those arguments are all correct. What this page changes is how their numbers should be read as a collection grows.

An index proportional to z, on real prose, gets relatively smaller as the collection grows, and about three quarters of that improvement is the logarithm rather than the collection. An index proportional to r improves too, and all of that improvement is real. So two structures whose sizes look comparable at twenty-four thousand characters do not stay comparable, and the direction of the drift is knowable in advance from which measure each is quoted in.

That is not a criticism of either family. It is the reason a size plate on this site carries the text it was measured on and the length of it, and the reason an index has a size is a theme rather than a remark.

Three more places the same hidden argument sits #

Once the shape is named it is easy to find, and this collection has been careless about it in at least three other places worth putting on the record.

Occurrences per document. The cost that is the size of the answer turns on how many times a pattern occurs inside each document holding it, and the crossing between two listing methods was quoted as a number of occurrences. That number is not a property of a collection: it is a property of a collection and a pattern length, because a longer pattern occurs less often. Both were fixed when it was measured and only one was reported.

Bits per point in a grid. The runs a permutation does not leave prices a compressed grid against the information-theoretic floor log₂(z!), which grows faster than z — so the share of the floor a coding wins is a function of how many points there are, and the sixteen per cent quoted there is a sixteen per cent at one size.

And phrases per copy. The repetition sweeps in this field hold the base text fixed and add copies, so the axis is copies and n moves with it. That is the right experiment for the question being asked, and it means the curve mixes “more copies” with “a longer text”, exactly as this page’s does. The difference is that the copies axis makes the intent obvious and the characters axis does not.

None of the three is wrong. All three would read differently with a control drawn beside them, and the control is cheap in every case.

The check that would have caught it #

There is one, and it is cheap enough that it should probably be standing on every sweep whose axis is size.

Measure the control at both ends. If it moves by more than a little, the measure has the axis inside it and the raw curve is not reporting what it appears to report. That check is four lines here, it runs on every build, and it fails if the shuffle’s fall ever accounts for less than the amount this page claims — which is what makes the 1.37 a number somebody could refute rather than a number somebody wrote down.

The other three bars on that plate are the same mistake in three more places. A run count extrapolated as a rate is out by 18%, a phrase count by 44%, an alphabet by 46%. The one that survives does so because ⌈log₂ σ⌉ happened not to cross a power of two, which is luck rather than method.

Which alphabet the logarithm is over #

The prediction of 1.3 against a measured control of 1.70 is put down to the effective alphabet being smaller than 115, and that is right in direction and the wrong variable. What matters is not that it is smaller — it is that it does not move.

The 1.3 comes from evaluating $\log_\sigma n$ at each end with each end’s own alphabet: $\log_{66} 8192 = 2.15$ and $\log_{115} 10^6 = 2.91$, a ratio of 1.35. Feeding the growing symbol count into the prediction is what makes it small, because a wider alphabet lengthens the logarithm and so damps the fall.

Hold the alphabet fixed instead and the $\sigma$ cancels entirely: the ratio becomes $\ln 10^6 / \ln 8192 = 1.533$, whatever $\sigma$ is. Against a measured 1.70 that is an 11% residual rather than a 26% one.

And a fixed alphabet is the right model, because the alphabet the parse actually sees is fixed. The symbol count runs 66 to 115 — a rise of 74% — while the zeroth-order entropy runs 4.385 to 4.410 bits, so the effective alphabet $2^{H_0}$ goes from 20.9 to 21.3: two per cent, across two orders of magnitude.

The fifty new symbols are rare punctuation and stray accents. They widen $\sigma$ and carry no probability, so they lengthen a matched string not at all — a parse looking for the longest previously-seen prefix is competing against an alphabet of about twenty-one, and has been at every size on the plate.

Which sharpens the page’s own accounting by halving what is unexplained. Of the raw 2.34 fall, 1.53 is the logarithm — computable from nothing but the two lengths — 1.11 is whatever the shuffle does that the logarithm does not, and 1.37 is the collection. The middle term is small enough to be finite-size effects in the parse’s early behaviour, and it is what the earlier attribution was absorbing into a vaguer “effective σ”.

It also says which alphabet belongs in any of these formulas, which is a fact worth having wherever this field writes $\log_\sigma$. A symbol count is the wrong argument and an entropy-derived alphabet is the right one, and the two disagree by a factor of five here and diverge as a collection grows. The measure that cannot see the alphabet is about a measure that ignores $\sigma$ entirely; this is the complementary case, where a measure depends on $\sigma$ and the $\sigma$ in the formula is not the one in the data. The entropy that cannot see a copy is the quantity that turns out to be the right argument, in the one role it is good for.

What is left over #

The honest summary of this page is three sentences and a caveat.

Real prose does repeat itself more as more of it arrives, by a factor of 1.37 over two orders of magnitude. The raw phrase count per character says 2.34, and the difference is a logarithm that belongs to the measure rather than to the collection. The run count needs no such correction, which makes it the better of the two numbers to quote when the question is about arrangement rather than about size.

The caveat is that 1.37 is itself measured on one collection of one kind of text, at one alphabet, with one control. A shuffle is the strongest control available and the least informative: it says how much the arrangement is worth in total and nothing about which scale of arrangement it came from. The gentler controls — shuffling sentences inside documents, shuffling documents inside the collection — would say, and they are a sweep of one parameter that nothing here has drawn.

What the page is really about is smaller and more portable than any of those numbers. A rate is only a rate if its own axis is not inside it, and the only reliable way to find out is to measure the thing that has everything except the property being claimed.