Shift rule — where it appears
Named by 10 essays across 4 fields — each of them below, with the objects they name alongside it.
The shift a set of patterns allows
Aho-Corasick reads every character of the text exactly once, whatever the number of patterns. Commentz-Walter reads backwards inside a window and steps over what it can, and on eight patterns of ten characters it looks at sixty-two per cent of a twenty-thousand-character text. The rule that does the skipping is not the one everybody implements.
The table that walks every pair
The exact shift rules cost 769,724 character comparisons to build for 128 patterns and the published ones cost 5,604. The scan they are both built for reads 41,580 characters, so one of the two constructions is eighteen times the work it is there to save.
The rule that pays on a long enough text
With two patterns, the cheap tables cost 106 steps and the scan reads 13,084 characters; the exact tables cost 594 and the scan reads 12,306. Below thirty-two thousand characters the cheap tables win the total, above it the extra skipping pays for them, and with thirty-two patterns there is no crossing at all.
The ceiling the shortest pattern sets
A matcher that skips is described as faster than one that reads every character, and the description leaves out what decides it. No shift can exceed the shortest pattern in the set, so adding one two-character pattern to fifteen of sixteen characters takes a run from reading fifty-eight per cent of the text to reading all of it twice.
The shift somebody published
The exact rules for shifting a multi-pattern window are a definition that quantifies over every pattern at every offset. The 1979 rules are two tables read off the trie's own failure links, they are computed in one pass, and on this pattern set they agree with the definition at every node.
Where the exact rules pay now
With a construction as cheap as the published one, the exact shift rules pay for themselves past eight thousand characters of text at two patterns, four thousand at four, and never at thirty-two — because by thirty-two patterns the two rules make identical decisions.
The case a failure link does not cover
Compute the exact good-suffix rule from the failure links alone and eighteen of twenty-two entries come out too large. The matcher then steps past sixty-six of two thousand and twenty-five occurrences, and every match it does report is a match.
The table the links already knew
The exact good-suffix rule costs 757,058 character comparisons to build from its definition at 128 patterns, and 3,824 from the trie's failure links. Same table, checked at every node — a factor of 198, and the definition was never the algorithm.
What the approximation gives up
Compared at every one of the 3,736 decisions a search could ask about, the published shift rules and the exact ones agree at all of them on a set of 128 patterns. At two patterns they differ at five of 84, by up to four positions — and the run reads 6.3% more characters.
The ratio that was an implementation
This collection published a factor of forty-two between two shift rules' preprocessing. Sixty-nine per cent of the denominator was a table the published rule never reads, and the numerator was a definition rather than a construction. The corrected ratio is 1.6.
Named alongside it
The objects these essays reach for when they reach for this one.
MeasurementMulti patternPreprocessingCommentz-walterTrieAho-corasickGood-suffix ruleFailure linkString matchingBad-character ruleConstructionPattern matching