A parse that will not follow a long chain

An index built on a text’s own parse stores no text. It produces a character by following the phrase that holds it back to the phrase it was copied from, and that one back again, until it reaches a literal — a character that was written down because it had never been seen before.

The character that costs a chain measures that price and states the limit plainly: the greedy parse bounds the chain by nothing. On a collection of thirty-two copies the worst position costs thirty-eight follows, because each copy is parsed as a copy of the one before it, and the mean is 17.89. The structure’s size stopped growing at the second copy and the price of reading it did not.

This essay caps it.

What the depth of a position is #

Every position gets a number. A position inside a literal phrase has depth zero. A position inside a copying phrase has one more than the depth of the position it was copied from.

That is well defined because the source is always strictly earlier, so the depths can be computed left to right and each one refers to a number already known. It is also the reason a phrase that overlaps its own source has increasing depths along its length: a thousand identical characters is one literal and one phrase of length 999 copying from position zero, and the depth at the end of it is 999.

The number matters because it is exactly what the index charges. charAt(i) follows the chain and returns the depth alongside the character, so the depth of a position and the cost of producing it are the same quantity measured once.

The construction #

At each position, take the longest match starting earlier whose whole source region has depth at most $D - 1$. If no such match exists, write the character down as a literal.

Two things about that sentence are load-bearing.

“Whole source region”, not “source”. A phrase copying $\ell$ characters from position $s$ inherits the depth at $s$, at $s+1$, and so on to $s + \ell - 1$, and those are different numbers. Taking the depth at $s$ alone is cheaper — one array read instead of a scan — and it is wrong exactly where the source region spans a change in depth, which is every self-overlapping copy and therefore every case the cap exists for.

That version is a check that must reject, and it does: on a text of two thousand characters with a cap of four, it lets a chain of nine through. Every phrase it produced satisfied the condition it tested, the parse looked completely ordinary, and the structure it built had positions costing more than twice what the cap promised.

The shape of that failure is one this collection keeps meeting. A cheap test that agrees with the expensive one on the common case and disagrees on the case the whole feature exists for is not a shortcut, it is a different feature — and the only thing that catches it is measuring the property afterwards from the output rather than trusting the construction that claimed it. So the depth walk that verifies a parse is deliberately separate from the parse that produced it: a construction that both enforces a bound and reports whether it holds is a check of nothing.

“Longest match”, still greedy. The cap restricts what is available; it does not change the rule for choosing among what is available. That matters for the comparison: at $D = \infty$ the construction has to be the greedy parse, phrase for phrase, or every cost attributed to the cap would be partly the cost of a second implementation. It is, checked on four texts.

Both ends of the dial are degenerate, and both are informative #

At $D = \infty$ it is the parse the phrases a text copies from itself measures. On sixteen copies of five hundred and twelve characters: 156 phrases, worst depth 22, mean 9.89.

At $D = 1$ every phrase must copy from literal positions, and there are only about $\sigma$ of those — one per symbol, which is the alphabet-sized floor that essay measures. So almost nothing can be copied from and the parse is nearly a character-at-a-time enumeration: 7,351 phrases over 8,192 characters, which is 0.90 of the text.

The second of those is the finding the whole ladder is about, and the next essay but one is where it is drawn. A structure proportional to the phrase count is worth building because the phrase count is 1.9% of the text; at $D = 1$ it is 90% of the text, and the term proportional to $n$ that the entire family of compressed indexes exists to remove has come back.

What happens in between #

The interesting part, and it is not linear in anything.

At sixteen copies the phrase count runs 7,351, 2,857, 946, 170, 157, 156 for caps of 1, 2, 4, 8, 16 and none. The worst depth runs 1, 2, 4, 8, 16, 22.

So a cap of eight costs fourteen phrases — nine per cent — and cuts the worst chain from 22 to 8. A cap of sixteen costs one phrase and cuts it to 16. A cap of four costs six times the phrases. The curve is flat at the loose end and vertical at the tight one, and the elbow is somewhere around a cap of six to eight on this collection.

The reason for the shape is the depth distribution rather than anything about the parse. Most positions are shallow: the mean depth without a cap is 9.89 against a worst of 22, and the tail is thin. A cap above the bulk of the distribution costs almost nothing because almost no phrase has to change; a cap below it costs everything because almost every phrase does.

The trade is monotone, and that is a claim rather than an observation #

Tightening the cap must not reduce the phrase count and must not raise the worst depth. Both directions are checked at every step of the sweep, and the check is not decorative: a non-monotone row is the symptom of a greedy choice made against a stale depth, which is the most likely way for this construction to be subtly wrong.

