What the approximation gives up

The published shift rules are a safe approximation to a quantity with an exact definition. Two questions follow and neither is answered by the phrase: how safe, and how approximate.

The first is a proof and it is checked: at every pair of a trie node and a mismatching character, on every pattern set measured here, the published shift is at most the exact one. The second is a measurement, and the answer is that the approximation gives up nothing at all past a set size a plate can show.

Comparing over the domain, not over a run #

A run is a sample. It visits the trie nodes its text happens to lead it to, mismatches on the characters that text happens to contain, and reports a number that mixes the rules’ difference with the text’s shape.

So the comparison here is over the whole domain of the function: every trie node, every character of the alphabet, whether or not any text would produce that pair. At 128 patterns of ten characters that is 3,736 pairs; at two patterns it is 84.

That distinction matters because the run-level numbers and the decision-level numbers say different things, and only the second is a property of the rules. It is the same move the ceiling the shortest pattern sets makes when it asserts the shift ceiling over the whole shift table rather than over the shifts a run happened to take.

The numbers #

Across pattern sets of one, two, four, eight, sixteen, thirty-two, sixty-four and 128 patterns of ten characters over four symbols:

At one pattern, 2 of 44 pairs differ, with deficits of one and seven. At two, 5 of 84, with a worst of four. At four, 3 of 152, all of them one. At eight, 6 of 288, all of them one. At sixteen, 2 of 552, both one.

At thirty-two, sixty-four and 128 patterns: zero. Not a small share — none. The two functions agree at every one of the 1,060, 2,016 and 3,736 pairs in their domains.

So the approximation is an approximation on small sets and is the exact rule on large ones, which is the opposite of what “linear-time approximation” suggests and is exactly what the mechanism predicts once it is looked at.

Why the gap closes as the set grows #

The published shift is $\min(\max(d_1, \mathrm{char}(c) - j - 1), d_2)$ and the exact shift is the largest step no pattern can end inside. The difference between them lives in the slack between $d_1$ and the exact good-suffix condition, and in the unconditional $\min$ with $d_2$.

Both of those quantities collapse as the trie fills up. With 128 patterns of ten characters over four symbols, nearly every node has a failure child one level down, so $d_1$ is one nearly everywhere; nearly every node has a pattern end within one or two levels of its suffix set, so $d_2$ is small everywhere as well.

And the exact rule collapses too, for the same reason: with that many patterns, the segment already matched can line up with something at almost every offset, so the exact shift is small as well.

Two functions that are both pinned at their floor agree. The gap between them is largest where both have room to move, which is on small sets — where the exact tables are cheap to compute anyway.

What it costs in a run #

The decision-level numbers are the property of the rules; the run-level numbers are what a user of them pays.

On twenty thousand characters of four-symbol text: at one pattern both rules read 7,197 characters. At two, the published rules read 13,084 against 12,306, which is 6.3 per cent more. At four, 12,211 against 12,069 — 1.2 per cent. At eight, 23,551 against 22,551 — 4.4 per cent. At sixteen, 24,372 against 24,299 — 0.3 per cent. At thirty-two and above, identical to the character.

The largest penalty in the sweep is 6.3 per cent, it occurs at two patterns, and it is not monotone: 6.3, then 1.2, then 4.4, then 0.3, then nothing. That wobble is the run sampling the decisions rather than the rules changing, which is exactly why the domain-level comparison is the one to believe.

Both counts move differently, again #

The run-level comparison has two numbers in it and this strand’s convention requires both, because they do not move together.

Characters examined is what the matcher spends, and it counts a position once for every window that reads it. At 128 patterns the published rules examine 41,580 characters in a text of twenty thousand — more than twice the text, because windows overlap.

Distinct positions read is the complement of the skip. At the same point it is 17,405 of 20,000, so 13 per cent of the text was never looked at.

The two rules agree on both at large sets and differ on both at small ones — at two patterns, 13,084 examined against 12,306 and 10,254 touched against 9,870. The second gap is 3.9 per cent where the first is 6.3, which is the same run reported two ways.

That convention came out of the phase that first measured a skipping matcher, where the two counts cross the one-pass matcher’s at different set sizes: examined characters overtake at eight patterns and distinct positions never do. The shift a set of patterns allows is where that was established, and it is why no plate here reports one of them alone.

Safety is the half that is not negotiable #

