The cap an automaton cannot see

The linear construction reproduces the uncapped parse exactly. The capped one it does not, and this essay is why, how much it costs, and where it costs nothing.

The short version is a sentence about what an automaton state is. A state stands for a set of occurrences and can hand back one of them cheaply. A cap is a condition on which occurrence is used, and a structure that offers one occurrence cannot be asked to search among them.

The parse in one pass of the text is where the construction comes from, and a parse that will not follow a long chain is where the cap does. This essay is the one place they do not fit together.

What the exhaustive construction does #

At each position it tries every earlier position as a source. For each, it extends the match character by character, checking as it goes that the depth of the source character it is about to copy is below the cap, and stopping when the check fails.

Then it keeps the longest match any source produced.

That “any source” is the whole of it. A candidate string of length seven may occur four times earlier; three of those occurrences sit in deep regions and one does not, and the construction finds the one that does — by looking at all four.

What the automaton offers #

A state of the automaton stands for a set of strings that share an endpos set: the positions at which they all end. It carries one number from that set — the smallest — and that is what makes it a locator rather than a membership test.

So the walk can ask: does this string occur earlier, and where does its earliest occurrence end? It cannot ask: does this string occur earlier in a shallow region, and where.

Answering the second means a query of the form minimum, over the endpos set of this state, of the maximum depth over a window ending there — a range condition over a set that is not stored, about a quantity that depends on the length of the match as well as on the position. There is no field to add to a state that answers it.

So the cap becomes a different cap #

The relaxed construction tests the cap on the earliest occurrence and stops the match when that occurrence fails it, rather than looking for another.

Both constructions produce a valid parse, in the sense the term that came back requires: the text comes back out of it, character for character. Both satisfy the cap — no position of either is deeper than it, checked by walking the finished parse and recomputing every depth from the phrases rather than trusting the construction that claims to enforce them.

They are not the same parse, and the relaxed one is never longer in matches at any single step. Whether it uses more phrases overall is a different question, because greedy is greedy.

A construction and a definition, again #

This is the third time in this collection that a construction has turned out to answer something narrower than the definition it implements, and the pattern is worth naming.

The definition is not the algorithm is the thread it belongs to. There, the usual shape is that evaluating a definition directly costs whatever quantifying over everything costs, and a construction avoids the quantifier by computing the same answer another way — the exact shift rules, whose definition is quadratic and whose construction is linear and identical.

Here the construction does not compute the same answer. It computes a different, valid one, and the difference is a measurement rather than a bug. Both outcomes come from the same starting point — a definition with a quantifier in it — and which one arrives depends on whether the quantifier can be eliminated or only avoided.

What it costs #

At a collection of 4,096 characters with copies diverged by five per cent:

Three regimes, and only the middle one is about the relaxation.

At the tightest cap there is nothing to choose: almost every phrase is a literal or a one-character copy, and both constructions produce the same parse.

Above the text’s own worst depth the cap never binds, and both produce the free parse.

Between them the relaxation pays, and the worst of it is a tenth of the phrases.

The row that runs the other way #

There is a cap at which the relaxed construction produces fewer phrases, and it is left in rather than tuned out.

Greedy is not optimal. Taking the longest match at every position is a rule, not a claim about the result: a phrase cut short now can leave a longer one available later, and a construction that is never better at any single step can come out ahead over a whole text.

On a smaller collection at a cap of three, the relaxed parse uses 358 phrases against the exhaustive one’s 361.

That is worth three sentences rather than a footnote, because it is the clearest available demonstration that “chooses the longest match every time” describes a rule and not a result — the same distinction the fold that minimises the wrong thing draws about a merge order, and the order nobody fixed about a merge policy. Every argument in this ladder about what a cap costs is an argument about a rule’s output, and the output is not monotone in the rule’s local quality.

Why the cost is a property of the text #

At exact copies the relaxation costs nothing, at any cap.

The reason is symmetry. When every copy is identical, every occurrence of a string sits at the same depth as every other — the copies are produced from each other in the same pattern — so choosing the earliest is choosing an arbitrary member of a set whose members are interchangeable.