Monotonicity is also what makes the plate a frontier. A set of points where tightening sometimes helps both quantities would be a scatter with a best point in it, and the honest picture of a trade is a curve on which every point is undominated.

Why the cap has to be a parameter and not a setting #

There is an obvious question — what is the right cap — and the honest answer is that there is not one, because the elbow is a property of the text.

On four texts of four thousand characters, a cap of four costs 2.96 times the phrases on an internally repetitive text, 1.31 on English-like text, 1.28 on four-symbol text and 1.11 on a periodic one. That is a threefold spread from one parameter value, and the fourth essay on this ladder is about the direction of it, which is the opposite of the obvious guess.

So the cap belongs on the plate rather than in the code, the way every other model parameter on this site does. The model has parameters is the thread and the threshold somebody chose is the essay: a constant nobody measured is a constant that will be wrong on the next input, and the sensible form of the answer is a curve with the parameter along it.

What a capped index still is #

Everything else about the structure is unchanged, and that is worth checking rather than assuming.

A capped parse is a parse: the same phrase records, the same three orderings of the boundaries, the same crossing search, the same propagation. The index built on it produces its text character for character at every cap, and finds the same occurrences as exhaustive search at every cap. Both are checked, at four caps, because a construction that quietly produced a different text would show up as nothing at all in any size or depth plate.

That is the same discipline the parse strand applied when it built the index in the first place — an index with z in its size checks its occurrence set against brute force at four pattern lengths before reporting a single size — and the reason it is repeated here is that the cap changes the parse and every downstream number is computed from the parse.

What it costs to build, which is not nothing #

A tighter cap is more expensive to compute, and by a lot.

The parse is quadratic either way — at each position it scans every earlier position for the longest allowed match — but a capped parse produces more phrases and each one is another scan. Measured on the sixteen-copy collection: 10,857 character comparisons with no cap, 30,093 at a cap of 8, 458,460 at a cap of 4, and 2,683,493 at a cap of 1. A factor of 247 between the ends.

That is a property of this construction rather than of the cap. A linear-time parse from a suffix automaton — the structure every substring, in fewer states than substrings builds — computes the unbounded parse in linear time, and a depth-bounded variant of it would have to carry the depth condition through the automaton, which is not something this collection has built. So the construction cost above is an honest measurement of what was run and a poor guide to what the cap would cost in an implementation that cared.

The distinction is the same one the phrases a text copies from itself draws about the quadratic parse: the sizes the sweeps run at are set by the construction, and the claims are about shapes rather than extrapolations.

The depth is not the only thing a chain costs #

One thing the cap does not fix, and it is worth naming so the plates are not read as a general remedy.

A chain of $D$ follows is $D$ phrase lookups, and each lookup is a predecessor query over the phrase starts — a binary search of $\lceil\log_2 z\rceil$ steps. So producing a character at depth $D$ costs $D\log z$ operations, not $D$, and tightening the cap raises $z$ and therefore raises the logarithm.

At the measured sizes that second effect is small: $\log_2 z$ goes from 8 at $z=156$ to 13 at $z=7351$, so a cap of 1 costs one follow at 13 steps against no cap’s ten follows at 8 steps — 13 against 80, still a large win. But the two terms move in opposite directions, and a cap chosen by looking at depths alone is chosen against half of the arithmetic.

The same shape appears one ladder over: the grids that make this index’s search proportional to its answer are $z\lceil\log_2 z\rceil$ bits, so a tighter cap makes them larger too. The structure paid for before the first query prices them, and a reader building both structures is paying the cap’s cost twice.

Which of the two terms actually decides it #

The section above puts $D\log z$ in place of $D$, evaluates it at the two ends of the dial and stops. Evaluating it at every cap is one line of arithmetic and it settles which term the cap is really trading against — the answer being neither of the two the section names.

Worst depth times $\lceil\log_2 z\rceil$, at the sixteen-copy collection’s six settings:

• cap 1 — $z = 7{,}351$, so 12.8 steps a follow, one follow: 12.8
• cap 2 — $z = 2{,}857$, 11.5 steps, two follows: 23.0
• cap 4 — $z = 946$, 9.9 steps, four follows: 39.5
• cap 8 — $z = 170$, 7.4 steps, eight follows: 59.3
• cap 16 — $z = 157$, 7.3 steps, sixteen follows: 116.7
• no cap — $z = 156$, 7.3 steps, twenty-two follows: 160.4

