The cap that binds on one text and not another

A cap on the copy depth costs phrases, and the number of phrases it costs is not a property of the cap. It is a property of the text, and the direction of the effect is the opposite of the one the words suggest.

The measurement #

Four thousand characters of each of this collection’s text kinds, parsed greedily and then under a cap of four. The ratio is the capped phrase count over the uncapped one.

A threefold spread, from one parameter value, on texts of identical length. Every one of those parses is a working index over its text; nothing here is a failure, and the variation is in what the same constraint costs to satisfy.

The guess, and why it is wrong #

A periodic text is the obvious candidate for the expensive one. Its parse is a chain by construction: each phrase copies from one period earlier, that phrase copied from one period before it, and so on back to the first period. Nothing could look more like a structure a depth cap would ruin.

It is the cheapest of the four.

The internally repetitive text — a text built by copying pieces of itself at random, which is the collection’s model of a corpus with duplicated passages — is the expensive one, at nearly three times the phrases.

What depth actually measures #

Not repetition. Nesting.

The distinction is easiest to see in the two extreme parses this collection already has. A run of a thousand identical characters is one literal and one phrase of length 999 copying from position zero, and its depths run 0, 1, 2, … 999 — the deepest chain in the whole field, on the most repetitive string there is. A collection of two identical documents is one long phrase copying from the first, and its depths are 1 everywhere in the second document — the shallowest possible chain, on a string that is exactly as repetitive.

Same amount of repetition, depths differing by a factor of a thousand. Depth is not counting how much of the text is a copy; it is counting how many times a copy has been copied.

A periodic text’s chain is long and flat: every phrase copies from one period earlier, so the depths increase by one per period and the chain from any position back to a literal is one step per period. But each of those steps is a long phrase, because a periodic text lets a phrase run for many periods before anything new happens. Cap the depth at four and the parse simply takes a shorter run of periods and starts again from a shallow source — which costs a few extra phrases and nothing else, because a shallow source in a periodic text is still a source that matches for a long way.

An internally repetitive text’s chains are short and deep in the sense that matters: a passage is copied, then a piece of the copy is copied somewhere else, then a piece of that is copied again. Each level of that is a genuinely different region of text, and a cap forces a phrase to reach back past all the intermediate copies to a shallow original — which is further away, and agrees for fewer characters, and therefore breaks into more phrases.

So the quantity a cap is expensive on is how many distinct generations of copying the text contains, and a periodic text has one generation repeated many times while a repetitive text has many generations.

The worst chain does not predict the cost #

The right-hand column of the table is the number a reader would use to choose a cap, and it does not work.

The four texts’ worst chains are 13, 10, 10 and 9 — a range of four across a threefold spread in cost. The periodic text, with a worst chain of nine, pays 1.11; the four-symbol text, with a worst chain of ten, pays 1.28; English, also at ten, pays 1.31.

That is the failure this collection keeps finding and keeps naming the same way. The words “on average” are not a number is the foundation version; expected is not average is the sharper one. A single summary statistic of a distribution — here the maximum — does not determine a quantity that depends on the whole shape of it, and the cost of a cap depends on how much mass sits above the cap and on how far each unit of that mass has to reach.

The dial that separates the two mechanisms #

There is a way to see the two effects apart, and it is the collection’s own dial.

Take a base text and repeat it $k$ times with a substitution rate. At divergence zero the copies are identical, and the parse of the whole collection is one generation deep in exactly the way a periodic text is: copy two is a copy of copy one, copy three of copy two, and each is a single long phrase. A cap costs almost nothing — nine per cent at a cap of eight over sixteen copies.

Turn the divergence up and each copy is no longer a single phrase. It becomes a sequence of phrases interleaved with the substitutions, and the phrases of copy three copy from the phrases of copy two rather than from the whole of it, so the generations multiply. A cap then has to reach further back for each of them.

That is the same dial the phrases a text copies from itself uses to separate a copy from a near-copy, and it turns out to separate the two mechanisms of depth as well: identical copies give long shallow chains, near-copies give the nested kind.

The same finding on the collection rather than on a single text #

The four texts above are single texts of four thousand characters. The ladder’s other measurements are on collections of copies, and the ordering survives the change of setting — which is worth confirming, because a collection of copies of a repetitive text is a different object from a repetitive text.

Sixteen copies of five hundred and twelve characters of the internally repetitive text: the uncapped parse gives 75 phrases with a worst chain of 23, and a cap of four gives 545 — 7.3 times, against English-like text’s 6.06 at the same setting. A cap of eight gives 104, which is 1.39 times against English’s 1.09.

So on collections the spread is smaller in ratio and larger in absolute terms, and the direction is the same: the text with fewer phrases pays more to have its depth bounded. The reason is the same reason. A structure that is small because it is nested is a structure whose nesting is where the smallness came from.

That is the sentence to carry out of this ladder. The cap is expensive exactly where the parse is small, and the two facts have one cause — which means the texts a phrase index is best on are the texts a depth bound costs most on, and any account of the structure quoting one without the other is quoting the good half.

Why this makes the cap a parameter rather than a setting #

If the cost of a cap were a function of the cap, a library could choose one. It is a function of the text, and the four texts here differ by a factor of three at the same setting.

Worse, the property it depends on is not one anybody measures. A corpus is described by its size, its alphabet and sometimes an entropy; the number of generations of copying it contains is not a statistic anyone reports, and the two measures of repetition this collection does compute — $r$ and $z$ — do not determine it. The periodic text has $z = 1{,}285$ and the repetitive one $z = 110$, so the cheaper text to cap is the one with twelve times the phrases.

The practical consequence is the one this site keeps arriving at. The threshold somebody chose is the essay about a constant nobody measured; a parameter that waits for another is about a parameter whose right value depends on a second parameter’s. This is the third shape: a parameter whose right value depends on a property of the input that nothing in the pipeline measures.

The honest answer is a two-line procedure rather than a default: parse once with no cap, look at the depth histogram, and put the cap where the mass ends. That costs one extra parse, which on this construction is the cheapest parse of the set.

Two other places a cap’s cost depends on the input #

Worth naming, because the shape recurs and this collection has met it twice.

Introsort’s recursion limit. The depth limit that almost never fires measures a cap on quicksort’s recursion depth that costs nothing on ordinary input and everything on the adversarial input it exists for — a parameter whose cost is zero almost always and unbounded rarely, which is the opposite distribution from this one and the same lesson about summary statistics.

A window’s size against a rate. Sized for a rate that does not hold still is about a parameter chosen against a property of the stream that the stream does not hold constant. The parallel here is exact: a cap chosen from one corpus’s depth histogram is a cap chosen against a property that the next corpus does not share.

The difference between those two and this one is what a library can do about it. A recursion limit can be set defensively, because its cost when it does not fire is zero. A window size can be adapted, because the rate can be measured while the stream runs. A depth cap has to be chosen before the parse and its cost is paid in the parse, so the only measurement available is a parse — which is why the honest procedure above is “parse twice”.

What the assertion had to be changed to #

This measurement broke its own check, which is worth recording because the fix is a convention rather than a repair.

The first version of the assertion required that the same cap cost English-like text and a periodic text different amounts, and it failed: 1.31 against 1.11, a spread of 1.18, which is not a finding. The two texts that do differ are the repetitive one and the periodic one, at 2.96 against 1.11.

The interesting part is which way round the first guess was. The pair chosen for the check was “ordinary text against the text that is obviously all chains”, and the periodic text was expected to be the expensive one. It is the cheap one, and the check as written could not have said so — it demanded a spread, got 1.18, and reported a failure rather than a surprise.

So the convention this ladder adopts: a check that a parameter’s cost varies with the input must name the two inputs it varies between, and the pair is chosen by measuring rather than by reasoning about which ought to be extreme. The same rule appears in this collection’s own gotchas about plates whose assertion holds at one end of a dial and are drawn at the other.

