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

String matching — where it appears

Locating a pattern in a text exactly, where the cost is proportional to the text and the interesting question is what fraction of it is read at all. The interesting quantity is what fraction of the text was read at all, which separates a matcher that skips from one that reads every character once.

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

—gactacgat—gattacagt0123456789101234567821012345673211123456432212345554332123456543321234765443222387655432339876554333one unit = one subproblem given a value100 cells, 100 held at once

A distance that is a path through a grid

How far apart two strings are is a shortest-path problem on a grid whose every edge is drawn by the recurrence — and finding a string in a text costs 4,988 character comparisons where measuring how far it is from one costs 96,000.

text · Distance 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 1,00010,000110occurrences12481632characters in the collection · copies aboveall occurrencessecondaryprimarypattern "ss is un" · z = 1561 primary · 31 secondary

The occurrences that cross a boundary

One pattern, thirty-two copies of a text, thirty-two occurrences. The search finds one of them and produces the other thirty-one by arithmetic, and the count it finds is the same one at two copies, at eight and at thirty-two — the searching does not grow when the answer does.

text · Parse 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 —1234152abcbcbccbsolid: a transition on a character · dashed: a suffix or failure link8 states ≤ 9, 9 transitions ≤ 11

Every substring, in fewer states than substrings

A text of 512 characters has 129,416 distinct substrings. A machine that recognises every one of them, and nothing else, needs 831 states — and the bound it is under, 2n − 1, is reached exactly by a string one line long.

structures · Automaton ·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 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.

MeasurementCommentz-walterMulti patternPreprocessingShift ruleAho-corasickTrieAlphabetCrossoverFailure linkGood-suffix rulePattern matching

All concepts