Foundations — Aho-Corasick — multiple pattern search, automaton

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

Pehle main note pe chadhne se pehle, tumhe woh vocabulary apni karni hogi jo woh bolti hai. Hum ise ek ek brick se build karte hain.

0 · Raw material — strings, characters, aur alphabet

Yahan sab kuch text ke baare mein hai: symbols ki ek row jo left to right padhi jaati hai.

$\Sigma$ symbol kyun? Kyunki baad mein, cost formulas count karte hain "ek slot per possible next letter", aur us slots ki sankhya hai hi $|\Sigma |$. Alphabet ko naam dene se hum us cost ke baare mein baat kar sakte hain.

Figure dekho: ek string bas ek line mein cells hain, har cell mein ek character hai. Cells ke neeche chhote index numbers tab matter karenge jab hum positions ki baat karenge — "match position 4 pe khatam hua".

1 · Prefix aur suffix — woh do halve jo sab kuch chalate hain

Yeh do words poore algorithm ka dil hain. Inhe galat samjha toh baaki kuch bhi nahi samjhega.

Aho-Corasick inse itna obsessed kyun hai? Kyunki machine ka poora kaam yeh hai:

"Kisi search word ka sabse lamba prefix jo abhi tak padhe gaye text ka suffix bhi ho."

Woh ek sentence dono concepts ek saath use karta hai. Jab koi letter ek match extend karne mein fail karta hai, toh "shortcut rope" tumhe sabse lamba proper suffix pe jump kara deta hai jahan tum the — jo abhi bhi kisi word ka prefix ho. Dono halve, phir se. Ise pakad ke rakho — yeh parent note ke Step 2 mein wapas aata hai.

2 · Set, aur $\sum |p_i|$ — ek poora dictionary measure karna

Hum ek word nahi dhundh rahe; hum ek saath words ka ek dictionary dhundh rahe hain.

Humein $M$ ki zaroorat kyun hai? Kyunki machine ki build cost $M$ (aur $|\Sigma |$) mein measure hoti hai, "number of patterns" mein nahi. Length 1000 ke do patterns build karne mein utna hi cost aata hai jitna length 1 ke 2000 patterns mein — jo matter karta hai woh total characters hain. $M$ ko naam dene se complexity line yeh precisely keh sakti hai.

3 · Graphs, nodes, edges — machine ki shape

Machine ek graph hai. Agar yeh word dara raha hai, toh yeh bas arrows se jude dots hain.

Tree kyun na ki plain list? Kyunki jo words same start share karte hain (he aur hers dono he se start karte hain) woh apne front edges share kar sakte hain, toh machine he ek baar store karti hai. Yahi sharing exactly woh hai jo ek tree deta hai aur ek list nahi.

4 · Trie — prefixes ka ek tree

Ab "tree" ko "prefix" ke saath combine karo aur tumhe pehla real structure milega.

Trie ke baare mein hum Trie — prefix tree mein zyada detail mein jaate hain; yahan tumhe bas chahiye: node = ek prefix, edge = ek character, terminal = ek word yahan khatam hota hai.

Hum iske teen operations name karte hain, parent note ke saath match karte hue:

• $\text{str}(v)$ = woh string jo node $v$ represent karta hai.
• $\text{go}[v][c]$ ya $\text{child}(v,c)$ = woh node jo tumhe $v$ se character $c$ labeled real edge follow karne pe milta hai (ho sakta hai exist na kare).
• terminal: ek node jo flag ki gayi hai kyunki ek poora pattern wahan khatam hota hai.

5 · Failure link — "shortcut rope"

Yeh genuinely naya idea hai; parent note ise fully derive karta hai. Yahan hum bas ensure karte hain ki symbol aur picture clear ho.

Yeh "hamesha shorter / hamesha upar" fact wahi hai kyun hum failure links ek specific order mein build karte hain — agla brick dekho.

Yeh idea directly single-pattern matching se liya gaya hai. Agar tumne KMP — single pattern matching dekha hai, toh failure link exactly KMP ka prefix function hai, lekin ek word ki jagah words ke poore tree pe spread kiya gaya hai.

6 · BFS — sabse pehle shortest strings process karna

Har failure link sahi se fill karne ke liye, humein nodes depth ke order mein visit karna hoga. Woh tool jo yeh karta hai woh BFS hai.

7 · Automaton aur uska transition $\delta$

Finally, topic title mein woh word: automaton.

Suffixes pe built string machines ka ek poora family hai na ki ek fixed dictionary — Suffix Automaton aur Suffix Tree dekho — aur doosre matching engines jaise Z-algorithm and string matching. Aho-Corasick "ek saath kaafi fixed patterns" ka specialist hai.

8 · Cost symbols — $n$, $M$, $\Sigma$, $z$, aur big-$O$

Aakhri brick: complexity line mein letters, taaki yeh English ki tarah padhe.

Prerequisite map

Ise upar ki taraf padho: characters se strings banti hain; strings prefixes/suffixes aur ek dictionary deti hain; graphs se trees milte hain, trees se trie milta hai; prefix + suffix + BFS se failure links milte hain; trie + failure links se automaton milta hai; cost symbols add karo aur tumhare paas poora Aho-Corasick machine hai.

Equipment checklist

Right side cover karo aur zor se jawaab do; agar koi ruk jaaye, toh main note se pehle woh section dobara padho.