The premium is on the structure. What a reader actually pays when they read is the mean depth, and on the expensive text the two numbers are far apart in the useful direction.

Which sharpens the warning rather than softening it: what a tight cap buys is a guarantee that almost nobody exercises, and what it costs is a phrase count that everybody pays for.

What a reader should do with this #

The measurement is a warning rather than a recipe, and it is worth being explicit about what it does and does not license.

It does not say a cap is a bad idea. On every text here a cap of eight costs under ten per cent and bounds a chain that is otherwise bounded by nothing. The expensive settings are the tight ones and the expensive text is expensive at every setting, so a defensive cap high above the depth histogram is cheap everywhere measured.

It does say the number cannot be shipped. A default of four is a nine per cent premium on one corpus and a threefold one on another, and nothing about a corpus that anybody records distinguishes them.

And it says the two obvious proxies do not work. The worst chain does not predict the cost, and neither does the phrase count — the text with the fewest phrases is the most expensive to cap, which is the reverse of the direction a reader would assume.

What is left is the histogram, which costs one parse. On a construction that already runs a parse to build the structure, computing the depths afterwards is a linear walk over the phrases and costs nothing beside it — which is the same asymmetry every check in this collection relies on: measuring the property from the output is cheap, and trusting the construction that claimed it is what goes wrong.

The generated texts, and how far this generalises #

Every text here is generated, and it is worth being clear about what each one models, because the finding is a statement about the four of them.

Periodic is a fixed pattern of period seventeen, repeated. It models a structured record format, and its repetition is entirely local: everything a phrase needs is one period back.

Internally repetitive is built by copying random earlier pieces of itself, which models a document with duplicated passages, a codebase, or a log with repeated stanzas. Its repetition is at many scales and the copies overlap.

English-like is a Markov-ish source over nineteen symbols with word structure, and four symbols, uniform is incompressible beyond its alphabet. Neither has structural repetition and their parses are correspondingly large.

The threefold spread is measured across those four, which span the shapes this collection can generate and do not span the shapes a real corpus has. A genome, a version history and a web crawl each have a repetition structure that is none of these, and the honest form of the claim is: the cost of a cap varies by a factor of three across four synthetic texts of one length, so it varies, and the direction of the variation is set by nesting rather than by how much of the text is a copy. How far it varies on real data is not measured here.

Two more parameters whose right value is a property of the input #

The list is worth keeping because the fix is the same each time and the fix is a measurement rather than a default.

The threshold somebody chose is the insertion-sort cutoff inside a library quicksort: a constant in production code, chosen once, correct for the machine and the element type it was measured on and for nothing else.

The formula everybody sizes filters with is a Bloom filter’s bit count, computed from a formula whose derivation assumes something the implementation does not do.

A parameter that waits for another is the two-parameter version, where the right value of one depends on the value of a second that is chosen elsewhere.

The cap is the fourth shape: a parameter whose right value depends on a property of the data that nothing in the pipeline computes. Of the four it is the easiest to fix and the least likely to be, because the measurement it needs — a depth histogram — is one linear pass and is not a number anybody currently prints.

What is being claimed #

The cost of a cap of four spans a factor of 2.7 across four texts of the same length, from 1.11 times the phrases on a periodic text to 2.96 on an internally repetitive one.

The direction is the opposite of the obvious guess. The text whose parse is most visibly a chain is the cheapest to cap.

Because depth measures generations of copying rather than repetition. A long flat chain of long phrases is cheap to cut; a short chain through several distinct copies is not.

And the worst chain does not predict the cost. Four texts with worst chains of 13, 10, 10 and 9 pay 2.96, 1.31, 1.28 and 1.11.

So the cap is an input-dependent parameter with no summary statistic behind it, and the only defensible procedure is to parse once, look at the depth histogram, and set the cap where the mass ends.

And the expensive texts are the ones the structure is best on. The internally repetitive text has 110 phrases where the periodic one has 1,285, and it pays nearly three times as much to have its chains bounded — which is one cause showing up twice, since the nesting that made the parse small is the nesting a cap has to undo.