The shift somebody published

A phase ago this collection built the exact shift rules for a multi-pattern matcher — the largest step a window can take without passing an occurrence — and measured what they cost: 359,251 character comparisons at 128 patterns, against a scan of 49,072. Seven times the scan, to compute the tables that make the scan cheap.

That measurement ends with a sentence about the rules that actually ship: the published shift functions are linear-time approximations; they skip less and they cost nothing to build. Neither half of that was measured, because they were not built.

The exact rule is a definition, not an algorithm #

The window ends at some text position and the matcher has read backwards through a trie of the reversed patterns, matching $j$ characters and then mismatching on a character $c$. The question is how far the window may move.

A pattern can end at the new position only if two conditions hold: the segment already read lines up with that pattern at the new offset, and the mismatching character lines up too. Both quantify over every pattern at every offset, so computing the smallest safe shift means walking the whole set for every trie node — which is the quadratic cost above, and which the shift a set of patterns allows measured.

The published rules replace that with two tables and a character table, all three computed in one pass over the trie.

What the three tables are #

char($c$) is the shallowest depth at which $c$ appears in any reversed pattern, capped at the length of the shortest pattern. A character no pattern contains gets that length plus one, which is the largest shift the set can ever allow.

d₁($v$), for a trie node $v$, is the least depth increase to a node whose word has $v$’s word as a proper suffix. It is the good-suffix idea in the multi-pattern setting: if the segment already matched can reappear deeper in the trie, the window cannot move past that possibility.

d₂($v$) is the same quantity restricted to nodes that end a pattern, and inherited from the parent where there is none. It is a guard rather than a saving: it stops the window stepping past a place where a whole pattern could finish.

The shift is then

$$\mathrm{shift}(v, c) = \min\big(\max(d_1(v),\ \mathrm{char}(c) - \mathrm{depth}(v) - 1),\ d_2(v)\big).$$

Three tables, one formula, and no quantification over the patterns anywhere in it.

Why the tables are cheap: the failure links are the relation #

The definition of d₁ is “the least depth increase to a node whose word has this one as a proper suffix”, and that is the Aho–Corasick failure relation read backwards.

A failure link points from a node to the deepest node whose word is a proper suffix of its own. So the nodes whose words have $v$’s word as a proper suffix are exactly the nodes whose failure chains pass through $v$, and the nearest of them is a direct failure child. One pass over the trie’s failure children gives d₁ at every node.

d₂ needs one more pass, because the nearest failure child need not end a pattern: process the nodes deepest-first, carry at each node the least gap to a pattern end within its own suffix set, and then walk shallowest-first applying the parent’s value where a node has nothing of its own.

Two passes, linear in the trie. The same automaton one pass for every pattern at once builds for a matcher that never skips is what makes the skipping matcher’s tables affordable — which is a pleasing dependency and is not usually stated.

Checked against the definition, node for node #

An identity of that kind is exactly the sort of thing that is true, is believed, and is implemented with an off-by-one. So both are computed: the linear tables from the failure links, and the same tables from the definition by walking every pair of nodes and testing whether one word ends with the other.

On three pattern sets — two, four and eight patterns of eight characters — the two agree at every node for both tables. That is the check the plate at the top of this essay carries, and it runs on every build.

The cost difference between the two computations is visible in the same run: 226 units against 289 at two patterns, 474 against 1,089 at four, 885 against 3,481 at eight. The quadratic one is already four times dearer at eight patterns, which is where the table that walks every pair takes the measurement seriously.

What it reads #

The rules exist to make a scan cheap, so the scan is the measurement that matters.

On twenty thousand characters of four-symbol text with patterns of ten characters: stepping one position at a time reads 87,923 characters at 128 patterns. The bad-character rule alone reads 87,923 — it has stopped skipping entirely, which the shift a set of patterns allows measured and explained. The published rules read 41,580. The exact rules read 41,580.

Identical. Not close: the same number, at 32, 64 and 128 patterns.

At small sets they differ: 13,084 against 12,306 at two patterns, 12,211 against 12,069 at four, 23,551 against 22,551 at eight. The published rules read between zero and six per cent more, and the difference vanishes as the set grows.