An unsafe shift is a wrong answer, and the gate treats it as one.

Every run in this strand is checked against exhaustive search on the occurrence list, and the domain-level comparison additionally requires the published shift to be at most the exact one at every pair. A rule that stepped one position too far would pass a count comparison whenever the missed occurrence happened not to exist, so both checks are needed.

The rejection test is the constructive half: raise $d_1$ to the ceiling at every node — a change that looks like a strict improvement, since larger shifts mean fewer windows — and require the exhaustive comparison to catch it. Measured: two occurrences reported where there are eight.

The bug this comparison found #

The comparison over the whole domain found something, and it was in the reference rather than in the approximation.

The helper that reports “the shift this node and this character allow” took an argument named depth, and it used that argument twice: once to index the good-suffix table, which is indexed by node, and once to index the bad-character table, which is indexed by depth. One argument cannot be both.

It had been correct at every existing call site by accident, which is the shape the check must reject is about: a condition nobody asks about is a condition nobody is checking. The two callers were an assertion about the shift ceiling — every shift is at most the shortest pattern, which holds whichever node’s entry is read — and a rejection test that inflates a shift on purpose and requires the matcher to break.

It became visible the moment two rules were compared decision by decision: the published shift came out larger than the exact one at a node, which is a safety violation, and it was an indexing error in the thing the comparison was against.

The lesson is one this collection keeps relearning. A helper is only as checked as the questions asked of it, and a helper whose two existing callers both ask about a maximum can be wrong about every individual entry and right about the maximum.

What the deficits look like when there are any #

The distribution of deficits is short and it is worth reporting rather than summarising, because a mean over five values is not a summary.

At two patterns: three decisions short by one, one short by two, one short by four, out of 84. At one pattern: one short by one and one short by seven, out of 44. At four, eight and sixteen patterns: every deficit is exactly one. That is a shift falling one position short of the largest safe step, which costs one extra window and the characters that window reads — a quantity one run, two counts would have this collection report in both of its units.

The worst case in the sweep is seven positions against a shortest pattern of ten, and it occurs on a single pattern, where the published rule is at its crudest: with one word in the trie there are no failure children at all, so $d_1$ is the pattern’s length everywhere and $d_2$ is the length as well, and the shift is whatever the character table says.

That is Horspool’s matcher, near enough, which is what a single-pattern skipping matcher usually is — and the shift the pattern already knows is where this collection measured the exact good-suffix rule against it and found the same shape of gap.

The one place the deficit is worth something #

Six point three per cent of reads is small and it is not nothing, and there is a regime where it would be the whole decision: a pattern set that is built once and used on an enormous amount of text.

There, the construction cost is amortised to nothing and the only thing that matters is the scan. The exact rules read 12,306 characters per twenty thousand at two patterns against the published rules’ 13,084, so on a terabyte the difference is six per cent of the whole run and the tables cost 594 comparisons to build.

That is the crossing the rule that pays on a long enough text measures, and it exists only at the set sizes where the two rules differ at all. At thirty-two patterns and above there is no crossing to find, because the scan is identical and the construction is 13.8 times dearer — so the exact rules are dominated at every text length.

An approximation that is exact past a threshold has no crossing above that threshold. That sounds obvious written down and it is the reason the third curve this strand was asked for turns out to have two regimes rather than a shape.

What this settles about the third curve #

The direction after the phase that built the exact rules asked where the published functions sit between “no rules” and “the exact rules”. The answer is a surprise in one direction and not the other.

They do not sit in the middle. On randomly drawn sets of two or more patterns they are within 6.3 per cent of the exact rules in reads and are identical from thirty-two patterns up, while the bad-character rule alone has stopped skipping entirely by eight patterns.

So the scale is not a scale: there are two useful rules and one useless one, and the difference between the two useful ones is a construction cost rather than a skip. The table that walks every pair is that construction cost, and it is a factor of 137 at the top of this sweep — for the construction measured there. The table the links already knew builds the same tables from the trie’s links at 1.6 times the published rule’s cost, which is what the difference between the two rules is actually worth.

Where an adversary would put the difference #

The measurement is on pattern sets drawn uniformly at random with no member a substring of another, and it establishes what happens on such sets. It does not establish what happens on a set built to separate the two rules.

