The case a failure link does not cover

The table the links already knew splits the exact good-suffix condition into two cases and shows that the first of them is the failure-link relation the published rule already computes. This essay is about the second case, which is the part somebody arriving at that observation would most naturally leave out.

Leaving it out produces shift values that are too large, which is the unsafe direction.

The case, once more #

The matcher has read backwards from the window’s end and spelled the word of a trie node $v$, of length $j$. It asks how far the window may move without stepping past a place a pattern could end.

A shift of $d$ is allowed if some reversed pattern $r$ agrees with the known segment at that offset. There are two ways for that to happen:

The segment fits inside the pattern. $\text{word}(v)$ occurs in $r$ starting at offset $d$ — which is case one, and is $d_1$.

The segment hangs off the end. The pattern ends before the segment does, so only the part of the segment that overlaps has to agree: $r[d..|r|-1]$ equals a prefix of $\text{word}(v)$.

The second case is where a shorter pattern lines up with the tail of the window. The ceiling the shortest pattern sets is the essay about what a short pattern does to a set’s shifts in general, and this is the same short pattern making a different kind of trouble: not capping every shift, but permitting one that case one would have refused. It is not a corner case and it is not rare — it is what happens whenever the pattern that could end at the new window position is shorter than the segment already read.

What omitting it does #

The minimum over two sets is at most the minimum over one of them. Drop case two and every entry is at least as large as the exact one, and some are strictly larger.

Measured on eight patterns of eight characters over four symbols: eighteen of the twenty-two trie nodes get an inflated good-suffix value, each by one position.

One position sounds harmless, and on most windows it is: the extra position skipped usually holds nothing. It is not harmless in general, because the shift is a licence: the matcher moves the window by that many places and never looks at what it passed. An entry one too large means one window position never examined, and a pattern could have ended there.

What it costs on a text #

On twenty thousand characters with the patterns actually present at a density of one in five:

• occurrences in the text: 2,025
• occurrences the inflated table finds: 1,959
• occurrences it misses: 66

Every one of the 1,959 is a genuine occurrence at a genuine position. Nothing about the run is anomalous: the matcher terminates, the shifts are all positive and all at most the shortest pattern’s length, and it reads fewer characters than the correct version, which on a plate about skipping looks like an improvement.

Why the first text tried found nothing #

Worth recording, because the check that caught this failed twice before it worked.

On twenty thousand characters of uniform random text with no patterns planted, the inflated table skips past nothing at all. There are almost no occurrences in such a text — a set of eight-character patterns over four symbols occurs a handful of times in twenty thousand characters by chance — so the windows the matcher wrongly skips are almost never windows holding an answer.

So the first version of this check reported an unsafe rule as safe, and it did so with eighteen inflated entries sitting in the table. The rule was wrong, the check ran, and the check passed.

The fix is the one the fleet’s own gotchas keep arriving at: an unsafe shift is only visible where an occurrence sits in the span it steps over, so the text has to contain occurrences at a rate a real search would meet. Planting them at one in five makes the check fail every time and makes it fail by sixty-six.

That is a general shape for checking a skipping algorithm. The thing being tested is what happens in the region not examined, and a test input where that region is empty tests nothing.

An example of case two, worked #

Two patterns: edcba and bazz. Reversed — which is the order the trie is built in and the order the matcher reads — they are abcde and zzab. The shortest pattern is four characters, so no shift can exceed four.

Take the node whose word is abc, which the matcher reaches after reading three characters backwards from the window’s end.

Case one asks: does abc occur inside a reversed pattern at an offset of at least one? In abcde it occurs at offset zero and nowhere else; in zzab it does not occur. So case one offers nothing below the ceiling of four.

Case two asks: is a suffix of some reversed pattern, starting at offset $d \ge 1$, a prefix of abc? The reversed pattern zzab has the suffix ab starting at offset two, and ab is a prefix of abc. So $d = 2$ is allowed.

The exact good-suffix shift at that node is therefore 2, and a construction using the failure links alone gives 4. Measured, on exactly those two patterns: the nodes abc, abcd and abcde all come out at 4 instead of 2.

