Visual walkthrough — Aho-Corasick — multiple pattern search, automaton

3.8.6 · D2 · Coding › String Algorithms › Aho-Corasick — multiple pattern search, automaton

Step 1 — Words ko ek tree ki tarah draw karo (the trie)

KYA. Hum chaaro words ko ek single tree mein stack karte hain jahan har edge ek letter carry karta hai aur har node ek "abhi-tak-ka-word" hai — yaani ek prefix.

KYUN. Agar hum har word alag rakhte toh shared beginnings baar baar re-scan karni padti. he, her, hers — teeno he se shuru hote hain; ek tree se woh shared start sirf ek baar walk hota hai. Yeh shared-prefix tree exactly ek trie hai.

PICTURE. Upar wale circle (root — empty word) se black edges follow karo. Kisi node tak letters padhte jaana us node ki string spell karta hai. Red rings terminal nodes hain: wahan ek poora dictionary word khatam hota hai.

Yahaan abhi failure links ki zaroorat nahi. Step 1 sirf pure spelling hai.

Step 2 — Woh problem jo sirf trie solve nahi kar sakta

KYA. Sirf trie se text match karne ki koshish karo aur dekho kaise fail hota hai.

KYUN. Ilaaj banane se pehle dard dikhna zaroori hai. Root se shuru karo, u, s, h, e padho — hum node she pe pahunch jaate hain. Ab text ka agla letter r hai. Node she ke paas r pe koi edge nahi hai. Ek naive trie kehta hai "dead end, root pe vapas jao" — aur hum sab kuch phek dete hain.

PICTURE. Red X us missing edge ko mark karta hai. Agar hum r pe root se restart karein, toh yeh fact kho denge ki humne abhi he match kiya tha (she ki tail), isliye hum thodi der baad hers miss kar denge.

Step 3 — Shortcut rope ko precisely define karo

KYA. Har node $v$ ke liye hum ek arrow define karte hain, uska failure link $\text{fail}[v]$.

KYUN. Hume ek rule chahiye, koi guess nahi, taaki computer ise build kar sake. Rule yeh hai: us node pe land karo jiska string $\text{str}(v)$ ka longest proper suffix ho jo trie mein abhi bhi ek node ho.

Har word unpack karte hain:

• she ka suffix: koi bhi tail — he, e, "".
• proper suffix: woh tail jo poori string nahi hai — isliye she khud exclude hai.
• "jo abhi bhi ek node hai": woh hamare trie mein spellable hona chahiye (kisi pattern ka prefix).

she ke proper suffixes mein, he ek node hai, e nahi, "" (root) hamesha hai. Longest node he hai. Isliye $\text{fail}[\text{she}]=\text{he}$.

PICTURE. Akela red arrow failure link she → he hai. Dhyan do yeh hamesha strictly shorter string ki taraf point karta hai (kam letters), aur kabhi neeche nahi.

Step 4 — KYUN in ropes ko shortest-first (BFS) banana zaroori hai

KYA. Hum saare failure links ko trie mein breadth-first order mein chalke compute karte hain — depth 1 nodes, phir depth 2, phir depth 3…

KYUN. Failure link hamesha ek shorter string ki taraf point karta hai (Step 3). Isliye jab hum node $v$ process karte hain, har node jis pe uski rope point kar sakti hai uske kam letters hain, yaani chhoti depth, aur isliye woh pehle se done hai. Shallow pehle process karo, deep baad mein — aur kuch bhi kabhi "not ready" nahi hoga.

PICTURE. Trie ko depth-layer se colour kiya gaya hai. Red layer woh frontier hai jise BFS abhi fill kar raha hai; us se nikalne wala har arrow upar pehle-se-finished (black) layer mein point karta hai.

Step 5 — Parent-chain rule jo har rope compute karta hai

KYA. "Longest proper suffix jo ek node hai" ko mechanical computation mein badlo parent ki rope use karke.

KYUN. Hum har suffix manually test nahi karna chahte. Yeh raha shortcut. Maano $v$ ka parent $p$ hai, letter $c$ se reach hua, toh $\text{str}(v)=\text{str}(p)+c$. $\text{str}(v)$ ka koi bhi proper suffix jo $c$ pe khatam hota hai woh $s+c$ jaisa dikhta hai jahan $s$, $\text{str}(p)$ ka proper suffix hai. $p$ ke proper suffixes jo nodes hain woh exactly $\text{fail}[p],\text{fail}[\text{fail}[p]],\dots$ hain — parent ki failure chain. Isliye:

$p$ ki failure chain upar walk karo. Pehle node $u$ pe jo $c$ pe child rakhta hai, us child pe jump karo. Wahi child $\text{fail}[v]$ hai.

PICTURE. $v=\text{she}$ ke liye: parent $p=\text{sh}$, letter $c=\text{e}$. sh se red chain follow karo: $\text{fail}[\text{sh}]=\text{h}$. Kya h ke paas e pe child hai? Haan → he. Isliye $\text{fail}[\text{she}]=\text{he}$, jo Step 3 se match karta hai.

Step 6 — Har transition fill karo (koi dead ends nahi bache)

KYA. "Mismatch pe, failure chain chase karo" ko ek complete table $\delta (v,c)$ se replace karo jis mein har node aur har letter ka jawab ho.

KYUN. Query time pe hum per character ek lookup chahte hain — koi chain-walking nahi. Isliye hum precompute karte hain ki har (node, letter) actually kahaan jaata hai. Definition sirf yeh kehti hai: agar real edge hai toh lo; warna failure link ke us hi letter ke liye jawab lo (jo BFS pehle se compute kar chuka hai).

PICTURE. Node she, letter r: koi real edge nahi (Step 2 wala X). Hum $\delta (\text{fail}[\text{she}],\text{r})=\delta (\text{he},\text{r})=\text{her}$ ka answer copy karte hain. Red dashed arrow woh filled-in transition hai she --r--> her. Dead end khatam.

Yeh ab ek genuine DFA hai: total, deterministic, ek move per letter.

Step 7 — Har landing pe kai words shout ho sakte hain (output links)

KYA. Jab hum kisi node pe land karte hain, hum sirf us node ka word report nahi karte balki har woh pattern jo yahaan suffix ke roop mein khatam hota hai — failure links ko root tak follow karke milta hai.

KYUN. she pe land karo. Uski string "s-h-e" hai; tail "h-e" bhi ek real pattern he hai, us hi text position pe khatam hoti hai. Woh match current node pe nahi, failure chain pe chhupa hai. fail follow karne se she se he (terminal) milta hai → dono report karo.

PICTURE. she se dictionary links ki red chain: she(✓) → he(✓) → root. Path pe do red rings = is position pe do matches.

Step 8 — Poora text finished machine se guzaro

KYA. ushers mein ek ungli chalao, exactly ek $\delta$-step per letter lete hue aur har landing se matches shouting karte hue.

KYUN. Yahi payoff hai: saari building ke baad, scanning ek flat loop hai, $O(n+z)$ — kitne bhi patterns store kiye hon us se independent, bilkul jaisa KMP ek pattern ke liye hota hai (KMP — single pattern matching).

PICTURE. Automaton mein traced path. Har dot ek landing hai; do red dots (e pe aur final s pe) wahan hain jahan words shout hote hain.

r pe transition woh moment hai jab Step 2 ka dead end humse hers chhin leta. Failure link ne apna kaam kiya.

Ek-picture summary

Upar sab kuch, compressed: Trie (black tree) → Tie (red failure links) → Try (text path). Ek machine, ek pass.

Flashcards