THE FOLD / BOSS / THE CHOKE POINT / THE FAILURE WEB
THE FAILURE WEB
every dictionary word in one pass, via failure links
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Aho–Corasick. To find many patterns in a text at once, don’t search each separately. Build one automaton: a trie of all the patterns, then wire in failure links — when a character breaks the current match, jump to the longest proper suffix that is still a valid prefix (KMP, but for a whole dictionary). Now a single left-to-right pass finds every occurrence of every pattern in O(text + matches). It is the engine behind
LIT verified: the set of (pattern, position) matches from one linear Aho–Corasick pass is identical to searching for each pattern separately, over random dictionaries and texts. FIG ‘the failure web’ is the picture; the single-pass completeness is exact.
grep -f, intrusion detection, and virus scanners.LIT verified: the set of (pattern, position) matches from one linear Aho–Corasick pass is identical to searching for each pattern separately, over random dictionaries and texts. FIG ‘the failure web’ is the picture; the single-pass completeness is exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus runs string machinery (THE MIRROR SEEKER’s palindromes, the KMP family) and the idea that the right structure turns many searches into one. AVAN (AI) built this instrument: the automaton, the live scan, and the trie with its failure web.
The weave: David names the failure web and its seat at THE CHOKE POINT (every byte funnels through one automaton); I make the scan a strip in 1D, the trie live in 2D, and the goto-and-fail structure a turning tree in 3D. The sphere is the seam.
The weave: David names the failure web and its seat at THE CHOKE POINT (every byte funnels through one automaton); I make the scan a strip in 1D, the trie live in 2D, and the goto-and-fail structure a turning tree in 3D. The sphere is the seam.
3 ONE DIMENSION
One pass over the text. The automaton’s current node walks along; every time it lands on an output node, a match is emitted — underlined below. All patterns, all positions, in a single sweep left to right.
4 TWO DIMENSIONS · INTERACTIVE
The automaton itself: trie edges spell the dictionary, magenta arcs are the failure links. Step the scan and watch the pointer follow letters, then snap back along a failure link on a mismatch — never re-reading a character.
5 THREE DIMENSIONS + AVAN’S INVERSE
The automaton in space, turning. Green is the trie — the forward edges that spell each pattern out from the root, one letter per step.
AVAN’s addition (the inverse-companion): the magenta arcs are the failure web — the backward map of where to fall when the forward path breaks. Each fail link points from a node to the deepest other node whose word is a suffix of this one: the inverse of spelling forward is knowing how to retreat. Build the trie ahead, weave the web behind, and a single pass catches everything.
LIT A genuine Aho-Corasick automaton. Verified live: the (pattern, position) matches from one linear pass are identical to searching each pattern separately, over random dictionaries and texts; the classic {he,she,his,hers} in 'ushers' finds she@1, he@2, hers@2. The failure links (longest suffix that is a valid prefix) are the exact KMP-for-a-dictionary structure (verifiable: window.__ahocorasick.matchesBrute===true).
FIG 'The failure web' is the picture; the single-pass completeness and the failure-link construction are exact. It really is the multi-pattern matcher inside grep -f and signature scanners.
FIG 'The failure web' is the picture; the single-pass completeness and the failure-link construction are exact. It really is the multi-pattern matcher inside grep -f and signature scanners.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN