Concept

Sublinear — where it appears

Reading less of the input than there is of it, which for a matcher means never examining most of the text. It is a property of the pattern length and the alphabet rather than of the algorithm, and it fails quietly when either moves.

Named by 3 essays across 2 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.

text · Symbol

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

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

Named alongside it

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

Aho-corasick Alphabet Measurement Multi pattern Pattern matching Preprocessing Shift rule Trie Counterexample Asymptotic notation Bad-character rule Boyer moore

All concepts