Every edit breaks that. A copy with a substitution in it produces, around the edit, occurrences at different depths, and the earliest is no longer guaranteed to be among the shallowest.

Measured at a cap of four, across a divergence sweep: 0%, 1.7%, 1.2%, 3.2% at zero, two, eight and twenty-five per cent of characters changed.

That is a useful shape, because it says where the relaxation is safe. A collection of near-identical versions — which is the case a phrase index is built for — is the case where taking the earliest occurrence costs least.

Why the middle is where it binds #

The three regimes are not a coincidence of these numbers; they follow from what a cap does.

At a cap far above the text’s worst depth, no phrase is ever rejected, so no choice among occurrences is ever made and both constructions take the same longest match everywhere.

At a cap of one, almost every candidate source is rejected whichever occurrence is examined — a source at depth zero is a literal, and literals are rare — so both constructions fail almost always and produce nearly the same parse of literals and one-character copies.

In between, a candidate is sometimes admissible, and that is exactly the condition under which “which occurrence” matters. The width of the middle regime is the width of the depth histogram, which is the measurement the number that would choose a cap is about.

The construction that would close it #

It is worth being precise about what would be needed, because “the automaton cannot do it” is a claim that deserves a boundary.

What is missing is a query over the endpos set. If a state’s occurrences were enumerable in order of their region’s maximum depth, the walk could take the shallowest and the two constructions would agree.

Endpos sets are enumerable — they are the leaves beneath a state in the suffix-link tree — but enumerating them is proportional to the number of occurrences, which is what makes the exhaustive construction quadratic in the first place. A structure answering “the shallowest occurrence of this state, for a window of this length” would be a range structure over a quantity that changes as the parse proceeds, since depths are assigned by the parse being built.

The depths are the parse’s own output, which is the real obstacle: the query is about a quantity that does not exist until the query has been answered for every earlier position. That is not a structure problem; it is a dependency.

Two ways of getting the relaxed cap wrong #

Both produce parses that satisfy every condition except the one that matters, and both are checked as cases that must be rejected.

Testing the cap on the source’s first character only. The source region can reach into a deeper part of the text three characters later, so a source whose first character is shallow admits a phrase that is not. Measured at a cap of three: the finished parse has a position at depth five, with 182 phrases against the correct 358 — a parse that is half the size and violates its own guarantee.

Taking the latest occurrence rather than the earliest. A state can hand back either end of its endpos set cheaply, and the latest is a legal source for an uncapped parse. Under a cap it is a catastrophe: the latest occurrence is the deepest almost by definition, so the cap bites on every phrase and the parse collapses. Measured at a cap of four: 2,048 phrases for a 2,048-character text — one per character — against 245.

The second is the more interesting of the two, because it shows that the choice of which occurrence a state reports is load-bearing rather than arbitrary. Taking the earliest is not a convenience; it is the policy that makes the relaxation cost ten per cent rather than a factor of eight.

What this means for the numbers at scale #

The essay before this one re-ran the cap ladder at thirty-two times its original size, using the relaxed construction, and reported that the ladder’s conclusions hold.

This essay is the caveat on that. At the caps the ladder’s knee sits in — four to eight — the relaxed construction uses between 0.2% and 9.8% more phrases than the exhaustive one would. So the scaled sweep’s phrase counts in that band are upper bounds, and the true exhaustive figures would be up to a tenth lower.

Every conclusion in that essay survives it: a factor of 25.9 at the tightest cap is not sensitive to a tenth, and the knee’s location is set by where the curve turns rather than by its height. But the numbers are stated as what they are, and the plates in that essay draw the relaxed construction because that is the one that runs at that size.

A measurement taken with a relaxed instrument is a measurement, provided the relaxation is measured. That is what this essay is for.

Why the cost peaks at four rather than rising to the tight end #

The middle regime is not a plateau. It is 1.9%, 2.3%, 9.8%, 0.2%, 0.5% across caps two to eight — a single spike, four times its neighbours, and the shape is worth deriving because it says where the relaxation actually matters.