What each table is doing, in the run #

The formula combines three quantities and it is worth seeing which of them decides a shift in practice, because the answer changes with the pattern set.

At one pattern the character table dominates. There is one word in the trie, $d_1$ and $d_2$ are both the pattern’s length wherever the word has no self-suffix, and the shift is essentially the bad-character rule — which is Horspool’s matcher, the one that ships in every string library that skips.

At eight patterns the trie has shared suffixes and $d_1$ has become small at many nodes, so the $\max$ is often the character term and the $\min$ with $d_2$ often binds. The shift is a genuine combination.

At 128 patterns almost every node has a failure child one level down, $d_1$ and $d_2$ are both one or two nearly everywhere, and the shift is decided by $d_2$ regardless of the character. The run’s mean shift is 2.03 against a ceiling of ten.

So the same formula is three different rules at three set sizes, and the collapse of the character term is the effect the shift a set of patterns allows measured: a shift must be safe for every pattern, so its table is a minimum over the set, and a minimum over 128 patterns is small.

Where the approximation is #

The formula has a $\min$ with $d_2$ in it, and that is the whole of what makes it an approximation rather than the exact rule under another name.

The exact good-suffix condition asks whether the segment already read can line up with some pattern at the new offset. $d_1$ asks a weaker question — whether the segment can reappear deeper in the trie — which is implied by the first but does not imply it.

And $d_2$ is applied unconditionally. It guards against a pattern ending inside the window’s new position, whether or not the good-suffix condition would have allowed a larger step.

So the published shift can never exceed the exact one and is free to fall short of it. That is precisely the property a published rule must have — safety is not negotiable and tightness is — and it is measured rather than assumed in what the approximation gives up, across every decision either rule could ever make.

The character table, and the case it handles badly #

char($c$) is the crudest of the three tables and the one that carries the most weight on a wide alphabet.

For a character no pattern contains, it returns the shortest pattern’s length plus one, so the window jumps the maximum. That is the case a wide alphabet makes common — on twenty-six symbols with a few patterns, most characters appear in none of them — and it is where a skipping matcher gets its best behaviour.

For a character that appears near the right-hand end of any pattern, it returns something small, and it does so for every pattern in the set. That is the minimum-over-the-set problem the ceiling the shortest pattern sets is about: a shift has to be safe for all of them, so one pattern with an e in its last position makes every e in the text a small shift for the whole set.

With eight patterns of ten characters over four symbols, nearly every character appears near the end of something, which is why the bad-character rule alone reads the entire text.

The safety check is a comparison against exhaustion #

Every run in this strand is checked against a naive matcher that examines every position, and the check is on the occurrence list rather than on its length.

That is what catches an unsafe shift, and an unsafe shift is the failure this machinery invites: a rule that steps one position too far misses occurrences, and every occurrence it does report is real. The counts differ only if the missed occurrence is not also found somewhere else.

The gate’s rejection test raises $d_1$ to the maximum at every node — a change that looks like an optimisation, since larger shifts mean fewer windows — and requires the comparison to notice. Measured: two occurrences reported where there are eight.

Both counts, again #

A plate reporting a skipping matcher’s cost has to report two numbers, and this strand inherits the rule from the phase that established it.

Characters examined is what the matcher spends: 41,580 at 128 patterns under the published rules. A window that overlaps its predecessor re-reads characters, so this number can exceed the text’s length — under no rule at all it is 87,923 on a text of twenty thousand.

Distinct positions read is what it skipped: 17,405 of 20,000 at 128 patterns, so a fifth of the text was never looked at.

The two move differently as the set grows — the first because windows overlap more, the second because the shifts shrink — and a plate showing one of them chooses the answer. That convention came out of the earlier measurement, where the two counts cross at different set sizes.

Why this is not simply the exact rule computed cleverly #

A reader who has followed the measurement to this point could reasonably ask why the exact rules are ever computed, if the published ones agree with them on everything but small sets and cost a fraction as much.

