A corpus that was not generated

Three essays in a row ended with the same sentence, and it was the oldest thing on this collection’s list of what was missing.

Every collection here is copies or near-copies of a generated text, and the properties the document strand is about — how many generations of copying, how many documents, what alphabet — are exactly the ones a synthetic corpus does not settle.

This is a corpus that was not generated, and the first four measurements taken on it.

What the generator does #

One line and one dial. Take a text; make k copies; replace a fraction of each copy’s characters with random ones. A collection is fixed by three numbers — the base length, the number of copies, and that fraction — and every measurement in five strands has been taken on one.

It is exact, it is reproducible, and it made every figure in those strands possible. Nothing below is a criticism of it. What follows is a question about what its numbers mean.

The three parts, and why there are three #

The corpus is frozen: written down once and never re-read from anywhere. A measurement about a moving collection is true on the day it is taken and unreproducible after, and this collection’s rule is that a number in an essay is a number a reader could get back.

Its three parts repeat for three different reasons, which is the whole reason there are three.

Prose — twelve essays. Repeats a vocabulary: the same few thousand words in different arrangements, with almost no long repeated stretch. Twelve documents, 144,606 characters, 95 distinct symbols.

Source — eight modules of the program that draws this collection’s figures. Repeats a form: long identifiers, boilerplate lines, the same indentation on every line of every file. Eight documents, 106,276 characters, 111 symbols.

Revisions — ten successive versions of one file, oldest first, as they were written. Repeats almost everything, with localised changes. Ten documents, 75,649 characters, 79 symbols. This is the case every compressed index in this collection is built for, and the only one of the three whose documents stand in a known relation to each other.

What made it measurable #

The measure this strand turns on is the phrase count of the parse, and computing it by comparing characters is quadratic. That is why every measurement in this collection before now was taken on a few thousand characters, and it is why a corpus of a hundred and forty thousand was not a thing anybody could weigh.

The parse in one pass of the text is the construction that removed it, and it landed one strand before this one. The whole of this corpus is parsed in the time one of those small texts used to take.

That is worth stating because it is the reason this strand exists now rather than long ago. The instrument came first and the question was already there.

Why three parts rather than one #

The temptation with a real corpus is to take one and call it real. Three were taken because the word “real” hides a distinction this collection needs.

A compressed index’s whole argument is that a repetitive collection is small. Repetitive is a property, not a synonym for real, and most real text is not repetitive: twelve unrelated essays share their vocabulary and almost nothing else. If the corpus had been prose alone, every structure in these strands would have looked bad on it and the conclusion would have been that the structures do not work on real data — which is false, and would have been an artefact of choosing the one real case they are not for.

Three parts spanning the range make the range visible instead. Prose is the case the structures are not for; a version history is the case they are for; source is in between and is the one real collections most often actually look like.

The first measurement #

Runs of the transform and phrases of the parse, both divided by the length of the text so that three parts of different sizes sit on one plate.

Only the version history is repetitive in the sense this field means. Twelve unrelated essays have four times the runs per character that ten revisions of one file do, and prose and source are indistinguishable from each other on both measures.

That is not surprising and it is worth having measured, because the strands built on compressed indexes have been measuring collections whose repetitiveness was set by a dial, and this says which of the three real cases the dial has been imitating.

The alphabet, which is the largest difference #

A generated text here draws from 22 symbols. Real prose has 87, real source 98, a version history 75.

Punctuation, digits, capitals, brackets, quotation marks, the characters nobody thinks of as part of a text. Between three and four and a half times the alphabet, on every part.

It matters more than it sounds, for two reasons.

The alphabet sits inside a logarithm in every size this field measures — a packed text is n⌈log₂ σ⌉ bits, a wavelet tree is ⌈log₂ σ⌉ levels deep, a backward search step costs a symbol rank whose price is the code length. Four times the alphabet is about two extra bits a character everywhere.

And a headline in the document strand turns on whether adding a symbol crosses a power of two. At 22 symbols it does; at 87 nothing near it does. Documents that are not the same length is where that comes apart.

What is frozen, and how #

Twelve slugs, eight module names and ten dated revisions, listed explicitly and written out in full. Not a rule for selecting documents — a list, so that adding an essay to this collection changes nothing here.

