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

Multi pattern — where it appears

Searching for a set of patterns at once rather than one at a time, which is a different problem from running a single-pattern matcher repeatedly. The set is the parameter: its size decides the structure and its shortest member caps every shift a skipping matcher can take.

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

8 patterns of 10 characters over four symbols02,0004,0006,0008,00010,00012,00014,00016,00018,000one cell = 10 positions · shade = fraction read61.6% of the text

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.

text · Symbol 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,00010,00010³10⁴characters of textcomparisons, built and scannedcrossing at n = 32,000both rules, exactlythe 1979 tables2 patterns of 10 · four symbolscrossing n = 32,000

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.

practice · Symbol the same 16 patterns, one of them shortenedshortest 1658.4%mean shift 3.15shortest 1262.8%mean shift 2.99shortest 869.7%mean shift 2.64shortest 680.5%mean shift 2.35shortest 493.4%mean shift 1.98shortest 399.2%mean shift 1.71shortest 2100.0%mean shift 1.3716 patterns, 15 of them 16 characterstext 20,000

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.

wrong · 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 1,00010,00010³10⁴characters of textsteps, precomputation plus scancrossing at 8,000published rulesexact rules2 patterns · four symbolscrossing 8,000 · was 32,000

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.

practice · 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

Named alongside it

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

Shift ruleMeasurementPreprocessingCommentz-walterTrieAho-corasickFailure linkGood-suffix ruleString matchingPattern matchingAlphabetBad-character rule

All concepts