Aho-Corasick — multiple pattern search, automaton

3.8.6 · Coding › String Algorithms

HOW banate hain — scratch se derivation

Step 1 — Patterns ko trie mein insert karo

Har pattern ke liye, root se walk karo, naye characters ke liye child nodes banate jao. Final node ko us pattern ke liye terminal mark karo. Yeh sirf shared prefixes ko merge karna hai.

Step 2 — BFS se failure links compute karo

Failure rule ki derivation. Maano node $v$ ka parent $p$ hai character $c$ ke zariye (toh $str (v) = str (p) + c$ ). Hum chahte hain $str (v)$ ka sabse lamba proper suffix jo ek trie node ho.

$str (v)$ ka ek proper suffix jo $c$ par khatam hota hai, $s + c$ ki form mein hoga jahan $s$ $str (p)$ ka proper suffix hai.
Aisa sabse lamba $s$ jo ek node hai, $c$ ke baad followed by, wahi chahiye.
"p ka sabse lamba proper suffix jo ek node hai" ke candidates exactly $fail [p]$ , phir $fail [fail [p]]$ , … hain ( $p$ ki failure chain).

Toh:

fail [v] = go (first node u in {fail [p], fail^{2} [p], \dots} that has a child on c, c)

aur agar kisi ke paas $c$ par child nahi hai, toh $fail [v] = root$ . Root ke children ka $fail = root$ hota hai.

Step 3 — Automaton banao (lazy → full transitions)

Query time par failure chain chase karne se bachne ke liye, ek complete transition $δ$ precompute karo:

δ (v, c) = {child (v, c) δ (fail [v], c) if v has a real edge on c otherwise

$δ (root, c) = root$ ke saath agar root ke paas $c$ par koi child nahi hai. Usi BFS ke dauran compute kiya gaya, yeh har step ko $O (1)$ bana deta hai.

Step 4 — Text scan karo

Root par shuru karo. Har text char $c$ ke liye: state = δ(state, c); phir state ke output (dictionary) links ke zariye sabhi patterns report karo.

Figure — Aho-Corasick — multiple pattern search, automaton

Worked Example 1 — patterns {he, she, his, hers}

Text: ushers

Trie (nodes par strings): h, he(✓he), her, hers(✓hers), s, sh, she(✓she), hi, his(✓his).

Key failure links:

fail[she] = he? Nahi — "she" ka sabse lamba proper suffix jo ek node hai woh "he" hai. ✓ Toh fail[she]=he, aur kyunki he terminal hai, "she" scan karte waqt "he" bhi report hota hai.

Scan u s h e r s:

char	state	reports	Why this step?
u	root	–	koi edge `u` nahi, δ(root,u)=root
s	s	–	root ke paas child `s` hai
h	sh	–	`s`→`h` edge exist karta hai
e	she	she, he	`sh`→`e`; `she` ka output + fail `he` ke zariye
r	her	–	δ(she,r): she ke paas `r` nahi; fail→he follow karo, he→r=her
s	hers	hers	her→s = hers (terminal)

Worked Example 2 — patterns {a, ab, bab, bc, bca, c, caa}

Yeh interesting kyun hai: overlapping outputs. Text abccab scan karte waqt:

a → reports a
b → node ab, reports ab
c → δ(ab,c): ab ke paas c nahi; fail[ab]=b, b→c=bc, reports bc; saath hi bc ka fail c de sakta hai → reports c
aage chalte hue c phir milta hai, etc.

Common mistakes

Recall Feynman: ek 12-saal ke bachche ko samjhao

Tumhare paas forbidden words ki ek list hai aur ek giant book. Tum chahte ho ki har forbidden word jaldi milo. Pehle, saari words ko ek shared "word tree" mein likho taaki jo words ek jaisi shuru hoti hain (jaise "he" aur "hers") branches share karein. Phir shortcut ropes add karo: agar tum "she" spell kar rahe the aur agla letter fit nahi hota, root par bilkul vapas jaane ki jagah, ek rope tumhe "he" par gira deti hai — kyunki "he" "she" ki sabse lambi tail hai jo abhi bhi kisi word ki shuruat hai. Ab tum ek ungli book ke andar ek letter karke slide karte ho, branches ya shortcut ropes follow karte ho, aur jab bhi kisi marked jagah par pohunchte ho toh matched words shout karte ho. Ek pass, sabhi words, done.

Flashcards

Aho-Corasick kaunsi problem solve karta hai?

Text mein bahut saare patterns ke sabhi occurrences ek single pass mein dhundo,

O (n + M + z)

mein.

Node v ka failure link kya hota hai?

Woh node jo str(v) ke sabse lambe proper suffix ke barabar hai jo ek trie node bhi hai (kisi pattern ka prefix).

Failure links BFS order mein kyun compute kiye jaate hain?

fail[v] strictly chote string ki taraf point karta hai (smaller depth), toh badhti depth se process karne par saare zaroori fail values ready hote hain.

goto/transition δ(v,c) kya hota hai jab v ke paas c par koi real edge nahi hoti?

δ(fail[v], c) — failure link ke transition par recurse karo (root agar sab fail ho jayein).

Dictionary (output) links kyun follow karne chahiye, sirf terminal flag check nahi?

Ek chota pattern usi position par suffix ki tarah khatam ho sakta hai (jaise "she" ke andar "he"); woh matches failure chain par hote hain.

Query time complexity (full transition table ke saath)?

O (n + z)

: har char ke liye ek

O (1)

lookup plus z matches ka output; patterns ki count se independent.

Explicit transition table ke saath build time/space?

O (M \cdot Σ)

, jahan

M

= total pattern length,

Σ

= alphabet size.

str(v)=str(p)+c ke liye failure-link rule?

Parent p ki fail chain walk karo; pehla ancestor u jo c par child rakhta ho woh fail[v]=child(u,c) deta hai; warna root.

Trie mein ek node kya represent karta hai?

Ek prefix jo ek ya zyada patterns ke liye shared hai; root se chars ka path ise spell karta hai.

Aho-Corasick KMP se kaise related hai?

Yeh KMP ke prefix-function/failure-function ko ek single string se bahut saari strings ke trie tak generalize karta hai.

Connections

KMP — single pattern matching (failure function = ek path par special case)
Trie — prefix tree (skeleton structure)
Suffix Automaton / Suffix Tree (alag multi-substring machines)
Finite Automata — DFA/NFA (Aho-Corasick patterns par ek DFA hai)
Z-algorithm and string matching
BFS — breadth-first search (failure links banane mein use hota hai)