Truncation, where it is needed, scales every document by the same factor rather than cutting each to a common length. That is a deliberate choice and it is what documents that are not the same length is about: a corpus whose documents are all cut to one length is a corpus whose length distribution has been thrown away, and the distribution is one of the things this strand exists to measure.

Every document is kept whatever the factor, for the same reason.

What a real collection looks like in the small #

The revision history is the part most worth looking at, because it is the case the compressed-index strands are built for and the one the generator claims to model.

Ten revisions, from 1,086 characters to 4,079, growing monotonically — a file that was edited across ten occasions and mostly got longer. The generated collection matched to it has ten documents of exactly 2,458 characters each.

That difference is not cosmetic. Several of the real pairs differ in nothing at all over their common prefix and simply have a few hundred characters appended; none of the generated pairs does, because the generator’s model of an edit is a substitution and a substitution does not change a length.

What the numbers mean, in units a reader can hold #

Runs per character and phrases per character are compact and abstract, so it is worth converting them once.

A version history of 24,580 characters has 3,103 runs in its transform and 1,642 phrases in its parse. That means an index proportional to the run count is holding about three thousand things where the text has twenty-four thousand characters — a factor of eight — and a phrase index is holding about sixteen hundred.

Twelve essays of the same length have 12,065 runs and 5,234 phrases: a factor of two, not eight. An index proportional to either measure is barely smaller than the text it indexes, which is an index larger than what it indexes in its natural habitat.

The structures work, on the collection they are for, and the collection they are for is a version history. That is the plainest thing this corpus says.

The measures do not see the order #

One thing that might have been expected and is not there.

A version history has an order, and the intuition is that a compressed index is small on it because consecutive versions sit next to each other. Shuffle the documents into an order they were never in — keeping every document, every character, every symbol — and the measures move by 0.06% in runs and 0.4% in phrases.

They do not see it. Both measures find a previous occurrence wherever it is, and every version of this file resembles every other, so which one a phrase copies from moves and how many phrases there are does not.

That matters because it is the assumption under every collection in five strands: the generated ones are exchangeable copies, and this says the real one is exchangeable too, for the two quantities being measured. It is the first thing this corpus has confirmed rather than contradicted.

The control that must fail #

A measure of repetition has to be shown to be measuring repetition, and the sharpest available control is a shuffle of the characters.

Shuffling a text’s characters keeps its length, its alphabet and every symbol’s frequency exactly — so its zero-order entropy is identical to the last bit — and destroys every structure above that.

Measured on the revision history: the run count multiplies by 7.42 and the phrase count by 6.09, with the zero-order entropy unchanged.

That is the check that licenses everything else here. The entropy that cannot see a copy is the essay that first made the point in this collection — a text and its shuffle have the same entropy at every order the text is long enough to estimate — and this is the same demonstration on data nobody constructed.

Why a frozen corpus rather than a live one #

There is an obvious alternative — read the collection as it stands whenever a figure is drawn — and it was rejected for a reason worth recording.

Every number in this strand would then be a number about whatever the collection held on the day, and no reader could reproduce one. Worse, the numbers would drift: this collection grows by twenty essays at a time, so the prose part’s alphabet, length distribution and repetition would all move, and an essay’s claim about a factor of four would become a claim about whatever factor happened to hold later.

A frozen corpus is a fixed object. Its provenance is stated, its documents are listed, and its measurements are reproducible in the only sense that matters — the same input produces the same number.

The cost is that it ages. In a year the source part will describe a program that has changed and the revision history will stop at revision ten. That is the right cost to pay: an aged measurement that is reproducible is worth more than a current one that is not.

The ratio between the two measures is what transfers #

The table reports two measures per collection and reads them down the columns. Reading it across — dividing one by the other — gives a quantity that is far more stable than either, and it is where the generator’s mismatch shows up as a single number.

Twelve essays: 0.491 runs a character against 0.213 phrases, a ratio of 2.31. Eight source modules: 0.461 against 0.210, 2.20. Ten revisions: 0.126 against 0.0668, 1.89. The matched generated collection: about 0.118 against 0.048, 2.46.

So across four collections whose absolute repetitiveness spans a factor of four — prose at half a run a character, a version history at an eighth — the ratio between the two measures moves by 30%. The measures are nearly proportional, and the constant of proportionality is a much smaller thing than either measure.

That is the useful form of the relationship this strand keeps asserting. A collection with more runs per character has more phrases per character is true and weak; the two are within 30% of a fixed multiple of each other across every collection measured is the same observation with a number, and it is a number a reader can check against their own text in one pass.

It also locates the generator’s error precisely. The generated collection has the highest ratio of the four, 2.46, and the version history it is meant to model has the lowest, 1.89 — so the model produces too many runs for the phrases it produces, by about 30%.

Which is the same fact the dial that has no setting reports in a different shape. There the generator is fitted to the real collection twice, once on each measure, and the two settings come out a factor of 1.40 apart; here the mismatch is one ratio against another, 2.46 against 1.89, which is a factor of 1.30. Same direction, comparable size, and one number instead of two fitted parameters.

That suggests the calibration a future generator should be checked against. Fitting the divergence to reproduce $r$ leaves $z$ wrong; fitting it to reproduce $z$ leaves $r$ wrong; and fitting it to reproduce $r/z$ would catch the shape error in one comparison rather than requiring two fits and a discrepancy between them. It would not fix the generator — the model’s edits are scattered where real edits are localised, which is a structural difference no dial reaches — but it would report the failure in a single number computable from one pass over each collection.

And it explains why the relationship survives where the values do not. A run and a phrase are both bounded below by the same thing: the number of distinct contexts the text contains. So a collection’s two measures are two views of one property, differing in how they count it, and the ratio between them is a property of how the repetition is arranged rather than of how much there is. The collection decides which index is small is where the two measures decide between two structures; this is the quantity that says when they will disagree.

What this corpus cannot settle #

Three limitations, stated because a real corpus invites more confidence than it earns.

It is one corpus. Three parts, thirty documents, three hundred and twenty thousand characters. Every number here is about it, and a different version history would give different numbers.

Its prose is unusually uniform. The twelve essays vary in length by a factor of 1.26, which is the narrowest spread of the three parts and is an artefact: they come from a collection that requires every essay to sit inside a length band. Real prose corpora are not like that.

And it is small. A hundred and forty-five thousand characters is a large collection by this site’s standards and a small one by any real measure. Nothing here says what happens at a million characters or at a hundred million, which is where the structures this collection weighs are actually deployed.

The one thing that is not a limitation #

It is worth defending one choice that looks like a weakness.

The prose part is twelve of this collection’s own essays. That is self-referential, and a reader might reasonably wonder whether a collection measuring its own text is measuring anything.

It is, and the self-reference is incidental. What the prose part is for is to be natural language written by people about a technical subject, with the punctuation, the numbers, the capitals and the varied vocabulary that comes with it. Any twelve documents of that kind would do; these were to hand, their provenance is exactly known, and they can be listed by name so that a reader can see what was measured.

The one place the self-reference does bite is the length uniformity, and that is stated above rather than hidden: these essays are unusually similar in length because they were written to a standard, and a corpus of twelve arbitrary essays would have a wider spread.

What is checked #

The corpus is what it says: three parts, thirty documents, none empty, none unlabelled, with their character counts and symbol counts asserted rather than described.

The documents are uneven, in at least one part, by a factor of more than 1.5 — and the matched generated collection is required to have a length spread of exactly one, which is the assertion that makes the comparison mean something.

The alphabets differ by more than a factor of two on every part, asserted in that direction so that a change to the generator’s alphabet would fail here rather than quietly removing this essay’s second finding.

And two things must fail. A corpus cut to one length loses 55.8% of itself and moves both measures. A corpus with its characters shuffled multiplies the run count by seven and leaves the entropy alone.

What follows #

Three questions, in the order they matter.

The dial that has no setting asks whether the generator can be made to be this corpus — whether some fraction reproduces the real collection’s measures — and finds two answers a factor of 1.4 apart.

Documents that are not the same length takes the document strand’s own findings to real documents, and one of its headlines does not survive.

And what the generated collection was right about is the accounting: which of five strands’ conclusions hold on data nobody made, and which were properties of the maker.