A million characters of the same thing

Every number this collection has published about real text was measured on 24,576 characters.

That was not a choice about statistics. The measure the whole argument turns on is the phrase count of a self-referential parse, and computing it by comparing characters is quadratic — so twenty-four thousand was what a figure could afford, and a corpus of a hundred and forty thousand was a thing nobody could weigh.

The parse in one pass of the text removed the quadratic term. The ceiling moved, and nobody went back to look.

This is what is behind it.

The second corpus, and why it is a second one #

There are now two frozen objects, and the first is not touched.

The reason is the one that made it frozen in the first place: a measurement about a moving collection is true on the day it is taken and unreproducible afterwards. Every essay in this strand that quotes a number about real prose quotes a number about a specific 326,531 characters, and regenerating that object to make it bigger would turn each of those numbers into a claim about something that no longer exists.

So the second corpus is a separate object with separate parts, and it answers what the first was too small to ask:

A million characters of prose. Eighty-two essays in slug order, figures and tables removed, taken until the total first passed a million. 1,004,741 characters — forty times the size every measurement in this strand was taken at.

Two thousand short documents. Every figure caption in this collection, one document each: 2,214 documents averaging 247 characters. That is the shape a document collection usually has, and two thousand documents of two hundred characters is what it does to every structure built over one.

A longer version history. Fourteen successive revisions of one file rather than ten, because the shape of a real history’s depth needs generations to be a profile over.

The two measures, swept #

The two numbers this field summarises a collection with are r, the number of runs in its Burrows–Wheeler transform, and z, the number of phrases in its parse. Both are counts of repetition and neither is entropy — that distinction is the entropy that cannot see a copy, and it is why a compressed index is measured in these two and not in bits per symbol.

Per character, both of them fall as the collection grows.

z/n falls from 0.2532 at 8,192 characters to 0.1082 at a million — a factor of 2.34. r/n falls from 0.5155 to 0.3699, a factor of 1.39. Read alone, that says a real collection of essays becomes twice as repetitive as more of it arrives, which is a striking claim about prose and is not what happened.

The control, and what it eats #

The upper line on that plate is the same characters in a random order.

A shuffle holds the length exactly, the alphabet exactly and the zeroth-order entropy exactly — 4.39 bits a symbol at 8,192 characters and 4.41 at a million, which is as flat as anything in this collection gets. What it destroys is the arrangement, and the arrangement is the only thing the two measures are supposed to be about.

The shuffle’s phrase count per character falls too: 0.4508 to 0.2648, a factor of 1.70.

That is not a defect in the control. It is a property of the measure. A parse of any text at all produces roughly n / log_σ n phrases, because a phrase can be as long as the longest substring that has occurred before, and in a random text over σ symbols that length grows like log_σ n. So most of the fall in z/n is the logarithm in the denominator, arriving on schedule and having nothing to do with whether the collection repeats itself.

Dividing one by the other leaves 1.37 — the amount by which a real collection of essays genuinely does repeat itself more as it grows, over two orders of magnitude. It is a real effect and it is a fifth of the headline.

The measure that needs no correction #

The runs measure behaves differently, and the difference is worth a paragraph because it changes which of the two numbers is worth quoting.

A shuffled text has almost exactly 0.93 runs per character at every size on the plate. The transform of a random string is a random string, and a random string over ninety-odd symbols has a run boundary at nearly every position however long it is — there is no logarithm in it to move.

So r/n’s fall of 1.39 is entirely the collection, and z/n’s fall of 2.34 is mostly not. The two measures are usually quoted side by side as though they were two views of one property, and on this sweep one of them needs a control and the other does not.

That asymmetry is the strongest argument this sweep produces for drawing controls at all. Nothing about the definitions of r and z says which of them carries a size effect; only the measurement does.

The alphabet is not a constant either #

The second thing forty times the size moves is σ.

Sixty-six symbols in the first 8,192 characters, 115 in the first million. That is Heaps’ law arriving in the alphabet rather than in the vocabulary, and it is not a curiosity: σ is inside a logarithm in every size this field measures. A packed text is n⌈log₂ σ⌉ bits. A wavelet tree is ⌈log₂ σ⌉ levels deep, so rank is the only thing it does costs that many bit-vector operations. An interval extension in a bidirectional index costs σ ranks unless every child at once is available.