The answer is that the agreement is a measurement rather than a theorem. The published rules are provably safe and provably no larger than the exact ones; nothing proves they are equal, and on a pattern set constructed to separate them they would not be. What this strand establishes is that on randomly drawn sets over a small alphabet they are equal from eight patterns up — which is a fact about those sets.

The exact rules are therefore the reference rather than the implementation. They are what the published ones are checked against, they are what makes “the approximation gives up 6.3 per cent at two patterns” a measurement rather than a guess, and they are computable at the sizes where the check is worth running.

That relationship — an expensive exact quantity kept as a reference for a cheap approximate one — is the same one how close anything gets to the floor sets up between a bound and an algorithm, and it is the reason both exist in this collection’s code rather than only the one that ships.

What this settles #

The direction after the phase that built the exact rules asked for one thing: the position of the published functions on the scale between no rules and exact rules. The answer is that on this pattern family they are not on the scale at all — they are at the exact end of it, for a construction cost that grows linearly rather than quadratically.

That is a stronger result than expected and it is bounded in a specific way: it is a statement about pattern sets drawn uniformly at random over a small alphabet, at one pattern length, on one text family. Where the two rules differ at all is on small sets, which is where the exact rules are cheap enough to build anyway.

The two essays after this one take the two halves of that apart: how much is given up, and what the difference in construction cost is worth.

The agreement is smaller news than it looks #

Reading “the published rules and the exact rules produce the same number at 32, 64 and 128 patterns” as a verdict on the approximation is the natural mistake, and the run’s own shift distribution is what corrects it.

The mean shift at 128 patterns is 2.03 against a ceiling of ten, and a shift is a positive integer. So almost every decision in that run is choosing between one and three, the published rule can never exceed the exact one, and the interval between them contains at most a position or two. The two rules agree because neither of them has any room left to disagree in. Agreement measured in that regime is a statement about how little the tables are distinguishing, not about how well the cheap one imitates the dear one.

The trend across the sweep says the same thing twice. The scan gap runs 6.3 per cent at two patterns, 1.2 at four, 4.4 at eight, and zero from thirty-two upwards; the decision-level plates find two differing pairs of eighty-four at two patterns and two of a hundred and fifty-six at four. Both the rate of disagreement and the size of the largest disagreement fall together, and they fall for one reason — a shift that has to be safe for a hundred and twenty-eight patterns at once is small, and small quantities have few values to be wrong about. That is the same collapse the ceiling the shortest pattern sets measures on the character table, arriving here as a property of the comparison rather than of the matcher.

Put the two ends of the sweep together and the practical conclusion is sharper than either alone, and it argues against the exact rules rather than for them.

Where the exact rules would be worth having — a large set, where a matcher is reading forty thousand characters instead of eighty-eight — they buy nothing, because the published tables already return every position the exact ones would. Where they buy anything at all — two to eight patterns — the difference is a few per cent of a scan that was already cheap, against a construction the plates put at four times the price by eight patterns and a hundred and thirty-seven times by a hundred and twenty-eight.

So the exact rules are not an implementation that lost on constants. They are an instrument, and this essay is the reading it was built to take: the approximation is exact where it matters and slightly loose where it does not. Which rule is cheaper is a question about the text only after both have been shown to skip the same distance, and that is what the identity above establishes — and what a single-pattern matcher, where the shift the pattern already knows is computed exactly and cheaply, never has to establish at all.

The honest limit #

The patterns here are drawn uniformly at random with the condition that none is a substring of another, and a real pattern set is not like that: it has shared prefixes, shared suffixes, and a length distribution. Both tables are functions of the trie’s suffix structure, so a set with heavy sharing gives smaller $d_1$ and $d_2$ and less skipping under both rules.

The construction counts are in character comparisons for the exact rules and in node visits for the published ones, which are not the same act. The comparison between them in this essay is a comparison of counts of primitive steps, and the essay that takes it seriously says so.

And the failure-link construction here walks the failure children rather than deriving them in one pass with the standard queue, so its own constant is larger than a careful implementation’s. That makes the linear side of the comparison pessimistic, which is the safe direction.