Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Good-suffix rule — where it appears

A shift condition that uses the segment already matched: a window may only move to a position where that segment still lines up with some pattern. In a multi-pattern matcher it is approximated by the least depth increase to a trie node whose word has the matched one as a proper suffix.

Named by 6 essays across 3 fields — each of them below, with the objects they name alongside it.

101001,00010010³10⁴10⁵characters of pattern in the setcomparisons before the scanboth rules, exactlybad character onlythe 1979 shift functionsfour symbols · patterns of 10137.35x at 128 patterns

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.

bounds · Symbol ·1, 4b1, 3b1, 2b4, 2a4, 2a2, 2a4, 2b4, 2b4, 2b4, 2patterns abbb, baab, bbab · shortest 4d₁, d₂ under each node · a filled node ends a patternthe reversed-pattern trie10 nodes

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.

text · Symbol good suffix, defined757,058good suffix, from links3,824bad character, defined12,666bad character, swept5,168128 patterns · 1,280 characters of patternfour symbols · m = 10198x and 2.5x

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.

bounds · Symbol 101001,00010010³10⁴10⁵total length of the pattern setprimitive stepsthe definitionfrom the linksthe published rulefour symbols · m = 1085.60x apart at 128 patterns

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.

text · Symbol short by 133.6% of pairsshort by 211.2% of pairsshort by 411.2% of pairsthe same shift7994.0% of pairspatterns of 10 over four symbolsthe published rule is never the larger of the twoshift decisions84 pairs · 21 nodes

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.

wrong · Symbol 101001,00010100total length of the pattern settimes the published rule's precomputationwritten as a definitionbuilt from the linksthe published rulefour symbols · m = 10137x becomes 1.60x

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.

wrong · Symbol

Named alongside it

The objects these essays reach for when they reach for this one.

Commentz-walterShift ruleFailure linkMeasurementMulti patternPreprocessingTrieBad-character ruleAho-corasickConstructionString matchingConstant factor

All concepts