Between 64 and 128 symbols the packed width steps from six bits to seven, and every character of the collection pays it. The step is visible on the plate as the moment the whole collection got 17% larger for holding one more distinct symbol.

How the sweep is taken, and what it holds fixed #

The axis is a prefix. Each point is the first n characters of the same collection, not a fresh sample of n characters, and that choice is doing work worth naming.

A fresh sample at each size would confound two things: the collection getting larger, and the collection getting different. Essays arrive in slug order here, which is alphabetical and is as close to arbitrary as an ordering of a real collection gets — but any ordering has structure, and drawing a hundred thousand characters at random from the whole would mix documents from all over it. A prefix has the property the sweep needs instead: every point is a superset of the one before, so a phrase counted at 131,072 characters is still a phrase at 262,144, and the curve is one collection observed as it accumulates rather than eight collections compared.

The cost is a bias worth stating: the first eighty-two essays in slug order are not a random eighty-two, and prefixes of a prefix share their first document. Neither matters for what is being asked here, because the question is about a rate and not about the collection’s identity — but a plate about which subject repeats itself most would have to be drawn the other way.

What is held fixed is more interesting than what varies. The shuffle at each size uses the same permutation generator seeded once, so the control at 262,144 characters is not a re-roll of the control at 131,072. The alphabet is measured on the same prefix that everything else is measured on, which is why the σ curve and the z curve can be read against each other. And every one of these numbers comes out of the same two constructions the rest of the strand uses — the transform for r, the automaton parse for z — rather than out of an approximation chosen because a million characters is large.

What the join costs at this size #

There is a second number in every one of these collections that is not a property of the text: the separator between documents.

Eighty-two documents need eighty-two separator symbols if every suffix has to be comparable, and the alphabet goes from 115 to 183 — across the power of two at 128, so ⌈log₂ σ⌉ steps from seven bits to eight and the packed collection gets 14.3% larger. On twelve documents the same construction cost nothing at all, because 96 and 97 sit on the same side of 128.

That is the same step the alphabet plate shows, arriving from a different direction: once from the text growing and once from the collection being cut into more pieces. Both are counted in the same place and neither is visible in a size quoted as n log σ with σ treated as a property of the language.

What the old rate would have said #

Put those together and the arithmetic is uncomfortable.

A phrase count extrapolated from the old size over-predicts by 44%. A run count over-predicts by 18%. The alphabet under-predicts by 46%. Only the packed width survives, and it survives by luck: ⌈log₂ σ⌉ happens to be 7 at both sizes, so the prediction is exact and would have been out by a seventh had the sweep started a little lower.

None of those errors is a mistake in the earlier measurements. Each of them is exact about the object it was taken on. What they are not is a rate, and every one of them was quoted as though it were: r/n is 0.45 on real prose, a phrase costs about five characters, the alphabet is around eighty symbols. Those sentences are all true at one size.

What did not move #

Three things held, and they are the reason the earlier work stands.

The ordering of the parts. Prose is still the least repetitive of the three, a version history still the most, source code still between them. Every conclusion in this strand that was about which part behaves how is unaffected — the ranking is stable across the whole range.

The generated collection is still not a model of a real one. The dial that has no setting showed that no divergence reproduces a real history’s two measures at once, and the gap does not close with size — it is a gap about where the edits are and not how many, so scaling both sides changes nothing about it.

Zeroth-order entropy is flat. 4.385 bits a symbol at 8,192 characters and 4.410 at a million. A measure that cannot see a copy does not notice that there are now forty times as many copies to see, which is the whole reason this field measures r and z instead.

What a million characters cost #

Nothing, which is the part worth stating plainly.

The suffix array of a million characters takes about two seconds here; the parse takes 1.8; the transform and its run count come out of the same construction. The whole sweep on this page — seven sizes, each measured twice, once shuffled — is under a minute.

That is the shape of this whole result. The instrument arrived, the ceiling moved, and the question of whether numbers taken under the old ceiling still held was a function call that nobody had made. It took one afternoon and it moved four of the five numbers this strand quotes.

What a reader should take from it #

Three things, in the order they bind.

A rate measured at one size is a measurement, not a rate. If a quantity has a logarithm in it — and z/n does, r/n does not, and neither definition says so — then quoting it per character is quoting a number that depends on how much there was.