The mechanism says where to look. The published $d_1$ asks whether the matched segment can reappear deeper in the trie; the exact rule asks whether it can line up with a pattern at a given offset. A set where those differ systematically is one with long shared suffixes arranged so that the trie’s failure links are short while the actual alignments are not.

Nothing here constructs such a set, and the honest reading of this essay’s numbers is therefore: on random sets over a small alphabet, at one pattern length, the approximation costs between nothing and 6.3 per cent. A worst case exists in principle and is not measured.

Why this is in the wrong-answers field #

The sentence this essay is against is one this collection wrote when it built the exact rules: that the published shift functions skip less.

They do, in principle, and on the pattern sets a real matcher is given they do not — at eight patterns, six decisions of 288 differ and every one of them by a single position. A reader taking “skips less, costs nothing to build” as a trade would conclude that using the exact rules buys something, and on these sets it buys 0.3 to 6.3 per cent of reads for between four and 137 times the construction as measured there — or 1.5 to 2.4 times, once the exact tables are built from the trie’s links rather than from their definition.

The correction is not that the published rules are better. It is that the two halves of the trade have completely different sizes, and the sentence gives no way to tell. That is the same complaint the constant the notation drops makes about complexity classes, arriving at a pair of algorithms that are not distinguished by a class at all.

Folding positions into reads, which the run already does #

The last of those limits — that the deficits are in positions and the costs are in reads — is one the sweep can close, because the run reports both counts and the ratio between their gaps is the exchange rate.

At two patterns the published rules read 778 more characters than the exact ones, 13,084 against 12,306, and touch 384 more distinct positions, 10,254 against 9,870. The second number is the shift actually given up; the first is what giving it up cost.

Divide: 2.03 characters read per position of shift lost. That is the missing conversion, and it is not a modelled quantity — it is the same run reported in its two units, so it already carries whatever the trie walk really costs on this set and this text.

It also explains the pair of percentages the essay reports without connecting: 6.3 per cent in reads against 3.9 per cent in positions. The ratio of those is 1.6, and the ratio of the two totals is $13{,}084/10{,}254 = 1.28$ — the same overlap appearing once in the gap and once in the base. Two counts that move differently move by a factor that is measured rather than mysterious.

With a rate, the deficit distribution can be priced. At two patterns the five differing decisions give up eight positions between them — three of one, one of two, one of four — so a firing of the worst of them costs about eight character reads and a firing of the commonest costs two. The seven-position deficit at one pattern is worth about fourteen.

Which makes the single-pattern row the most instructive line in the sweep, and it needs saying plainly. Two of its 44 decisions differ, one of them by seven positions, and both rules read 7,197 characters — identically. The text never put either pair to the matcher, so the largest deficit anywhere in this essay cost exactly nothing on the run that could have paid for it.

That is the distinction the whole comparison rests on, arriving as a number instead of a methodological remark. A deficit is a property of the rules; a cost is a property of the rules and a text, and the two need not be related at all. A decision that differs by seven positions and never fires is free; a decision that differs by one and fires four hundred times is 800 reads. Nothing about the domain-level comparison predicts which, and nothing about the run-level comparison distinguishes a rule that is nearly exact from a rule that is badly wrong in a corner the text avoided.

Both are needed, and the honest summary of what each is for is this. The domain comparison bounds the worst a text could extract — five decisions, eight positions, about sixteen reads per full sweep of the differing pairs. The run says what one text did extract, which at two patterns was 6.3 per cent and at one pattern was nothing. The gap between those two statements is the text, and it is the largest term in the whole comparison.

That is one run, two counts’s convention doing more than book-keeping. Reporting characters alone would have hidden the conversion; reporting positions alone would have hidden that a position is worth two reads on this set and would be worth more on a deeper trie, which is the direction the shift a set of patterns allows says the number moves as the set grows.

The honest limit #

Everything above is one pattern length — ten characters — on two alphabets, with sets drawn uniformly at random. The mechanism that closes the gap is the trie filling up, which happens sooner on a small alphabet and with short patterns, so a set of long patterns over a large alphabet would keep the two rules apart for longer.

The domain-level comparison covers every (node, character) pair, which is the whole function; it does not cover every pattern set, and the sets here are eight sizes at one seed each.

And the deficits are in positions rather than in reads. A shift short by one costs one extra window, and a window costs however many characters the trie walk reads before mismatching — which is a number this collection measures separately and does not fold in.