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

Aho-corasick — where it appears

A trie of many patterns with failure links, which reads a text once and finds every occurrence of every pattern. Its cost is one read per position whatever the set holds, which is the flat line every skipping matcher is measured against.

Named by 7 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 roothseirhesssolid: a transition on a character · dashed: a suffix or failure link10 states for 12 pattern characters

One pass for every pattern at once

Sixty-four patterns, one text, twenty thousand characters read. Running this site's KMP once per pattern reads 1,595,445 — and an implementation missing one kind of link finds fewer occurrences, reads exactly as much, and looks better on every counter.

text · Automaton 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 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

Named alongside it

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

MeasurementMulti patternPreprocessingShift ruleTrieAlphabetCommentz-walterString matchingFailure linkGood-suffix rulePattern matchingSublinear

All concepts