What the matcher would step over is a window position where bazz could end — which is the whole content of case two, in one instance. The known segment abc hangs off the end of the shorter pattern, only the part that overlaps has to agree, and it does.

Safe and exact are different properties #

This is the distinction the whole shift strand rests on and it is worth stating in one place.

Safe means the shift never exceeds the exact one. A safe rule may fall short — it moves the window less far than it could have, reads more characters than necessary, and finds every occurrence.

Exact means the shift is the largest one the condition permits. An exact rule is safe by definition.

The published Commentz-Walter rules are safe and not exact, and what the approximation gives up measures the cost of that: between zero and 6.3% more characters read, depending on the pattern-set size. The construction in this essay is neither — it is not exact, and it is not safe.

The asymmetry between the two directions of error is total. Falling short costs reads, which a plate shows and a user tolerates. Overshooting costs answers, which nothing shows.

Why the published rule’s guard is where it is #

The published rule computes $d_1$ — case one — and then takes the minimum with a second table, $d_2$, restricted to nodes that end a pattern.

That min is exactly the guard this essay’s broken construction is missing, arrived at from the other direction. $d_2$ asks “how far to a node where a whole pattern ends”, which is a bound on how far the window can move before passing a position where a pattern could finish. It is not case two — it is a different, weaker condition that happens to be safe — and taking the minimum with it is what keeps the published rule from ever exceeding the exact one.

So the published rule is safe by construction and inexact by construction, and the two facts have one cause. The exact rule replaces the guard with the real second case, which is tighter and is not free.

The check, and what it has to compare #

The rejection test in this site’s gate does three things, and the order matters.

First it builds the inflated table and requires at least one entry to exceed the exact one. If none did, the case would be doing no work on that pattern set and the check would pass for the wrong reason.

Then it runs the matcher with the inflated table over a text containing occurrences, and requires occurrences to be missed. A table with too-large entries that never gets to use them is a table whose defect has not been demonstrated.

And it reports both numbers — eighteen inflated entries, sixty-six missed occurrences — because they are different claims. The first is about the construction and the second is about what the construction does, and a check asserting only the first would pass on a rule that was inflated in a place no window ever reaches.

That three-part shape is what this collection means by a check that must reject: not “does the broken version fail” but “does it fail for the reason the essay says, on an input where the reason applies”.

Why the inflated rule still terminates and still looks fine #

A search whose shift table is wrong could plausibly loop, overrun, or produce nonsense positions. This one does none of those, and the reasons are worth listing because they are what makes the failure quiet.

The shifts are still positive. Every entry is at least one, so the window always advances and the scan always terminates.

The shifts are still bounded by $w_{\min}$. The ceiling is the third case and it is untouched, so no shift is absurd and an assertion about the ceiling — which this collection has — passes.

The matches it reports are found the same way. An occurrence is reported when the backward walk reaches a terminal node of the trie, which has nothing to do with the shift table. So every reported match is a real match at a real position, in the right pattern.

And it reads fewer characters, because it skips further. On a plate of characters read it is the best rule in the set.

Four properties that all hold, and the fifth — that it finds every occurrence — is the only one that does not. This collection’s own gate for the shift rules already had an assertion about the ceiling and a rejection test that inflates a shift on purpose; neither would have caught this, because the ceiling holds and the inflation here is not deliberate.

That is the same lesson this collection recorded about a helper whose two call sites both happened to ask about a maximum: a structure is only as checked as the questions asked of it, and a shift table asked only about its bounds can be wrong in every entry and right about its bounds.

What a reader deriving this would have done #

The path to the broken construction is short and reasonable, which is why it deserves an essay rather than a footnote.

Read that $d_1$ is the failure relation. Notice that the exact good-suffix condition is about the segment occurring in a pattern. Conclude that the exact rule is $d_1$ without the published rule’s min, since the min is described everywhere as the thing that makes the rule an approximation.

Every step of that is nearly right. The mistake is that the published rule’s min is doing two jobs — it makes the rule safe, and it makes it inexact — and removing it removes both. What replaces it in the exact rule is not nothing; it is the second case, which is tighter than the guard and is why the exact rule skips further.

The same failure, in three other structures here #

An entry that is too permissive, in a structure whose whole job is to let a search stop looking. This collection now has four.