It is monotone. Tightening the cap improves the product at every step, all the way to the degenerate end, and the measured means behave the same way — one follow at 12.8 steps against ten follows at 7.3, so 12.8 against 72.9.

So the two terms do move in opposite directions and it does not matter, because they move by wildly different amounts. Across the whole dial the depth spans a factor of 22 and the logarithm spans a factor of 1.8. A term that can only ever repay itself by 80% cannot pay for a term that costs twenty-two times, and no cap on this collection is anywhere near the point where the second competes with the first.

Which means the sentence about being chosen against half the arithmetic is right about the omission and wrong about its size, and the correction is worth making because it relocates the trade. A cap is not bought with a logarithm. It is bought with phrases, and phrases are the size of the index — 156 of them at no cap and 7,351 at a cap of one, which is 90% of the text and the end of the reason for building a compressed index at all.

That also explains why the trade plate is a genuine frontier while this product is monotone. The frontier’s axes are the phrase count and the depth, and those really do oppose each other. The extraction product folds the phrase count into a logarithm, which is exactly the operation that throws away the term doing the work: a structure going from 156 records to 7,351 is 47 times larger, and $\log_2$ of that is 1.8.

The condition under which the second term would bite falls out of the same arithmetic, and it is a self-defeating one. The logarithm competes when $D$’s range is comparable to 1.8 — that is, on a collection whose uncapped depth is already two or three. The term only matters where capping has nothing to win, so a reader will never meet a case where it decides the setting.

The tighter cap’s cost is also charged twice, which the section on the grids already notes and which this arithmetic sharpens. Grids over the phrase table are $z\lceil\log_2 z\rceil$ bits, so the cap of one that produced 7,351 phrases produces grids about 83 times the size of the uncapped ones — a size effect again, and again not a logarithm. The structure paid for before the first query is where that column is priced, and it is the column the cap is genuinely spending.

The honest form of the character that costs a chain’s question is therefore: how many phrases is a bounded read worth. On this collection a cap of eight answers it at fourteen phrases, and everything below six answers it at hundreds or thousands.

What this is not #

It is not LZ-End, and the difference is worth one paragraph because LZ-End is the published structure for this problem.

LZ-End bounds the extraction cost by requiring every phrase to end where an earlier phrase ended, which makes a substring extractable in time proportional to its length plus the number of phrases it spans. It is a different parse with a different phrase count and a different set of properties, and it does not bound the depth — it makes the depth irrelevant by changing what a chain walk has to do.

The cap here is on the depth itself, because the depth is what this collection’s index charges and because a bound stated in the same quantity the structure pays in is the one whose price can be read off a plate. Both are legitimate; only one of them can be measured against the numbers the parse strand already published.

One more thing the cap is not: a fixed tax. What it costs is a property of the text it is applied to, and the direction of that dependence is the opposite of the obvious guess.

So a cap is cheap on the collections a person expects it to be expensive on, and the quantity that predicts the price is the depth distribution rather than the amount of repetition.

The measured cost of a character, against the modelled one #

The cap is a bound on the worst case and a reader pays the mean, and the two are far apart.

Extracting 256 characters from the middle of the collection: with no cap the index follows 2,560 phrases, ten per character. At a cap of 8 it follows 1,024 — four per character, against a cap of eight. At a cap of 4, 2.80 per character. At a cap of 1, exactly one.

So the measured cost is roughly half the cap at every setting, because most positions are nowhere near it. A structure sold on its worst case is a structure whose typical cost is unstated, and the two differ by a factor of two here — which is the mildest version of the gap expected is not average is about, and the reason both numbers are on the plate. It is the same distinction the height is a distribution, and the coin is a parameter draws for a skip list: a structure whose worst case and typical case differ has two costs, and quoting either alone is a choice about which reader to serve.

What is being claimed #

The copy depth of a position is one more than the depth of the position it was copied from, computable left to right, and it is exactly what the phrase index charges to produce a character.

A parse restricted to sources of depth at most $D - 1$ has depth at most $D$, checked at every position under four caps, against an unbounded parse that breaches every one of them.

The restriction must be checked over the whole source region. Checking the source’s first character alone is cheaper, is what a reasonable implementation does, and lets a chain of nine through a cap of four.

At $D = \infty$ the construction is the greedy parse, phrase for phrase on four texts — which is what makes every cost below attributable to the cap.

And the dial’s two ends are 156 phrases at depth 22 and 7,351 phrases at depth 1, on a collection of 8,192 characters. What that second number means is the third essay on this ladder, and what the middle of the dial is worth is the next one.