A control is not optional on a sweep whose axis is size. The shuffle costs one line of code and it took a 2.34 down to a 1.37. Without it this page would have reported that essays become twice as repetitive as a collection of them grows, which is a claim about writing rather than about arithmetic and would have been wrong.

And the alphabet grows. Everything in this field is logarithmic in σ, everything treats σ as given, and σ is a function of how much text has been read. An index has a size, and part of that size is a number that was still moving when the last measurement was taken.

The statistic that would not have needed a control #

The control removes the size effect by division, which needs a second measurement. The same effect can be removed by multiplication, which needs none — and doing both is worth it, because they agree and the agreement is a check on each.

If the logarithm in $z \approx n/\log_\sigma n$ is what makes $z/n$ fall, then $z\ln n / n$ should be flat. Evaluate it on the control: $0.4508 \times 9.011 = 4.06$ at 8,192 characters and $0.2648 \times 13.816 = 3.66$ at a million. A fall of 1.11 across two orders of magnitude, against the raw rate’s 1.70.

So multiplying by $\ln n$ takes a seventy-per-cent drift down to eleven, on a text with no arrangement in it at all. That is the size effect, removed by arithmetic rather than by a shuffle.

Now the real collection: $0.2532 \times 9.011 = 2.28$ and $0.1082 \times 13.816 = 1.50$, a fall of 1.53. Divide out the control’s residual 1.11 and what is left is 1.38 — which is the 1.37 the ratio of the two lines gives, to within the rounding.

Two routes to the same number. One divides a measurement by a measurement; the other multiplies a measurement by a formula and then divides by a much smaller residual. They agree, which is evidence about both — the logarithm really is the mechanism, and the shuffle really is measuring what it claims to.

That has a practical consequence the page’s three closing rules do not quite reach. A rate measured at one size is a measurement, not a rate is right, and it leaves a reader with nothing to quote. The thing to quote is $z\ln n/n$, which is flat to eleven per cent on structureless text and therefore carries most of the way between sizes on its own. Quote $z/n$ and a reader extrapolating four-fold is out by a third before the collection’s own repetition is considered.

It also prices the earlier work more precisely than the 44% figure does. Of that over-prediction, $\ln(10^6)/\ln(24{,}576) = 1.37$ is the logarithm, and the residual — about five per cent — is the collection genuinely repeating itself more over that range. Thirty-seven of the forty-four points were arithmetic and five were prose, which is a sharper statement of what the earlier numbers got wrong than they were not rates.

And it says nothing about $r$, which is the point of measuring both. The runs measure has no logarithm to multiply out — its control is flat at 0.93 — so $r/n$ is already the right thing to quote and needs neither a shuffle nor a correction. The half of a fall that is the logarithm is the other half of this arithmetic, and a corpus that was not generated is the object both are measured on.

What is still not measured here #

Three things, and the first is the one a reader is most likely to want.

A million characters of a repetitive collection. Prose is the case the compressed structures are not for, and it is the case this page is about, because it is the one an essay collection can supply a million characters of. A real version history of that size exists — every large program has one — and nothing here says whether z/n on a repetitive collection falls with size the way it does on prose, or falls faster, or stops falling once the copies dominate. The arithmetic says it should behave differently: the logarithm in z ≈ n / log_σ n comes from how long a random match can get, and in a collection of near-copies the matches are long for a reason that has nothing to do with n.

A control for the runs measure that is not a shuffle. A shuffle destroys all the arrangement at once. Between the real order and a random one there is a whole family of partial destructions — shuffle within documents, shuffle the documents, shuffle the sentences — and each of them would say which scale of structure the transform’s runs are actually counting. That is a sweep of one parameter and it is not drawn anywhere in this collection.

And what a growing alphabet does to a structure that has already been built. Every size on this page is computed for a collection measured whole. A real index is built once and added to, and the symbol that arrives at character 900,000 and pushes σ past a power of two makes every previously packed character the wrong width. Nothing in this field’s usual accounting has a term for that, and this sweep is the first thing here to show that the moment is not hypothetical: it happens twice inside one collection of essays.

Where this sits #

Four pages on the corpus at scale. This one is the sweep. The half of a fall that is the logarithm is what the control eats. Two thousand documents of two hundred characters is the other shape parameter, and the crossing that never arrives is what that shape does to the structures built over it.