The pruning that loses an occurrence is the version in the index walk: a lower bound applied one character late, or computed on the wrong end of the pattern, abandons states holding answers and reports only real ones.

The threshold that reaches zero is the version in the counting filter: a threshold one above what the lemma allows rejects windows that hold occurrences. The filter that proposes everything is the same filter at the other extreme, where the threshold is so low that nothing is excluded — the two ends of one parameter, one of which loses answers and one of which loses the point.

The occurrences that cross a boundary is the version in the phrase index: a search that reports its primaries and skips the propagation returns one thirty-second of the answer on a collection of thirty-two copies.

Four mechanisms, one shape. In each case the structure is a licence to skip, the defect makes the licence too broad, and the output is a subset of the truth with nothing in it that is wrong. And in each case the only check with teeth compares against exhaustion on an input small enough for exhaustion — which is why every measurement in this strand runs at twenty thousand characters rather than at a size that would be impressive.

The two cases have different shapes, and only one is a tree walk #

A last structural observation, because it explains why the second case is the one that gets dropped and not merely the one that is harder.

Case one is a question about descendants in the failure tree: which nodes have this node’s word as a suffix, and how much deeper is the nearest. It is answered by looking down one level, and the answer for each node is independent of the answers for the others.

Case two is a question about ancestors in the trie, combined with a relation between whole patterns and nodes. It needs two structures — a value $S[a]$ per node, filled by walking each pattern’s failure chain, and then a running minimum propagated down the trie from the root. Neither pass is hard and neither is local.

So case one is the kind of thing a failure-link construction naturally produces and case two is not, which is exactly why an implementation derived from “d₁ is the failure relation” arrives at the broken version. The generalisation: a derivation that starts from an existing structure tends to find the cases that structure was already shaped for, and the cases it was not shaped for are the ones that go missing.

What the corrected construction is worth to a reader is not a shift count but a crossing, because a rule that reads less and costs more to build only wins past some length of text.

The construction, once more, with the guard in the right place #

Three quantities and a minimum, and it is worth writing the finished rule out because the essay has been about what happens when a term is missing.

$$\text{good}(v) = \max\Big(1,\ \min\big(d_1(v),\ \text{ancestorBest}(v),\ w_{\min}\big)\Big)$$

$d_1(v)$ is case one, the least depth increase to a failure child. $\text{ancestorBest}(v)$ is case two, the least $S[a] - \text{depth}(a)$ over the proper ancestors, where $S[a]$ is the shortest pattern having $\text{word}(a)$ as a suffix. And $w_{\min}$ is the vacuous case, which is the ceiling.

Take away the second term and the shifts inflate, which is this essay. Take away the third and they exceed the shortest pattern, which the ceiling the shortest pattern sets shows is unsafe for the same reason. Take away the first and the rule is safe and useless.

Each term is a way for a shift to be allowed, so the shift is the smallest allowed one and a missing term is a permission not granted — which is the safe direction — while a missing minimum is a permission wrongly granted. That asymmetry is why dropping case two is dangerous and dropping case one would not be, and it is worth knowing which of a rule’s terms is which before simplifying one away.

What is being claimed #

Omitting the second case inflates eighteen of twenty-two trie nodes’ good-suffix values, each by one position, on a set of eight patterns.

A matcher using the inflated table misses sixty-six of 2,025 occurrences on twenty thousand characters, and reports 1,959 genuine ones.

On text without planted occurrences it misses nothing, which is why the first version of this check passed and why the check now plants them. A skipping algorithm’s defect lives in the region it did not examine, and a test input whose skipped regions are empty is a test of nothing — the same reasoning the pattern that defeats the pattern uses to construct an input that makes a matcher’s best case impossible.

Safe and exact are different properties. The published rule is safe and inexact; this construction is neither, and the difference between the two failure modes is that one costs reads and the other costs answers.

And the published rule’s min with $d_2$ is the guard that does the job case two does, more weakly and more cheaply — which is why removing it looks like a simplification and is not.

The compact form, for a reader who wants one sentence: the published rule replaces the second case with a cheaper guard and comes out safe and short; dropping the second case and keeping no guard comes out neither.