The relaxation costs a phrase only when two things hold at once. The earliest occurrence of a candidate must be too deep for the cap, or the exhaustive construction would have taken the same match; and some other occurrence must be shallow enough, or there was nothing for the exhaustive construction to find either. So the cost is governed by the probability that a state’s occurrences straddle the cap.

Those two conditions move in opposite directions as the cap tightens. Lowering the cap makes the first more likely — more earliest occurrences fail — and the second less likely, because fewer occurrences of anything survive. Their product is zero at both ends and positive in between, which is exactly a single interior maximum rather than a trend.

The measurements locate it. The uncapped parse is 417 phrases; the exhaustive capped one is 434 at a cap of six, 531 at four, 781 at three. So the cap begins to bite between six and four and bites hard below it, and the straddling probability peaks where the curve first turns — at four, where the exhaustive parse is already 27% above free and has not yet collapsed. Below that the cap is rejecting nearly everything whichever occurrence is consulted, and the two constructions converge again from the other side.

Which puts the relaxation’s worst case at the cap a deployment would choose. The knee is the whole point of the sweep — a cap above it buys nothing and a cap below it costs a great deal — so a system setting its cap from the number that would choose a cap lands on or near four, and lands on the spike. The 9.8% is not a corner of the parameter space to be noted and set aside; it is the operating point, and the two other bands where the relaxation is free are the bands nobody would run in.

That reverses the natural reading of the three regimes. A cost that is zero at both extremes and nine per cent in the middle sounds like a well-behaved instrument with a narrow bad patch. It is better described as an instrument whose error is concentrated exactly where the quantity being measured is interesting, which is the shape where a crossing moved to keeps finding in this collection: the parameter that makes a comparison worth making is the parameter at which it is hardest to make honestly.

It does not change the caveat’s conclusion, because the caveat was already stated at the binding caps and in the conservative direction — the relaxed counts there are upper bounds, and the exhaustive figures would be up to a tenth lower. It changes what a reader should do with the number: carry the 9.8% as the figure that applies, rather than the near-zero the two flat regions invite.

What a reader should take from a relaxation #

The general shape is worth naming because this collection will meet it again.

A structure that makes a computation linear often does so by answering a weaker question than the definition asks. Here the definition asks about every occurrence and the structure answers about one. The right response is neither to pretend the questions are the same nor to abandon the structure, but to measure the gap.

The gap is measurable because the exhaustive construction exists and is affordable at small sizes. So the strand keeps both: the definition as the reference at 4,096 characters, and the relaxation as the instrument at 65,536, with the difference between them measured where both run.

That is the same arrangement the shift-rule strand arrived at — the table the links already knew keeps the definition as the default and checks the fast construction against it at every node — and it is what makes a fast construction trustworthy rather than merely fast.

What a strand gains from a construction it cannot use #

It is worth ending on what the exhaustive construction is still for, because the temptation after building a linear one is to delete it.

It is the reference. Every claim about the relaxation is a claim about a difference, and a difference needs both sides. Delete the quadratic construction and this essay becomes unwritable — not wrong, unwritable, because there would be nothing to measure the relaxation against.

It is also the definition. A cap is defined as a condition on a phrase’s whole source region, and the exhaustive construction is that definition executed. The relaxed one is a rule that satisfies the definition and is not it, and knowing which is which matters the next time somebody asks what a capped parse is.

So the strand keeps both, with the slow one as the default in every check and the fast one as the instrument in every sweep above four thousand characters. That arrangement costs a few seconds a run and it is what makes the fast one trustworthy.

What is checked #

The relaxed cap holds at every cap — the same requirement what a ceiling costs in phrases placed on the original — verified by recomputing every depth from the finished parse. A construction that both enforces a bound and reports whether it holds is a check of nothing, so the check walks the phrases.

The exhaustive cap holds too, on the same collections, which is what makes the comparison a comparison.

The relaxation costs phrases in total — asserted, so that a change making the two constructions agree everywhere would fail here rather than quietly removing this essay’s subject.

And the ends agree. The tightest cap and the loosest are required to produce identical phrase counts by both constructions, which is the assertion that establishes the three regimes rather than merely describing them.