Trie — where it appears
Named by 9 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.
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.
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 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.
The columns the candidates share
Three thousand tables against one query, and most of them begin the same way. Stored as a trie, the 2,424-word vocabulary has 7,710 distinct prefixes holding 17,239 letters, and a search that computes one column per prefix reads 61,449 cells against 156,714 — before it applies any bound at all. Apply the bound at a prefix instead of at a word and it reads 16,958, beating a list search that was told the answer in advance.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Multi patternShift ruleAho-corasickMeasurementPreprocessingCommentz-walterFailure linkGood-suffix ruleAlphabetPattern matchingString matchingBad-character rule