সরাসরি পর্বে যান
পর্ব ২৩ · ৮৫-এর মধ্যে · মডিউল ৪

String matching automaton — KMP আর Aho–Corasick

String Matching Automata — the KMP Automaton, the Failure Function and Aho–Corasick

Taught in Bangla, this lesson treats pattern search as recognizing Σ*P. It builds the (m + 1)-state string matching automaton and proves it tracks the longest prefix of P that is a suffix of the text, compresses it into the KMP failure function with an amortized O(n + m) bound. It extends to many patterns with the Aho–Corasick automaton. In-page Python (Pyodide) builds both, and a real desktop run benchmarks pyahocorasick against a hand-written Aho–Corasick and naive search.

এই পর্বে যা শিখবেন

  • একটি ধাঁচের string matching automaton MP-এর formal সংজ্ঞা, আর δ̂(0, x) = σ(x)-এর পূর্ণ প্রমাণ
  • Failure function π হাতে হিসাব করা, π থেকে δ-টেবিল বানানো, আর KMP-কে automaton হিসেবে পড়া
  • O(n + m) সময়ের amortized প্রমাণ, আর naive পদ্ধতির O(nm) কোথায় হারে
  • কেন একটি ধাঁচের DFA-তে 2m বিস্ফোরণ হয় না, আর কেন m + 1 state-ই ক্ষুদ্রতম
  • Aho–Corasick-এর trie, failure link আর output link; সত্যিকারের library-র সঙ্গে নিজের কোড মেলানো, বাংলা লেখার ফাঁদসহ

১ · ধাঁচ খোঁজার প্রশ্ন — SALE থেকে সাধারণ যন্ত্রে

বাজারঘরের অর্ডারের নোটে প্রতিদিন হাজার হাজার লাইন জমে। একজন কর্মী জানতে চান, কোন কোন লাইনে কুপন “SALE” আছে। পর্ব ০৮-এ আপনি ঠিক এই কাজের একটি DFA বানিয়েছিলেন: state i মানে “শেষ i অক্ষর SALE-এর প্রথম i অক্ষরের সঙ্গে মেলে”, আর অমিলে state 0-তে না গিয়ে আংশিক মিলে ফেরা। পর্ব ০৯-এ একই কাজ একটি ছোট NFA দিয়ে করেছিলেন, যে “এই S-ই শেষের SALE-এর শুরু” বলে অনুমান করে। এই পর্বে সেই দুটি ধারণাকে যেকোনো ধাঁচের জন্য সাধারণ করা হবে, প্রমাণসহ।

প্রশ্নটি এভাবে লেখা যায়। একটি ধাঁচ (pattern) P = p1p2⋯pm আর একটি লেখা (text) T = t1t2⋯tn, দুটিই একটি alphabet Σ-এর ওপর। এমন সব অবস্থান i বের করতে হবে, যেখানে ti−m+1⋯ti = P, অর্থাৎ P সেখানে শেষ হয়েছে। সবচেয়ে সরল উপায় হলো প্রতিটি সম্ভাব্য শুরুর ঘরে P বসিয়ে অক্ষর ধরে মেলানো (naive string matching). সবচেয়ে খারাপ ক্ষেত্রে এতে প্রায় n·m তুলনা লাগে। যেমন P = AAAAAAAAAB আর T = AAAA…A: প্রতিটি শুরুতে নয়টি A মেলে, তারপর দশম ঘরে অমিল।

ToC-এর চোখে প্রশ্নটি আরও সহজ। “T-এর প্রথম i অক্ষর P দিয়ে শেষ হয় কি না”, এটি Σ∗P language-এর membership. Σ∗P regular, কারণ এটি একটি regex. তাই এর একটি DFA আছে। সেই DFA-কে T-এর ওপর একবার চালালে, প্রতিটি অবস্থানে accepting state-এ থাকা মানেই সেখানে একটি মিল। প্রতি অক্ষরে একটি টেবিল-দেখা, মোট n ধাপ, কখনো পিছিয়ে যাওয়া নেই। প্রশ্ন শুধু দুটি: DFA-টি দেখতে কেমন, আর কত তাড়াতাড়ি বানানো যায়।

রেলস্টেশনের ঘোষণা মন দিয়ে শুনছেন, অপেক্ষা “চট্টগ্রামগামী সুবর্ণ” শব্দগুলোর জন্য। কয়েকটি শব্দ মিলে গেল, তারপর ভুল একটি শব্দ এল। আপনি পুরো ঘোষণা আবার গোড়া থেকে শোনেন না; মাথায় থাকে “শেষ যে অংশটুকু শুনেছি, তার কতটুকু এখনো কাজে লাগতে পারে”। String matching automaton ঠিক এই হিসাবটি রাখে, আর রাখে মাত্র একটি সংখ্যায়।

এই পর্বের notation: Pq = p1⋯pq হলো P-এর দৈর্ঘ্য q-এর prefix, P0 = ε. প্রমাণে অবস্থান ১ থেকে গোনা হয়; Python আর JavaScript কোডে ০ থেকে। DFA M = (Q, Σ, δ, q0, F), δ total, আর δ̂ পুরো string-এর transition (কিছু বইয়ে δ∗). n = |T|, m = |P|. একাধিক ধাঁচ হলে K = {P1, …, Pk}, আর M = মোট দৈর্ঘ্য |P1| + ⋯ + |Pk|. Algorithm-এর দিক থেকে KMP আর Rabin–Karp-এর বিস্তারিত কোড আছে DSA কোর্সের পর্ব ৫৮-এ; এখানে যন্ত্রের দিকটি, আর কেন সেটি সঠিক।

২ · String matching automaton — সংজ্ঞা আর সঠিকতার প্রমাণ

প্রথমে একটি function দরকার। যেকোনো string x-এর জন্য σ(x) হলো P-এর সবচেয়ে লম্বা সেই prefix-এর দৈর্ঘ্য, যা x-এর suffix:

σ(x) = max{ k : 0 ≤ k ≤ m আর Pk হলো x-এর suffix }

P0 = ε সবসময় suffix, তাই σ(x) সবসময় সংজ্ঞায়িত। উদাহরণ, P = ABABAC হলে σ(CABA) = 3 (শেষের “ABA” = P3), σ(ABABAB) = 4 (শেষের “ABAB”), আর σ(ABC) = 0. লক্ষ করুন, σ(x) = m ঠিক তখন, যখন x P দিয়ে শেষ হয়।

সংজ্ঞা ২.১ (String matching automaton)

ধাঁচ P (|P| = m)-এর string matching automaton হলো DFA MP = (Q, Σ, δ, 0, {m}), যেখানে Q = {0, 1, …, m}, আর প্রতিটি q ∈ Q ও a ∈ Σ-এর জন্য

δ(q, a) = σ(Pqa)

অর্থাৎ “P-এর প্রথম q অক্ষর মিলে আছে, এবার a এল; এখন P-এর সবচেয়ে লম্বা কোন prefix শেষে মিলছে?” State m থেকেও transition আছে, তাই একটি মিলের পরে যন্ত্র পরের, এমনকি পরস্পর-ঢাকা (overlapping) মিলও খুঁজে চলে। পর্ব ০৮-এর “কোথাও SALE আছে” DFA-তে state m সব চিহ্নে নিজের কাছে ফিরত; সেটি Σ∗PΣ∗-এর যন্ত্র, আর এটি Σ∗P-এর।

এখন দেখাতে হবে যে যন্ত্রটি সত্যিই σ হিসাব করে। দুটি ছোট lemma লাগে।

Lemma ২.২ (এক ধাপে বড়জোর এক বাড়ে): যেকোনো x আর a ∈ Σ-এর জন্য σ(xa) ≤ σ(x) + 1.

  1. r = σ(xa) ধরুন। r = 0 হলে কিছু প্রমাণের নেই। — তুচ্ছ ক্ষেত্র
  2. r ≥ 1 হলে Pr হলো xa-এর suffix, তাই Pr-এর শেষ অক্ষর a, আর Pr−1 হলো x-এর suffix. — শেষ অক্ষরটি দুই দিক থেকে সরানো
  3. σ-এর সংজ্ঞায় σ(x) ≥ r − 1, অর্থাৎ r ≤ σ(x) + 1. ∎ — σ(x) সবচেয়ে বড় এমন দৈর্ঘ্য

Lemma ২.৩ (শুধু শেষ মিলটুকুই যথেষ্ট): q = σ(x) হলে σ(xa) = σ(Pqa).

  1. Pq হলো x-এর suffix, তাই Pqa হলো xa-এর suffix. — q = σ(x)
  2. P-এর যে prefix Pqa-এর suffix, সেটি xa-রও suffix; তাই σ(Pqa) ≤ σ(xa). — suffix-এর suffix আবার suffix
  3. উল্টো দিকে r = σ(xa) ধরুন। Lemma ২.২-এ r ≤ q + 1 = |Pqa|. — Lemma ২.২
  4. Pr আর Pqa দুটিই xa-এর suffix, আর Pr ছোট বা সমান; তাই Pr হলো Pqa-এর suffix, আর r ≤ σ(Pqa). — একই string-এর দুটি suffix-এর ছোটটি বড়টির suffix
  5. ধাপ ২ আর ৪ মিলিয়ে σ(xa) = σ(Pqa). ∎
উপপাদ্য ২.৪ (MP সঠিক)

সব x ∈ Σ∗-এর জন্য δ̂(0, x) = σ(x). ফলে L(MP) = Σ∗P, আর T-এর অবস্থান i-তে P শেষ হয় ঠিক তখন, যখন t1⋯ti পড়ার পর state m.

প্রমাণ (|x|-এর ওপর induction):

  1. ভিত্তি: x = ε. δ̂(0, ε) = 0, আর σ(ε) = 0, কারণ ε-এর একমাত্র suffix ε = P0. — δ̂-এর সংজ্ঞা
  2. ধাপ: ধরুন δ̂(0, x) = σ(x) = q. তাহলে δ̂(0, xa) = δ(δ̂(0, x), a) = δ(q, a). — δ̂-এর সংজ্ঞা আর induction-এর অনুমান
  3. δ(q, a) = σ(Pqa), সংজ্ঞা ২.১ অনুযায়ী। — যন্ত্রের নিয়ম
  4. Lemma ২.৩-এ σ(Pqa) = σ(xa). তাই δ̂(0, xa) = σ(xa). — Lemma ২.৩
  5. সবশেষে δ̂(0, x) = m ⇔ σ(x) = m ⇔ P হলো x-এর suffix ⇔ x ∈ Σ∗P. ∎

প্রমাণটির সারকথা: পুরো অতীত মনে রাখার দরকার নেই, শুধু শেষের মিলটুকু, যা একটি সংখ্যা q. এই কারণেই সসীম যন্ত্রে কাজটি সম্ভব। এই নির্মাণ ও প্রমাণের ধাঁচটি Cormen ও সহলেখকদের “Introduction to Algorithms” বইয়ের string matching অধ্যায়েও আছে; সেখান থেকে মিলিয়ে নিতে পারেন।

৩ · Failure function — KMP-এর সংকুচিত automaton

সংজ্ঞা ২.১ সরাসরি মেনে δ বানালে প্রতিটি (q, a)-এর জন্য σ হিসাব করতে হয়, যা অনেক তুলনা। আরও ভালো একটি পথ আছে, আর সেটিই Knuth–Morris–Pratt (KMP) algorithm-এর হৃদয়।

একটি string-এর border হলো এমন একটি string, যা তার prefix-ও, suffix-ও, কিন্তু পুরো string নয় (proper). যেমন ABABA-এর border ε, A আর ABA. Failure function বা prefix function:

π[q] = Pq-এর সবচেয়ে লম্বা border-এর দৈর্ঘ্য (1 ≤ q ≤ m)

উপপাদ্য ৩.১ (π থেকে δ)

q < m আর a = pq+1 হলে δ(q, a) = q + 1. নইলে, q = 0 হলে δ(0, a) = 0, আর q ≥ 1 হলে δ(q, a) = δ(π[q], a).

প্রমাণ:

  1. a = pq+1 হলে Pqa = Pq+1, যা নিজেই P-এর prefix; Lemma ২.২-এ এর চেয়ে বড় হওয়া সম্ভব নয়। — সামনে এগোনো
  2. অন্যথায় r = σ(Pqa) ≤ q, কারণ q + 1 হতে হলে a = pq+1 লাগত। q = 0 হলে r = 0. — Lemma ২.২
  3. q ≥ 1 আর r ≥ 1 হলে Pr−1 হলো Pq-এর suffix, দৈর্ঘ্যে q-এর চেয়ে ছোট, অর্থাৎ একটি border; তাই r − 1 ≤ π[q]. — π-এর সংজ্ঞা
  4. Pπ[q]a হলো Pqa-এর suffix, দৈর্ঘ্য π[q] + 1 ≥ r. তাই Pr হলো Pπ[q]a-এর suffix, আর σ(Pπ[q]a) ≥ r. — ছোট suffix বড় suffix-এর suffix
  5. উল্টো দিকে Pπ[q]a নিজেই Pqa-এর suffix, তাই σ(Pπ[q]a) ≤ r. মিলিয়ে δ(q, a) = σ(Pπ[q]a) = δ(π[q], a). ∎ — Lemma ২.৩-এর ধাপ ২-এর মতো

এই উপপাদ্য দুটি জিনিস দেয়। এক, π জানা থাকলে পুরো δ-টেবিল O(m·|Σ|) সময়ে সারি ধরে ভরা যায়, কারণ δ(π[q], ·) সারিটি আগেই ভরা (π[q] < q). দুই, টেবিল না বানিয়েও চলে: অমিলে π ধরে পিছিয়ে যান, যতক্ষণ না a মেলে বা 0-তে পৌঁছান। এই “পিছিয়ে যাওয়া” কোনো input পড়ে না; এটি অনেকটা ε-transition-এর মতো একটি failure transition. KMP তাই একটি automaton, যার প্রতিটি state-এ মাত্র দুটি তীর: একটি সামনে (pq+1 পড়ে), আর একটি failure (কিছু না পড়ে π[q]-তে)।

π নিজেও একই কৌশলে বানানো হয়: Pq-এর border-গুলো হলো সবচেয়ে লম্বা border, তার border, তার border… (border-এর শিকল)। তাই π[q] পেতে আগের মান k = π[q − 1] থেকে শুরু করে দেখা হয় pk+1 = pq কি না; না মিললে k = π[k], আবার দেখা। P = ABABAC-এ হিসাবটি ধাপে ধাপে:

1π[1] = 0; k = 02q = 2 … m-এর জন্য:3  অমিল আর k > 0: k = π[k]4  p[k+1] = p[q] হলে k += 15  π[q] = k6ফল: π-এর পুরো সারি
এই ধাপের হিসাব
prefix Pq
শুরুর k
তুলনা
π এ পর্যন্ত
  1. শুরু। P1 = A-এর একমাত্র proper border ε, তাই π[1] = 0. k হলো “আগের prefix-এর সবচেয়ে লম্বা border-এর দৈর্ঘ্য”, শুরুতে 0.
  2. q = 2: B যোগ হলো। k = 0, তাই দেখা হয় p1 = A আর নতুন অক্ষর p2 = B সমান কি না। অমিল, আর k আগেই 0, তাই π[2] = 0: AB-এর কোনো অ-ফাঁকা border নেই।
  3. q = 3: A যোগ হলো। p1 = A মিলল, k = 1. ABA-এর শুরুতে A, শেষেও A: π[3] = 1.
  4. q = 4: B যোগ হলো। আগের border “A”-কে এক অক্ষর বাড়ানোর চেষ্টা: p2 = B আর নতুন B মিলল, k = 2. ABAB-এর border AB.
  5. q = 5: A যোগ হলো। আবার বাড়ল: p3 = A মিলল, k = 3, π[5] = 3. ABABA-এর সবচেয়ে লম্বা border ABA, যা নিজেই নিজের সঙ্গে খানিকটা ঢাকা পড়ে (ABA আর ABA মাঝের A ভাগ করে)।
  6. q = 6: C যোগ হলো। k = 3, কিন্তু p4 = B ≠ C. শিকল ধরে পরের border: k = π[3] = 1; p2 = B ≠ C. আবার: k = π[1] = 0; p1 = A ≠ C. আর পিছানো যায় না, π[6] = 0. লক্ষ করুন, এই এক ধাপে তিনটি তুলনা হলো।
  7. ফল। π = 0, 0, 1, 2, 3, 0. পুরো হিসাবে মোট তুলনা ৭টি (q = 2…5-এ একটি করে, q = 6-এ তিনটি), 2m = 12-এর কম; কেন সবসময় এমন হয়, তা §৪-এ। এখন উপপাদ্য ৩.১ দিয়ে এই π থেকেই পুরো δ-টেবিল আসে।

উপপাদ্য ৩.১ প্রয়োগ করলে Σ = {A, B, C}-এর ওপর MABABAC-এর পুরো টেবিল দাঁড়ায় নিচের মতো (→ শুরু, ∗ accepting). যেমন δ(5, B): p6 = C ≠ B, তাই δ(5, B) = δ(π[5], B) = δ(3, B) = 4; সরাসরি সংজ্ঞায়ও σ(ABABAB) = 4.

state qমিলেছেABCπ[q]
→ 0ε100—
1A1200
2AB3000
3ABA1401
4ABAB5002
5ABABA1463
∗ 6ABABAC1000

MABABAC: সামনের ছয়টি তীর আর পাঁচটি “আংশিক মিলে ফেরা” তীর

নীল-ধূসর তীর সামনে এগোয়। কমলা তীর অমিলে আংশিক মিলে ফেরে। ছবিতে না থাকা বাকি ১০টি তীর state 0-তে যায়।

String matching automaton for ABABAC: forward edges and the five non-zero back edges 0123 456 ABA BAC AAA AB বাকি সব তীর state 0-তে (আঁকা হয়নি)
ছবি ২৩.১ — ২১টি তীরের মধ্যে মাত্র ১১টি 0-ছাড়া অন্য state-এ যায়: ছয়টি সামনে, পাঁচটি পিছনে। State 6 থেকেও তীর আছে, তাই পরের মিলের খোঁজ চলতে থাকে।

নিচের Python ব্লক (ব্রাউজারে চলে) ঠিক এই কাজগুলো করে: π হিসাব, উপপাদ্য ৩.১ দিয়ে δ-টেবিল, সরাসরি সংজ্ঞা ২.১-এর σ দিয়ে টেবিলটি যাচাই, একটি লেখায় সব মিল খোঁজা, আর দৈর্ঘ্য 7 পর্যন্ত সব string-এ উপপাদ্য ২.৪-এর invariant পরীক্ষা। P বদলে নিজের ধাঁচ দিয়ে চালান।

from itertools import product
def prefix_function(P):                  # pi[i] = longest proper border of P[:i+1]
    pi, k = [0] * len(P), 0
    for i in range(1, len(P)):
        while k and P[k] != P[i]: k = pi[k - 1]
        if P[k] == P[i]: k += 1
        pi[i] = k
    return pi
def kmp_dfa(P, S):                       # delta built from the failure function
    pi, d = prefix_function(P), {}
    for q in range(len(P) + 1):
        for a in S:
            if q < len(P) and P[q] == a: d[q, a] = q + 1
            else: d[q, a] = d[pi[q - 1], a] if q else 0
    return d
def sigma(P, x):                         # longest prefix of P that is a suffix of x
    return max(k for k in range(len(P) + 1) if x.endswith(P[:k]))
P, S = "ABABAC", "ABC"
d = kmp_dfa(P, S)
print("pi =", prefix_function(P))
print("q | " + " ".join(S))
for q in range(len(P) + 1): print(q, "|", " ".join(str(d[q, a]) for a in S))
print("table == definition:", all(d[q, a] == sigma(P, P[:q] + a) for q, a in d))
T, q, states = "ABABABACABABAC", 0, []
for c in T: q = d[q, c]; states.append(q)
print("states:", states)
print("matches start at", [i - len(P) + 1 for i, s in enumerate(states) if s == len(P)])
ok = True                                # invariant: state after x == sigma(P, x)
for n in range(8):
    for x in map("".join, product(S, repeat=n)):
        q = 0
        for c in x: q = d[q, c]
        ok = ok and q == sigma(P, x)
print("invariant holds for all", sum(3 ** n for n in range(8)), "strings up to length 7:", ok)

আসল আউটপুট (ব্রাউজারের Python):

pi = [0, 0, 1, 2, 3, 0]
q | A B C
0 | 1 0 0
1 | 1 2 0
2 | 3 0 0
3 | 1 4 0
4 | 5 0 0
5 | 1 4 6
6 | 1 0 0
table == definition: True
states: [1, 2, 3, 4, 5, 4, 5, 6, 1, 2, 3, 4, 5, 6]
matches start at [2, 8]
invariant holds for all 3280 strings up to length 7: True

π আর টেবিল ঠিক stepper আর উপরের সারণির সঙ্গে মেলে, আর π-থেকে-বানানো টেবিল সংজ্ঞা থেকে বানানো টেবিলের হুবহু সমান (True). লেখা ABABABACABABAC-এ state 6 আসে দুবার, অবস্থান 7 আর 13-এ (০ থেকে গোনা), তাই মিল শুরু হয় 2 আর 8-এ। ষষ্ঠ অক্ষরে state 5 থেকে 4-এ নামা লক্ষ করুন: “ABABAB” পড়ার পর শেষের “ABAB” এখনো কাজে লাগে। শেষ লাইনটি প্রমাণের একটি সীমিত যাচাই: ১ + ৩ + ৯ + ⋯ + ৩৭ = ৩২৮০টি string-এর প্রতিটিতে state আর σ সমান। এটি প্রমাণের বিকল্প নয়, কিন্তু টেবিলে একটি ভুল সংখ্যা থাকলে সঙ্গে সঙ্গে ধরা পড়ত।

৪ · যন্ত্র চালানো আর O(n + m) — amortized হিসাব

এবার যন্ত্রটি একটি লেখায় চালানো যাক: T = ABABABAC. পূর্ণ DFA-তে প্রতি অক্ষরে ঠিক একটি টেবিল-দেখা। KMP-এর সংকুচিত রূপে কখনো কখনো এক বা একাধিক failure ধাপ লাগে। দুটি পাশাপাশি দেখুন।

0শুরু, কিছু পড়া হয়নি1A2B3A4B5A6B7A8C
এই ধাপের হিসাব
পড়া অংশ
DFA: δ(আগের, অক্ষর)
KMP-এর failure ধাপ
শেষে মিলেছে
  1. শুরু। কিছু পড়া হয়নি, state 0 = σ(ε). প্রতিটি ধাপে state সবসময় σ(পড়া অংশ), উপপাদ্য ২.৪ অনুযায়ী।
  2. A এল। p1 = A মিলল: state 1.
  3. B এল। p2 = B মিলল: state 2.
  4. A এল। state 3; এখন শেষের ABA মিলে আছে।
  5. B এল। state 4, শেষে ABAB.
  6. A এল। state 5, শেষে ABABA. পরের দরকারি অক্ষর C.
  7. B, অমিল। C-এর বদলে B এল। DFA সরাসরি δ(5, B) = 4 দেখে। KMP প্রথমে π[5] = 3-এ পিছিয়ে যায় (কিছু না পড়ে), তারপর p4 = B মেলে, তাই 4. দুই পথে একই উত্তর, কারণ উপপাদ্য ৩.১: δ(5, B) = δ(π[5], B). গোড়া থেকে শুরু করতে হয়নি: “ABABAB”-এর শেষের ABAB কাজে লাগল।
  8. A এল। আবার state 5.
  9. C এল। state 6 = m. অবস্থান 8-এ P শেষ হলো, তাই মিলটি t3⋯t8-এ (১ থেকে গোনা)। লেখার কোনো অক্ষর দুবার পড়া হয়নি।

পূর্ণ DFA-তে সময় স্পষ্টতই n ধাপ। KMP-তে একটি অক্ষরেই অনেক failure ধাপ হতে পারে (অনুশীলন ২-এ দেখবেন, m − 1টি পর্যন্ত), তবু মোট হিসাব রৈখিক। এটি একটি সুন্দর amortized যুক্তি।

উপপাদ্য ৪.১ (KMP-এর খরচ)

দৈর্ঘ্য n-এর লেখায় KMP-এর মোট failure ধাপ বড়জোর n, তাই মোট তুলনা বড়জোর 2n. একই যুক্তিতে π হিসাবে মোট তুলনা বড়জোর 2m. সব মিলিয়ে O(n + m) সময় আর O(m) জায়গা লাগে।

প্রমাণ (potential method-এর মতো, potential = বর্তমান state k):

  1. k সবসময় ≥ 0, আর শুরুতে k = 0. — state-এর সংজ্ঞা
  2. প্রতিটি লেখার অক্ষরে k বড়জোর 1 বাড়ে (মিললে k + 1, নইলে বাড়ে না)। তাই পুরো লেখায় মোট বৃদ্ধি ≤ n. — Lemma ২.২
  3. প্রতিটি failure ধাপ k-কে π[k]-তে নেয়, আর π[k] < k; তাই প্রতি failure ধাপে k অন্তত 1 কমে। — border proper
  4. k কখনো ঋণাত্মক নয়, তাই মোট কমা ≤ মোট বৃদ্ধি ≤ n. ফলে failure ধাপ ≤ n. — ধাপ ১–৩
  5. প্রতিটি অক্ষরে সফল বা শেষ তুলনা একটি, আর প্রতিটি failure ধাপের সঙ্গে একটি তুলনা; মোট ≤ n + n = 2n. ∎

নিচের JavaScript ব্লক তত্ত্বটি সংখ্যায় দেখায়। Naive পদ্ধতি আর KMP একই লেখায় একই ধাঁচ খোঁজে, আর প্রতিটি অক্ষর-তুলনা গোনে। ধাঁচ P = AAAAAAAAAB (m = 10), যা naive-এর জন্য সবচেয়ে খারাপ ধরনের।

// Count character comparisons: naive search vs KMP (same matches, different work).
function prefixFunction(P) {
  const pi = new Array(P.length).fill(0);
  for (let i = 1, k = 0; i < P.length; i++) {
    while (k > 0 && P[k] !== P[i]) k = pi[k - 1];
    if (P[k] === P[i]) k++;
    pi[i] = k;
  }
  return pi;
}
function naive(P, T) {                  // try every start, compare left to right
  let cmp = 0, hits = 0;
  for (let s = 0; s + P.length <= T.length; s++) {
    let j = 0;
    while (j < P.length) { cmp++; if (T[s + j] !== P[j]) break; j++; }
    if (j === P.length) hits++;
  } return [cmp, hits];
}
function kmp(P, T) {                    // never moves back in T
  const pi = prefixFunction(P); let k = 0, cmp = 0, hits = 0;
  for (const c of T) {
    while (true) {
      cmp++;
      if (P[k] === c) { k++; break; }
      if (k === 0) break;
      k = pi[k - 1];                    // failure transition: no input consumed
    }
    if (k === P.length) { hits++; k = pi[k - 1]; }
  } return [cmp, hits];
}
const P = "AAAAAAAAAB";                  // m = 10
for (const T of ["A".repeat(1000), "A".repeat(10000), "AAAAAAAAAB".repeat(1000)]) {
  const [c1, h1] = naive(P, T), [c2, h2] = kmp(P, T);
  console.log(`n=${T.length}: naive ${c1} cmp, KMP ${c2} cmp, matches ${h1}/${h2}`);
}

আসল আউটপুট (ব্রাউজারের JavaScript):

n=1000: naive 9910 cmp, KMP 1991 cmp, matches 0/0
n=10000: naive 99910 cmp, KMP 19991 cmp, matches 0/0
n=10000: naive 54955 cmp, KMP 10000 cmp, matches 1000/1000

শুধু A-এর লেখায় naive প্রতিটি শুরুতে ১০টি তুলনা করে: (n − 9) × 10, যেমন 991 × 10 = 9910. KMP-এর তুলনা 2n − 9 = 1991, উপপাদ্য ৪.১-এর 2n সীমার ঠিক নিচে: প্রতিটি A-তে state বাড়তে বাড়তে 9-এ আটকে যায়, তারপর প্রতি অক্ষরে একটি অমিল-তুলনা আর একটি failure ধাপ। n দশগুণ হলে দুটিই দশগুণ, কিন্তু অনুপাতটি থাকে m-এর মাপের। তৃতীয় লাইনে লেখাটি P-এর ১০০০টি পুনরাবৃত্তি: KMP ঠিক n = 10000 তুলনায় ১০০০টি মিলই পায়, প্রতিটি অক্ষরে একটি। দুই পদ্ধতির মিলের সংখ্যা সবসময় সমান, পার্থক্য শুধু কাজে।

৫ · কেন বিস্ফোরণ নেই — subset construction আর Myhill–Nerode

পর্ব ১০-এ দেখেছেন, NFA থেকে DFA বানালে state 2n পর্যন্ত বাড়তে পারে, আর “শেষ থেকে n-তম চিহ্ন 1” language-এ সত্যিই বাড়ে। “P দিয়ে শেষ”-এর NFA NP-ও ছোট: m + 1টি state, 0-তে সব চিহ্নে চক্র, আর i থেকে pi+1 পড়ে i + 1. তাহলে এর DFA-তে কতগুলো state আসে?

উপপাদ্য ৫.১ (Subset construction-এ m + 1টি subset)

NP-এর ওপর subset construction চালালে x পড়ার পর subset হয় B(x) = {k : Pk হলো x-এর suffix} = {σ(x), π[σ(x)], π[π[σ(x)]], …, 0}. B(x) পুরোপুরি σ(x) দিয়ে নির্ধারিত, তাই reachable subset ঠিক m + 1টি, আর ফলের DFA হুবহু MP.

প্রমাণের রূপরেখা: NP x পড়ার পর state k-তে থাকতে পারে ঠিক তখন, যখন x-এর শেষ k অক্ষর Pk (0-এর চক্রে বাকিটা খেয়ে, শেষ k অক্ষরে এগিয়ে); এটি |x|-এর ওপর সহজ induction. P-এর যে prefix-গুলো x-এর suffix, তারা সবাই সবচেয়ে লম্বাটির (Pσ(x)) suffix, অর্থাৎ তার border-এর শিকল। তাই subset-টি একটি সংখ্যা σ(x) থেকেই পুরো বের করা যায়। প্রতিটি q-এর জন্য x = Pq নিলে σ(x) = q, তাই m + 1টি মানই আসে। ∎

উদাহরণ P = ABABAC: subset-গুলো {0}, {0, 1}, {0, 2}, {0, 1, 3}, {0, 2, 4}, {0, 1, 3, 5} আর {0, 6}. যেমন {0, 1, 3, 5} মানে ABABA মিলেছে, আর তার border ABA, A, ε-ও। Scratch-এ {a, b}-এর ওপর দৈর্ঘ্য 8 পর্যন্ত প্রতিটি ধাঁচে (মোট ৫১০টি) subset-সংখ্যা ঠিক m + 1 পাওয়া গেছে।

আরও শক্ত দাবি: m + 1-এর চেয়ে কম state-এ Σ∗P চেনা অসম্ভব। এখানে পর্ব ১৮-এর Myhill–Nerode theorem কাজে লাগে: যেকোনো DFA-তে অন্তত ততগুলো state লাগে, যতগুলো string পরস্পর distinguishable.

উপপাদ্য ৫.২ (MP ক্ষুদ্রতম)

Σ∗P-এর যেকোনো DFA-তে অন্তত m + 1টি state.

  1. P0, P1, …, Pm এই m + 1টি string নিন। দেখাতে হবে, i < j হলে Pi আর Pj distinguishable. — fooling set-এর কৌশল
  2. z = pj+1⋯pm নিন (j = m হলে z = ε). তাহলে Pjz = P ∈ Σ∗P. — নির্মাণ
  3. Piz-এর দৈর্ঘ্য i + (m − j) < m, তাই এটি P দিয়ে শেষ হতে পারে না: Piz ∉ Σ∗P. — দৈর্ঘ্য গোনা
  4. z দুটিকে আলাদা করে, তাই কোনো DFA এদের একই state-এ রাখতে পারে না; m + 1টি আলাদা state লাগে। ∎ — Myhill–Nerode

অর্থাৎ KMP-এর automaton শুধু “ভালো” নয়, এটিই একমাত্র ক্ষুদ্রতম DFA (নাম বদলানো পর্যন্ত, পর্ব ১৯). তত্ত্বের দিক থেকে সুন্দর একটি মিলন: subset construction, Myhill–Nerode আর ১৯৭০-এর দশকের একটি দ্রুত algorithm, তিনটিই একই যন্ত্রে পৌঁছায়।

৬ · অনেক ধাঁচ একসাথে — Aho–Corasick automaton

বাজারঘরের review-বিভাগ এক তালিকা শব্দ দিয়ে সন্দেহজনক review আলাদা করতে চায়: “নকল”, “ভুয়া”, “প্রতারণা”, আরও কয়েকশো। প্রতিটি শব্দের জন্য আলাদা KMP চালালে k শব্দে k বার পুরো লেখা পড়তে হয়। ১৯৭৫ সালে Alfred Aho আর Margaret Corasick (Bell Labs) একটি গ্রন্থপঞ্জি-খোঁজার প্রোগ্রামের জন্য দেখান, কীভাবে সব ধাঁচ মিলিয়ে একটি যন্ত্রে লেখা একবারই পড়া যায়।

ধাঁচের সেট K = {he, she, his, hers} দিয়ে দেখা যাক (Aho–Corasick-এর মূল প্রবন্ধের পরিচিত উদাহরণ)। যন্ত্রের তিনটি অংশ:

  • Trie (goto): সব ধাঁচ একটি prefix tree-তে। প্রতিটি node একটি string, K-এর কোনো ধাঁচের prefix; root = ε. Node-সংখ্যা বড়জোর M + 1.
  • Failure link: node v-এর fail(v) হলো v-এর সবচেয়ে লম্বা proper suffix, যা trie-তেও একটি node. এটি KMP-এর π-এর সাধারণ রূপ: একটি ধাঁচের বদলে পুরো trie-র ওপর border.
  • Output: out(v) = K-এর যেসব ধাঁচ v-এর suffix. হিসাব সহজ: out(v) = (v নিজে ধাঁচ হলে {v}) ∪ out(fail(v)).

{he, she, his, hers}-এর trie আর failure link

কালো তীর trie-র পথ। কমলা ড্যাশ তীর failure link; আঁকা না থাকলে failure link root-এ যায়। সবুজ দুই দাগের node-এ কোনো ধাঁচ শেষ হয়।

Aho–Corasick trie for he, she, his, hers with failure links εhs hehish herhisshehers hsei hrses বাকি failure link root-এ (আঁকা হয়নি)
ছবি ২৩.২ — she-এর failure link he-তে, কারণ “he” হলো “she”-এর সবচেয়ে লম্বা proper suffix যা trie-তে আছে। তাই she-তে পৌঁছালে দুটি ধাঁচ একসঙ্গে মেলে: she আর he.

Failure link বানানো হয় BFS ক্রমে, অর্থাৎ ছোট গভীরতা আগে। গভীরতা 1-এর সব node-এর failure root. v থেকে c-তে u হলে: f = fail(v) থেকে শুরু করে যতক্ষণ f-এর c-সন্তান নেই আর f ≠ root, f = fail(f); তারপর fail(u) = f-এর c-সন্তান (থাকলে), নইলে root. এটি π হিসাবের হুবহু ধাঁচ। লেখা পড়ার নিয়মও KMP-এর মতো: বর্তমান node-এ পরের অক্ষরের সন্তান না থাকলে failure link ধরে পিছিয়ে যান, তারপর এগোন, আর পৌঁছানো node-এর out ছাপুন। লেখা “ushers” পড়ে দেখা যাক:

0শুরু: root1u2s3h4e5r6s
এই ধাপের হিসাব
পড়া অংশ
failure ধাপ
পৌঁছানো node
out (মিল)
  1. শুরু। যন্ত্র root-এ (ε). Invariant: প্রতিটি ধাপে node = পড়া লেখার সবচেয়ে লম্বা suffix যা trie-তে আছে। KMP-এ এটি ছিল σ(x).
  2. u এল। root-এর কোনো u-সন্তান নেই, আর root থেকে পিছানোর জায়গা নেই: root-এই থাকা। “u” কোনো ধাঁচের শুরু নয়।
  3. s এল। root থেকে s-এ। এখন শেষের “s” মিলেছে, যা she-এর শুরু হতে পারে।
  4. h এল। s থেকে sh. লক্ষ করুন, fail(sh) = h: “sh” না মিললেও শেষের “h” দিয়ে he বা his শুরু হতে পারে।
  5. e এল। sh থেকে she, যা একটি ধাঁচ। out(she) = {she} ∪ out(he) = {she, he}: অবস্থান 4-এ (১ থেকে গোনা) দুটি ধাঁচ শেষ হলো, অথচ যন্ত্র he-শাখায় কখনো যায়নি। এটিই output-এর শিকলের কাজ।
  6. r, অমিল। she-র কোনো r-সন্তান নেই। Failure link ধরে he-তে, কিছু না পড়ে। he-র r-সন্তান আছে: her. KMP-এর 5 → 3-এর মতো, শুধু এবার দুই শাখার মধ্যে লাফ।
  7. s এল। her থেকে hers, ধাঁচ: অবস্থান 6-এ hers শেষ। মোট মিল ৩টি: she (2–4), he (3–4), hers (3–6). লেখা একবারই পড়া হলো, চারটি ধাঁচের জন্য।
উপপাদ্য ৬.১ (Aho–Corasick, প্রমাণের রূপরেখা)

লেখা x পড়ার পর node = x-এর সবচেয়ে লম্বা suffix যা trie-তে আছে, আর out(node) ঠিক সেই ধাঁচগুলো, যারা এই অবস্থানে শেষ হয়। মোট সময় O(n + M + z), যেখানে z = ছাপা মিলের সংখ্যা (alphabet ছোট ধ্রুবক ধরে)।

রূপরেখা: invariant-এর প্রমাণ উপপাদ্য ২.৪-এর হুবহু: Lemma ২.২ আর ২.৩-এ “P-এর prefix”-এর জায়গায় “trie-র node” বসালেই চলে। x-এ শেষ হওয়া প্রতিটি ধাঁচ x-এর একটি suffix আর trie-র node, তাই সবচেয়ে লম্বা node-এর suffix-শিকলে (failure link-এর শিকল) পড়ে; out ঠিক এটিই জমা রাখে। সময়: গভীরতা প্রতি অক্ষরে বড়জোর 1 বাড়ে, প্রতিটি failure ধাপে অন্তত 1 কমে, তাই §৪-এর যুক্তিতে failure ধাপ ≤ n; failure link বানাতেও একই যুক্তি প্রতিটি ধাঁচের ওপর আলাদা খাটে, মোট O(M). ∎

Failure link দিয়ে trie-কে “পূর্ণ” করলে, অর্থাৎ δ(v, a) = goto(v, a) থাকলে সেটি, নইলে δ(fail(v), a), আর root-এ নইলে root, তখন এটি একটি সাধারণ DFA, Σ∗(P1 ∪ ⋯ ∪ Pk)-এর জন্য। আসলে প্রতিটি node-এর গায়ে একটি output-সেট লেখা বলে এটি একটি Moore machine (পর্ব ১২). তবে শুধু “কোনো ধাঁচ শেষ হলো কি না” প্রশ্নের জন্য এটি সবসময় ক্ষুদ্রতম নয়: K = {a, ba}-এর trie-তে ৪টি node, অথচ Σ∗{a, ba} = Σ∗a, যার ক্ষুদ্রতম DFA-তে ২টি state. DSA কোর্সের পর্ব ৫৯-এ Aho–Corasick-এর algorithm আর কোডের বিস্তারিত দিক আছে।

নিচের ব্লক trie, failure link আর out ছাপে, “ushers”-এ খোঁজে, তারপর বাজারঘরের তিনটি review-তে বাংলা শব্দ খোঁজে। প্রতিটি review-এর লাইনে প্রথম সংখ্যা সরাসরি খোঁজার মিল, দ্বিতীয়টি দুই দিক Unicode normalization (NFC) করার পরের মিল।

from collections import deque; import unicodedata
def build(pats):                         # trie + failure links + merged outputs
    goto, fail, out, name = [{}], [0], [[]], [""]
    for p in pats:
        v = 0
        for c in p:
            if c not in goto[v]:
                goto.append({}); fail.append(0); out.append([]); name.append(name[v] + c)
                goto[v][c] = len(goto) - 1
            v = goto[v][c]
        out[v].append(p)
    queue = deque(goto[0].values())      # BFS: depth-1 nodes fail to the root
    while queue:
        v = queue.popleft()
        for c, u in goto[v].items():
            f = fail[v]
            while f and c not in goto[f]: f = fail[f]
            fail[u] = goto[f][c] if c in goto[f] and goto[f][c] != u else 0
            out[u] = out[u] + out[fail[u]]; queue.append(u)
    return goto, fail, out, name
def scan(pats, text):
    goto, fail, out, _ = build(pats); v, found = 0, []
    for i, c in enumerate(text):
        while v and c not in goto[v]: v = fail[v]
        v = goto[v].get(c, 0)
        found += [(i - len(p) + 1, p) for p in out[v]]
    return found
words = ["he", "she", "his", "hers"]; goto, fail, out, name = build(words)
for v in range(1, len(goto)): print(f"{name[v]:5} fail -> {name[fail[v]] or 'root':5} out {out[v]}")
print("ushers:", scan(words, "ushers"))
nfc = lambda s: unicodedata.normalize("NFC", s)
bad = ["নকল", "ভু" + chr(0x9DF) + "া"]   # second keyword typed with the single code point
for r in ["পণ্যটি নকল মনে হচ্ছে", "একদম ভু" + chr(0x9AF) + chr(0x9BC) + "া জিনিস", "ভালো প্যাকেট"]:
    print(len(scan(bad, r)), len(scan([nfc(b) for b in bad], nfc(r))), r)

আসল আউটপুট (ব্রাউজারের Python):

h     fail -> root  out []
he    fail -> root  out ['he']
s     fail -> root  out []
sh    fail -> h     out []
she   fail -> he    out ['she', 'he']
hi    fail -> root  out []
his   fail -> s     out ['his']
her   fail -> root  out []
hers  fail -> s     out ['hers']
ushers: [(1, 'she'), (2, 'he'), (2, 'hers')]
1 1 পণ্যটি নকল মনে হচ্ছে
0 1 একদম ভুয়া জিনিস
0 0 ভালো প্যাকেট

Failure link ঠিক ছবি ২৩.২-এর: sh → h, she → he, his → s, hers → s, বাকি সব root. “ushers”-এ তিনটি মিল, শুরুর অবস্থান ০ থেকে গোনা: she 1-এ, he আর hers 2-এ, stepper-এর সঙ্গে হুবহু। বাংলা অংশটি একটি বাস্তব ফাঁদ দেখায়। “য়” Unicode-এ দুইভাবে লেখা যায়: একটি code point U+09DF, অথবা য (U+09AF) আর নুক্তা (U+09BC) পাশাপাশি। পর্দায় দুটি একই দেখায়, কিন্তু automaton অক্ষর নয়, code point পড়ে। তাই দ্বিতীয় review-তে সরাসরি খোঁজায় মিল 0. NFC-তে দুই রূপই একই দুই-code-point রূপে আসে (য়-এর ক্ষেত্রে Unicode-এর নিয়মে NFC জোড়া লাগায় না, ভেঙে রাখে), আর তখন মিল 1. শিক্ষা: ধাঁচ আর লেখা দুটিকেই একই normalization-এ এনে তবে automaton চালান।

৭ · সত্যিকারের run — pyahocorasick, নিজের Aho–Corasick আর naive

নিজের implementation একটি স্বাধীন library-র সঙ্গে মেলানো দরকার, আর গতির দাবিও মেপে দেখা দরকার। pyahocorasick Python-এর জন্য C-তে লেখা একটি Aho–Corasick library (licence: BSD-3-Clause, কিছু অংশ public domain). এটি একটি C extension; এর কোডে network বা usage-reporting-এর কোনো অংশ নেই। নিচের script ডেস্কটপে uv দিয়ে বানানো একটি আলাদা প্রকল্পে চালানো হয়েছে: pyahocorasick 2.3.1, Python 3.12. লেখা {a, b, c, d}-এর ওপর ২,০০,০০০ অক্ষরের একটি random string (seed স্থির), আর ধাঁচ দৈর্ঘ্য 5–8-এর random string; k = 10, 100, 1000 চেয়ে বানানো, পুনরাবৃত্তি বাদে। তিনটি পদ্ধতি: প্রতিটি ধাঁচের জন্য আলাদা str.find (C-তে লেখা দ্রুত একক-ধাঁচ খোঁজা), নিজের pure-Python Aho–Corasick, আর library.

import random, sys, time
from collections import deque
from importlib.metadata import version
import ahocorasick

def build(pats):                          # own Aho-Corasick: goto, fail, out
    goto, fail, out = [{}], [0], [[]]
    for p in pats:
        v = 0
        for c in p:
            if c not in goto[v]:
                goto.append({}); fail.append(0); out.append([]); goto[v][c] = len(goto) - 1
            v = goto[v][c]
        out[v].append(p)
    q = deque(goto[0].values())
    while q:
        v = q.popleft()
        for c, u in goto[v].items():
            f = fail[v]
            while f and c not in goto[f]: f = fail[f]
            fail[u] = goto[f].get(c, 0) if goto[f].get(c) != u else 0
            out[u] = out[u] + out[fail[u]]; q.append(u)
    return goto, fail, out

def own(pats, text):
    goto, fail, out = build(pats); v = n = 0
    for c in text:
        while v and c not in goto[v]: v = fail[v]
        v = goto[v].get(c, 0); n += len(out[v])
    return n, len(goto)

def lib(pats, text):
    A = ahocorasick.Automaton()
    for p in pats: A.add_word(p, p)
    A.make_automaton()
    return sum(1 for _ in A.iter(text)), A.get_stats()["nodes_count"]

def naive(pats, text):                    # one str.find pass per pattern
    n = 0
    for p in pats:
        i = text.find(p)
        while i != -1: n += 1; i = text.find(p, i + 1)
    return n, None

random.seed(2026)
text = "".join(random.choices("abcd", k=200_000))
print("python", sys.version.split()[0], "| pyahocorasick", version("pyahocorasick"))
print(f"{'k':>5} {'method':>14} {'matches':>8} {'seconds':>8}")
for k in (10, 100, 1000):
    pats = sorted({"".join(random.choices("abcd", k=random.randint(5, 8))) for _ in range(k)})
    res = []
    for name, f in (("naive str.find", naive), ("own AC", own), ("pyahocorasick", lib)):
        t = time.perf_counter(); n, st = f(pats, text); dt = time.perf_counter() - t
        res.append(n); print(f"{len(pats):>5} {name:>14} {n:>8} {dt:>8.3f}" + (f"  states {st}" if st else ""))
    assert len(set(res)) == 1
print("all three methods agree on every k")

সত্যিকারের run (ডেস্কটপ, pyahocorasick 2.3.1, Python 3.12):

~/bazarghar-toc$ uv init --vcs none --author-from none
~/bazarghar-toc$ uv add pyahocorasick
 + pyahocorasick==2.3.1
~/bazarghar-toc$ uv run python bench.py
python 3.12.13 | pyahocorasick 2.3.1
    k         method  matches  seconds
   10 naive str.find      945    0.003
   10         own AC      945    0.013  states 47
   10  pyahocorasick      945    0.002  states 47
   99 naive str.find     6383    0.029
   99         own AC     6383    0.017  states 388
   99  pyahocorasick     6383    0.003  states 388
  956 naive str.find    58763    0.280
  956         own AC    58763    0.020  states 2382
  956  pyahocorasick    58763    0.007  states 2382
all three methods agree on every k

প্রথমে সঠিকতা: প্রতিটি k-তে তিন পদ্ধতির মিলের সংখ্যা হুবহু এক (assert পাস করেছে), আর নিজের trie আর library-র trie-তে node-সংখ্যাও এক: 47, 388, 2382. Random ধাঁচে পুনরাবৃত্তি বাদ যাওয়ায় k হয়েছে 10, 99 আর 956. Node-সংখ্যা মোট দৈর্ঘ্য M (এখানে 62, 643 আর 6245)-এর চেয়ে অনেক কম, কারণ সাধারণ prefix ভাগ হয়।

এবার গতি, যেখানে শিক্ষাটি সূক্ষ্ম। ১০টি ধাঁচে আলাদা str.find (০.০০৩ সেকেন্ড) নিজের Python Aho–Corasick-এর (০.০১৩) চেয়ে দ্রুত: C-তে লেখা দশটি দ্রুত পাস, Python-এর একটি ধীর পাসকে হারায়। কিন্তু k বাড়লে naive-এর সময় প্রায় k-এর অনুপাতে বাড়ে (০.০০৩ → ০.০২৯ → ০.২৮০), আর Aho–Corasick প্রায় একই থাকে (০.০১৩ → ০.০২০), কারণ লেখা একবারই পড়া হয়; বাড়তি সময় মূলত বেশি মিল আর বড় trie বানানোর। ৯৫৬টি ধাঁচে নিজের pure-Python যন্ত্রও naive-এর প্রায় ১৪ গুণ দ্রুত, আর C library আরও প্রায় তিনগুণ। Asymptotic সীমা আর ধ্রুবক গুণক দুটিই বাস্তব; কোনটি জেতে, তা k আর implementation-এর ওপর নির্ভর করে। সময়গুলো একটি যন্ত্রে একবারের মাপ, তাই অনুপাতটিই মূল কথা, নিখুঁত সংখ্যা নয়।

৮ · বাস্তবে — fixed-string grep, signature আর বাংলা review filter

String matching automaton পরীক্ষার খাতার বাইরে অনেক জায়গায় কাজ করে:

Fixed-string খোঁজা

Unix-এর fgrep (আজকের grep -F) Aho–Corasick-এর ধারণায় লেখা হয়েছিল বলে সাধারণভাবে উল্লেখ করা হয়। অনেক ধাঁচের একটি তালিকা দিয়ে বড় log ফাইলে একবারে খোঁজা এর আদর্শ ব্যবহার।

Signature matching

Intrusion detection system আর antivirus হাজার হাজার পরিচিত ধাঁচ (signature) প্রতিটি packet বা ফাইলে খোঁজে; কিছু পরিচিত open-source IDS-এ এর জন্য Aho–Corasick-এর রূপভেদ ব্যবহৃত হয়। প্রতিরক্ষার দিকটি Cybersecurity কোর্সের পর্ব ২৩-এ।

বাজারঘরের review filter

শব্দ-তালিকা থেকে একটি automaton, প্রতিটি review একবার পড়া। আগে দুই দিকেই NFC, ইংরেজি অংশে ছোট-বড় হাতের অক্ষর এক করা (case folding), আর মিল পেলে শব্দের সীমা আলাদা করে যাচাই।

Streaming আর real-time

পূর্ণ DFA-টেবিলে প্রতি অক্ষরে ঠিক একটি টেবিল-দেখা, কখনো পিছিয়ে পড়া নয়। নেটওয়ার্কের স্রোতে বা sensor-এর ডেটায়, যেখানে লেখা জমিয়ে রাখা যায় না, এই নিশ্চয়তা জরুরি।

বাস্তবে দুটি নকশা-সিদ্ধান্ত বারবার আসে। প্রথম, পূর্ণ টেবিল না failure link? পূর্ণ টেবিলে state × |Σ| ঘর। Byte-ভিত্তিক (|Σ| = 256) যন্ত্রে এটি চলে, কিন্তু Unicode-এর পুরো code point পরিসরে (১১ লক্ষের বেশি) অসম্ভব; তখন প্রতিটি node-এ শুধু থাকা সন্তানগুলোর একটি ছোট map আর failure link রাখা হয়, ঠিক উপরের Python কোডের মতো। দ্বিতীয়, অক্ষর না byte? UTF-8-এ প্রতিটি বাংলা code point তিন byte. একটি সুবিধা হলো UTF-8 self-synchronizing: অক্ষরের শুরুর byte আর মাঝের byte-এর bit-ধাঁচ আলাদা, তাই একটি বৈধ UTF-8 ধাঁচের byte-মিল কখনো কোনো অক্ষরের মাঝখান থেকে শুরু হয় না। ফলে byte-এর ওপর বানানো automaton-ও বাংলা লেখায় ভুল মিল দেয় না, যদি normalization আগেই করা থাকে।

Automaton কী পারে না, সেটিও স্পষ্ট থাকা ভালো। এটি হুবহু মিল খোঁজে। “ভুয়া” আর “ভূয়া”-র মতো বানান-ভেদ, বা ইচ্ছাকৃত ফাঁক দেওয়া “ন ক ল” এটি ধরবে না; তার জন্য আলাদা নিয়ম বা approximate matching লাগে। আর প্রতিটি ধাঁচ একটি নির্দিষ্ট string; “BG- তারপর চারটি অঙ্ক”-এর মতো সাধারণ regex-এর জন্য পর্ব ২১-এর regex engine (backtracking বনাম automaton) প্রাসঙ্গিক, আর token-এ ভাগ করার কাজটি পর্ব ২২-এর lexer-এর।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • একটি ধাঁচের failure function বের করুন, যেমন ABABAC-এর। প্রতিটি prefix-এর সবচেয়ে লম্বা proper border: 0, 0, 1, 2, 3, 0.
  • ধাঁচ P-এর string matching DFA আঁকুন। State 0…m, δ(q, a) = σ(Pqa); π থেকে δ(q, a) = δ(π[q], a) দিয়ে দ্রুত ভরা যায়।
  • KMP কেন O(n + m)? State প্রতি অক্ষরে বড়জোর 1 বাড়ে, প্রতিটি failure ধাপে অন্তত 1 কমে; তাই failure ধাপ ≤ n.
  • Σ∗P-এর ক্ষুদ্রতম DFA-তে কয়টি state? m + 1; P0, …, Pm পরস্পর distinguishable.
  • Aho–Corasick-এর failure link কী, আর সময় কত? Node-এর সবচেয়ে লম্বা proper suffix যা trie-তে আছে; O(n + M + z).

আরও গভীরে: MP-এর বেশিরভাগ তীর state 0-তে যায়; Imre Simon-এর নামে পরিচিত একটি ফল অনুযায়ী 0-ছাড়া কোথাও যাওয়া পিছনের তীর বড়জোর m টি, তাই যন্ত্রটি O(m) জায়গায় রাখা যায় (scratch-এ {a, b, c}-এর ওপর দৈর্ঘ্য 8 পর্যন্ত সব ধাঁচে এই সীমা মিলেছে)। KMP-এর মূল প্রবন্ধে একটি উন্নত failure function দিয়ে এক অক্ষরে সর্বোচ্চ পিছানো O(log m)-এ নামানো হয়েছে বলে উল্লেখ আছে। অন্য দিকে Boyer–Moore (১৯৭৭) ধাঁচকে ডান দিক থেকে মিলিয়ে লেখার অনেক অক্ষর না দেখেই লাফ দিতে পারে, যা বাস্তবে প্রায়ই দ্রুত, কিন্তু সেটি আর “বাঁ থেকে ডানে একবার পড়া” automaton নয়।

৯ · AI-এর যুগে string matching automaton

AI assistant KMP-এর কোড প্রায় সবসময় লিখে দিতে পারে, কারণ এটি বহুল প্রচলিত। ভুল হয় সূক্ষ্ম জায়গায়, আর পরীক্ষার কয়েকটি উদাহরণে প্রায়ই ধরা পড়ে না:

AI-এর ভুলকীভাবে ধরবেন
π-কে ০ থেকে না ১ থেকে গোনা হচ্ছে, তা মিশিয়ে ফেলা (off-by-one)ছোট ধাঁচে (AABAA, ABABAC) হাতে π বের করে কোডের ফলের সঙ্গে মেলানো
Border-এর সংজ্ঞায় পুরো string-কেও ধরা, ফলে π[q] = q আর অসীম loopসংজ্ঞা দেখা: border proper, π[q] < q
মিলের পর state 0-তে ফেরা, ফলে overlapping মিল হারানোAAA-তে AA খোঁজা: সঠিক উত্তর ২টি মিল
Aho–Corasick-এ শুধু নিজের out ছাপা, failure-শিকলের out বাদ{he, she}-এ “she” খোঁজা: he-ও মিলতে হবে
Failure link BFS-এর বদলে DFS ক্রমে বানানোগভীর node-এর আগে অগভীর node-এর link তৈরি কি না দেখা; brute force-এর সঙ্গে random পরীক্ষা
“KMP সবসময় naive-এর চেয়ে দ্রুত” বা “Aho–Corasick O(n)” ধরনের দাবিz (মিলের সংখ্যা) আর ধ্রুবক গুণক মনে রাখা; §৭-এর মতো নিজে মেপে দেখা
ভুল সাল বা বানানো রেফারেন্সKnuth–Morris–Pratt (১৯৭৭) আর Aho–Corasick (১৯৭৫)-এর মূল প্রবন্ধ, বা Sipser / Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখা

AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু কোড না চেয়ে, টেবিল আর একটি স্বাধীন যাচাই চাওয়া, তারপর নিজে চালিয়ে দেখা।

আমি গণনার তত্ত্ব শিখছি। ধাঁচ P = AABAA, alphabet Σ = {A, B}. ১. P-এর failure function π (১ থেকে গুনে, proper border) বের করো, প্রতিটি ধাপের তুলনা দেখিয়ে। ২. String matching automaton-এর পুরো δ-টেবিল দাও (state 0 থেকে 5), আর অন্তত দুটি ঘর σ(P_q a)-এর সংজ্ঞা থেকে আলাদা করে যাচাই করো। ৩. লেখা AABAABAA-এ কোন কোন অবস্থানে মিল শেষ হয়? Overlapping মিলও গুনবে। ৪. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা টেবিলটি বানায় আর দৈর্ঘ্য ≤ 8-এর সব string-এ brute force দিয়ে মিলায়। ৫. কোনো দাবিতে নিশ্চিত না হলে স্পষ্ট করে বলো।

(নিজে যাচাই করুন: π = 0, 1, 0, 1, 2. টেবিলের সারি (A, B): 0 → (1, 0), 1 → (2, 0), 2 → (2, 3), 3 → (4, 0), 4 → (5, 0), 5 → (2, 3). যেমন δ(5, B) = σ(AABAAB) = 3, কারণ শেষের AAB = P3. AABAABAA-এ মিল শেষ হয় অবস্থান 5 আর 8-এ (১ থেকে গোনা); দ্বিতীয় মিলটি প্রথমটির শেষ দুই অক্ষর ভাগ করে। AI যদি একটিমাত্র মিল বলে, তাহলে সে মিলের পর state 0-তে ফিরিয়েছে।)

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১KMP algorithm তিনজনের নামে, অথচ তাঁরা আলাদা পথে একই জায়গায় পৌঁছেছিলেন। এই ইতিহাস automaton তত্ত্ব আর বাস্তব algorithm-এর সম্পর্ক নিয়ে কী বলে?

Donald Knuth, James Morris আর Vaughan Pratt-এর যৌথ প্রবন্ধ “Fast Pattern Matching in Strings” প্রকাশিত হয় ১৯৭৭ সালে, SIAM Journal on Computing-এ। প্রবন্ধের ঐতিহাসিক অংশের বর্ণনা অনুযায়ী, Morris ১৯৭০ সালের দিকে একটি text editor বানাতে গিয়ে বাস্তব প্রয়োজনে কাছাকাছি একটি পদ্ধতি পান। Knuth অন্য পথে আসেন: Stephen Cook-এর একটি তাত্ত্বিক ফল ছিল যে two-way deterministic pushdown automaton দিয়ে চেনা যায় এমন যেকোনো language রৈখিক সময়ে চেনা যায়। ধাঁচ খোঁজার সমস্যাটি এমন যন্ত্রে লেখা যায়, তাই রৈখিক algorithm থাকতেই হবে, এই যুক্তি থেকে Knuth পদ্ধতিটি বের করেন। Pratt এর বিশ্লেষণ ও উন্নতিতে কাজ করেন। পরে তাঁরা জানতে পারেন যে Morris-এর কাজ আগে থেকেই ছিল, আর একসঙ্গে প্রকাশ করেন।

এই গল্পের শিক্ষা হলো, একটি “শুধু তাত্ত্বিক” উপপাদ্য, যা কোনো নির্দিষ্ট algorithm দেয় না, শুধু বলে যে একটি দ্রুত algorithm থাকতেই হবে, সেটি একজন গবেষককে খুঁজতে বাধ্য করেছিল। এই পর্বে আপনি একই জিনিস উল্টো দিক থেকে দেখেছেন: Myhill–Nerode বলে m + 1 state-এর কম অসম্ভব, subset construction বলে m + 1 state-ই আসে, আর KMP সেই যন্ত্রটিকেই O(m) জায়গায় সংকুচিত করে। তত্ত্ব কখনো সীমা দেখায়, কখনো সম্ভাবনার নিশ্চয়তা দেয়, আর দুটিই বাস্তব কাজকে পথ দেখায়। উল্টো দিকে, Morris-এর পথ মনে করিয়ে দেয় যে বাস্তব সমস্যা থেকেও ভালো ধারণা আসে, তত্ত্ব পরে তার ব্যাখ্যা দেয়। দুটি পথের দেখা হলো একটি automaton-এ।

মূল উপলব্ধি: “এমন algorithm থাকতেই হবে” ধরনের তাত্ত্বিক নিশ্চয়তা নিজেই একটি শক্তিশালী হাতিয়ার; KMP তার একটি ঐতিহাসিক উদাহরণ।

প্র ০২“শেষ থেকে n-তম চিহ্ন 1” language-এর NFA ছোট, কিন্তু DFA-তে 2n state লাগে। “P দিয়ে শেষ”-এর NFA-ও ছোট, অথচ DFA-তে মাত্র m + 1. পার্থক্যটা কোথায়?

দুটি ক্ষেত্রেই NFA অনুমান করে: “এখান থেকে শেষের অংশ শুরু”। পার্থক্য হলো subset construction-এ কোন subset-গুলো আসলে আসে। “শেষ থেকে n-তম চিহ্ন 1”-এ subset মানে “শেষের n চিহ্নের কোনগুলো 1”, আর শেষের n চিহ্ন যেকোনো 2n রকম হতে পারে; প্রতিটি আলাদা ভবিষ্যৎ বোঝায়, তাই Myhill–Nerode-এ 2nটি class. পর্ব ১০-এ এই নিম্নসীমা প্রমাণিত।

একটি নির্দিষ্ট ধাঁচ P-এর ক্ষেত্রে subset মানে “P-এর কোন কোন prefix এখন শেষে মিলছে”। কিন্তু এই prefix-গুলো স্বাধীন নয়: যদি P5 শেষে মেলে, তাহলে P-এর যে ছোট prefix-গুলো শেষে মেলে, তারা সবাই P5-এরই border, অর্থাৎ P5 দিয়েই নির্ধারিত। সবচেয়ে লম্বা মিল একাই পুরো subset বলে দেয়, তাই subset-এর সংখ্যা সম্ভাব্য “সবচেয়ে লম্বা মিল”-এর সংখ্যা, m + 1. গঠনটি রৈখিক, একটি শিকল; 2n-এর মতো স্বাধীন বিট নয়।

অনেক ধাঁচের ক্ষেত্রেও একই কারণে Aho–Corasick-এর state বড়জোর M + 1: subset নির্ধারিত হয় trie-র সবচেয়ে লম্বা মিলে-থাকা node দিয়ে। কিন্তু ধাঁচে wildcard ঢুকলে (যেমন “a, তারপর যেকোনো n − 1টি চিহ্ন”), মিলগুলো আর একে অন্যের border নয়, আর বিস্ফোরণ ফিরে আসতে পারে; শেষ থেকে n-তম চিহ্নের language আসলে ঠিক এমন একটি ধাঁচ। তাই বাস্তব regex engine-এ (পর্ব ২১) পুরো DFA আগে না বানিয়ে প্রয়োজনমতো state বানানো হয়, যাকে lazy DFA বলে।

মূল উপলব্ধি: subset construction-এর খরচ নির্ভর করে কতগুলো subset সত্যিই reachable; নির্দিষ্ট string-এর মিল একটি শিকল তৈরি করে, তাই বিস্ফোরণ হয় না।

প্র ০৩পূর্ণ DFA-টেবিল প্রতি অক্ষরে ঠিক একটি ধাপ দেয়, আর failure link কম জায়গা নেয়। বাস্তবের একটি সিস্টেমে কোনটি বেছে নেবেন, আর কেন?

দুটির খরচ আলাদা মাত্রায়। পূর্ণ টেবিলে (state-সংখ্যা) × |Σ| ঘর। ১০ হাজার ধাঁচের trie-তে লাখখানেক node হতে পারে; byte-ভিত্তিক যন্ত্রে প্রতি node-এ ২৫৬টি ঘর মানে কয়েক কোটি ঘর, যা অনেক memory আর CPU cache-এ আঁটে না। Failure link-এর রূপে প্রতি node-এ শুধু থাকা সন্তানগুলো আর একটি link, মোট O(M), কিন্তু এক অক্ষরে কয়েকটি ধাপ লাগতে পারে। গড়ে মোট ধাপ ≤ 2n থাকে, তবে একটি নির্দিষ্ট অক্ষরের দেরি (delay) বড় হতে পারে।

কোথায় কোনটি দরকার, তা প্রশ্নের ওপর নির্ভর করে। নেটওয়ার্কের packet পরীক্ষা করা একটি IDS-এ প্রতিটি byte-এর জন্য একটি নিশ্চিত সর্বোচ্চ খরচ থাকা জরুরি, কারণ আক্রমণকারী ইচ্ছা করে এমন input পাঠাতে পারে যা সবচেয়ে বেশি পিছানো ঘটায়; এমন সিস্টেমে টেবিল বা টেবিলের সংকুচিত রূপ (যেমন একই রকম সারি ভাগ করে রাখা, বা alphabet-কে অল্প কয়েকটি শ্রেণিতে ভাগ করা) প্রচলিত। লগ ফাইলে offline খোঁজায় মোট সময়ই আসল, তাই failure link যথেষ্ট। বাংলা বা অন্য Unicode লেখায় code point-এর পরিসর এত বড় যে পূর্ণ টেবিল অসম্ভব; তখন হয় map-ভিত্তিক সন্তান, নয়তো UTF-8 byte-এর ওপর যন্ত্র।

আরেকটি বিষয় বানানোর খরচ। পূর্ণ টেবিল বানাতে O(M·|Σ|), failure link বানাতে O(M). ধাঁচের তালিকা ঘন ঘন বদলালে (যেমন প্রতিদিন নতুন signature) বানানোর সময়ও গুরুত্বপূর্ণ। §৭-এর মাপে দেখেছেন, ১০টি ধাঁচে সরল পদ্ধতিও যথেষ্ট ভালো; প্রকৌশলে সবসময় মাপের প্রশ্ন আগে।

মূল উপলব্ধি: একই automaton-এর দুটি রূপ সময়, জায়গা আর সবচেয়ে খারাপ দেরির মধ্যে আপসের দুটি বিন্দু; সিস্টেমের প্রয়োজনই ঠিক করে কোনটি।

প্র ০৪Automaton লেখার প্রতিটি অক্ষর পড়ে, অথচ Boyer–Moore অনেক অক্ষর না দেখেই এগোয়। তাহলে কি automaton-ভিত্তিক পদ্ধতি “ধীর”? এর তাত্ত্বিক সীমা কী?

Robert Boyer আর J Strother Moore-এর algorithm (১৯৭৭) ধাঁচকে লেখার ওপর বসিয়ে ডান দিক থেকে মেলায়। অমিলের অক্ষরটি যদি ধাঁচে একেবারেই না থাকে, তাহলে পুরো ধাঁচের দৈর্ঘ্যের সমান লাফ দেওয়া যায়। লম্বা ধাঁচ আর বড় alphabet-এ, যেমন সাধারণ ইংরেজি বা বাংলা লেখায়, এটি গড়ে লেখার অক্ষরের একটি ছোট অংশই দেখে। তাই অনেক text editor আর একক-ধাঁচ খোঁজার library এই পরিবারের কোনো রূপভেদ ব্যবহার করে।

তবে দুই পদ্ধতির নিশ্চয়তা আলাদা। সবচেয়ে খারাপ ক্ষেত্রে কোনো algorithm-ই লেখার প্রায় সব অক্ষর না দেখে পারে না: ১৯৭০-এর দশকের শেষে Ronald Rivest-এর একটি ফল এমন একটি নিম্নসীমা দেয় বলে উল্লেখ করা হয়, মোটামুটি n − m + 1টি অক্ষর। অর্থাৎ worst case-এ “প্রতিটি অক্ষর একবার” প্রায় সেরা, আর automaton সেটিই দেয়। গড় ক্ষেত্রে লাফ দেওয়া পদ্ধতিগুলো এগিয়ে।

আরেকটি পার্থক্য কাঠামোগত। Boyer–Moore-কে লেখার একটি জানালা স্মৃতিতে রেখে সামনে-পিছনে দেখতে হয়। Automaton কঠোরভাবে বাঁ থেকে ডানে একবার পড়ে, কোনো কিছু ফেরত চায় না; একে online বা streaming পদ্ধতি বলে। নেটওয়ার্কের স্রোত, ডিস্ক থেকে টানা ডেটা বা একটি pipe-এর মাঝখানে এটি স্বাভাবিকভাবে বসে। এ ছাড়া Aho–Corasick হাজার ধাঁচে একবারে কাজ করে; অনেক ধাঁচের জন্য Boyer–Moore-এর সাধারণ রূপ (যেমন Commentz-Walter-এর ১৯৭৯ সালের পদ্ধতি) আছে, কিন্তু সেগুলো জটিলতর।

মূল উপলব্ধি: “দ্রুত” শব্দটির অর্থ ঠিক করা দরকার: worst case, গড়, না streaming-এর নিশ্চয়তা; automaton প্রথম আর তৃতীয়টিতে প্রায় সেরা, দ্বিতীয়টিতে লাফ দেওয়া পদ্ধতি এগিয়ে।

প্র ০৫বাংলা লেখায় শব্দ খোঁজার জন্য automaton বানাতে গেলে কোন কোন ফাঁদ আছে, যা ইংরেজির ছোট উদাহরণে চোখে পড়ে না?

প্রথম ফাঁদ হলো “অক্ষর” কাকে বলে। Automaton-এর alphabet Σ-এর একটি চিহ্ন সাধারণত একটি Unicode code point. কিন্তু পাঠকের চোখে একটি অক্ষর, যেমন “ক্ষ” বা “স্ত্র”, কয়েকটি code point জুড়ে হয়: ব্যঞ্জন, হসন্ত, আবার ব্যঞ্জন। তাই “ক্ষ” খুঁজলে automaton সেটি “ক্ষেত”-এর ভেতরেও পায়, আর ধাঁচের দৈর্ঘ্য m-ও অক্ষর নয়, code point-এ গোনা। দ্বিতীয় ফাঁদ normalization, যা এই পর্বের Python ব্লকে দেখেছেন: য়, ড়, ঢ় এক code point-এও লেখা যায়, দুই code point-এও। NFC সব লেখাকে একটি রূপে আনে, আর এই তিনটি অক্ষরের ক্ষেত্রে Unicode-এর নিয়মে NFC ভেঙে দুই code point-এ রাখে।

তৃতীয়ত অদৃশ্য চিহ্ন: zero-width joiner আর non-joiner (U+200D, U+200C) যুক্তাক্ষরের চেহারা বদলায়, কিন্তু লেখায় থেকে যায়, আর হুবহু মিলকে ভেঙে দিতে পারে। এগুলো আগে সরানো বা নিয়মমতো রাখা দরকার। চতুর্থত শব্দের সীমা: automaton substring খোঁজে, তাই “নকল” পাওয়া যাবে “নকলের”-এর ভেতরেও; এটি কখনো কাম্য, কখনো নয়। মিলের পরে আগে-পরের চিহ্ন দেখে সীমা যাচাই করা যায়।

ভালো খবর হলো, এগুলো automaton-এর তত্ত্ব বদলায় না, শুধু Σ আর ধাঁচকে কীভাবে সংজ্ঞায়িত করবেন সেটি বদলায়। UTF-8-এর self-synchronizing গঠনের জন্য byte-এর ওপর বানানো যন্ত্রও মাঝপথে ভুল মিল দেয় না। আর বানান-ভেদ (ভুয়া, ভূয়া) ধরতে চাইলে হুবহু মিলের সীমা ছাড়িয়ে যেতে হয়: হয় সব রূপ তালিকায় যোগ করা, নয়তো edit distance-ভিত্তিক approximate matching, যার জন্যও automaton-ভিত্তিক পদ্ধতি আছে।

মূল উপলব্ধি: automaton সঠিক উত্তর দেয় সেই alphabet-এর ওপর, যা আপনি তাকে দেন; বাংলা লেখায় আসল কাজ হলো ধাঁচ আর লেখাকে আগে একই, পরিষ্কার রূপে আনা।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। উপরের Python ব্লকে P বা ধাঁচের তালিকা বদলে নিজের উত্তরও যাচাই করতে পারেন।

  1. নকশা: Σ = {a, b}, ধাঁচ P = aab. (ক) π বের করুন। (খ) String matching automaton-এর পুরো δ-টেবিল দিন। (গ) পর্ব ০৮-এ একটি ভুল নকশা ছিল: state 2-এ a এলে state 1-এ ফেরা। আপনার টেবিল “aaab”-এ কী করে, দেখান।

    (ক) π = 0, 1, 0: “aa”-এর border “a”, “aab”-এর কোনো অ-ফাঁকা border নেই।

    (খ) সারি (a, b): 0 → (1, 0); 1 → (2, 0); 2 → (2, 3); ∗3 → (1, 0). যেমন δ(2, a) = σ(aaa) = 2, কারণ শেষের “aa” = P2; δ(3, a) = σ(aaba) = 1; δ(3, b) = σ(aabb) = 0.

    (গ) “aaab”-এ state-ক্রম 1, 2, 2, 3: শেষে মিল। ভুল নকশায় তৃতীয় a-তে state 1, তারপর b-তে 0, তাই মিলটি হারাত। Scratch-এ টেবিলটি σ-এর সংজ্ঞা থেকে আলাদাভাবে বানিয়ে মিলানো হয়েছে।

  2. প্রমাণের ভুল ধরুন: দাবি: “KMP-এ একটি অক্ষরে m − 1টি পর্যন্ত failure ধাপ হতে পারে। লেখায় n টি অক্ষর, তাই সবচেয়ে খারাপ ক্ষেত্রে KMP-এর সময় Θ(nm), naive-এর সমান।” প্রথম বাক্যটি কি সত্য? যুক্তির ভুলটি কোথায়?

    প্রথম বাক্য সত্য। P = AAAAB, লেখা AAAAC: চারটি A-তে state 4, তারপর C-তে 4 → 3 → 2 → 1 → 0, চারটি failure ধাপ, m − 1 = 4.

    ভুল হলো “প্রতিটি অক্ষরে সবচেয়ে খারাপটি একসঙ্গে ঘটতে পারে” ধরে নেওয়া। চারটি failure ধাপের আগে state-কে 4-এ তুলতে চারটি অক্ষর লেগেছিল। উপপাদ্য ৪.১-এর potential যুক্তি: state প্রতি অক্ষরে বড়জোর 1 বাড়ে, প্রতিটি failure ধাপে অন্তত 1 কমে, আর কখনো 0-এর নিচে যায় না; তাই মোট failure ধাপ ≤ মোট বৃদ্ধি ≤ n. একটি অক্ষরের সর্বোচ্চ খরচ গুণ n দিয়ে মোট খরচের সীমা পাওয়া যায় ঠিকই, কিন্তু সেটি সর্বোচ্চ সীমা, আঁটসাঁট নয়। সঠিক উত্তর O(n + m). ∎

  3. Trace আর অনুমান: ধাঁচ K = {an, ana, nan}, লেখা “banana”. (ক) Trie-র প্রতিটি node-এর failure link আর out বের করুন। (খ) লেখা পড়ার সময় প্রতিটি অক্ষরের পরে node আর ছাপা মিল অনুমান করুন।

    (ক) Node: a, an, ana, n, na, nan. fail: a → root, n → root, an → n, na → a, ana → na, nan → an. out: an → {an}; ana → {ana}; nan → {nan} ∪ out(an) = {nan, an}; বাকিগুলো ফাঁকা।

    1. b → root, মিল নেই; a → a. — root-এ b-সন্তান নেই
    2. n → an: মিল an (২–৩, ১ থেকে গোনা)।
    3. a → ana: মিল ana (২–৪)।
    4. n: ana-র n-সন্তান নেই, fail → na, তারপর nan: মিল nan (৩–৫) আর an (৪–৫)। — output-শিকল
    5. a: nan-এর a-সন্তান নেই, fail → an, তারপর ana: মিল ana (৪–৬)। ∎

    মোট ৫টি মিল। Scratch-এর কোডে হুবহু এই node-ক্রম আর মিল এসেছে, আর random লেখায় brute force-এর সঙ্গেও মিলেছে।

  4. গণনা: ধাঁচ P = ABA, Σ = {A, B}. “ABA দিয়ে শেষ”-এর NFA NP (state 0–3, 0-তে সব চিহ্নে চক্র, i থেকে pi+1 পড়ে i + 1)-এর ওপর subset construction চালান। কয়টি subset আসে? প্রতিটিকে MP-এর একটি state-এর সঙ্গে মেলান।

    শুরু {0}. {0}: A → {0, 1}, B → {0}. {0, 1}: A → {0, 1}, B → {0, 2}. {0, 2}: A → {0, 1, 3}, B → {0}. {0, 1, 3}: A → {0, 1}, B → {0, 2}. নতুন আর কিছু আসে না: মোট ৪টি subset, m + 1 = 4.

    মিল: {0} = 0, {0, 1} = 1, {0, 2} = 2, {0, 1, 3} = 3 (accepting, কারণ 3 আছে)। প্রতিটি subset-এর সবচেয়ে বড় সংখ্যাই σ, আর বাকিগুলো তার border-শিকল: {0, 1, 3}-এ 3, π[3] = 1, π[1] = 0. যেমন {0, 1, 3} থেকে B পড়ে {0, 2}, আর MP-এ δ(3, B) = σ(ABAB) = 2. Scratch-এ দুটি নির্মাণ একই টেবিল দিয়েছে।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমঅনেক ধাঁচের Aho–Corasick automaton বানিয়ে একটি লেখায় সব মিল খোঁজার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. সব ধাঁচ একটি trie-তে ঢোকানো, আর যেখানে ধাঁচ শেষ সেখানে out-এ লেখা
  2. Root-এর সব সন্তানের failure link root-এ বসানো
  3. BFS ক্রমে বাকি node-গুলোর failure link বের করা, বাবার failure link থেকে শুরু করে
  4. প্রতিটি node-এর out-এর সঙ্গে তার failure link-এর out জুড়ে দেওয়া
  5. লেখা বাঁ থেকে ডানে একবার পড়া, অমিলে failure link ধরে পিছিয়ে, আর প্রতিটি node-এর out ছাপা

দৈর্ঘ্য m-এর একটি ধাঁচ P-এর জন্য Σ∗P language-এর ক্ষুদ্রতম DFA-তে কয়টি state?

  • m
  • m + 1
  • 2m
  • m·|Σ|

ধাঁচ AABAAA-এর failure function π (প্রতিটি prefix-এর সবচেয়ে লম্বা proper border-এর দৈর্ঘ্য, ১ থেকে ৬) কোনটি?

  • 0, 0, 0, 1, 2, 3
  • 0, 1, 0, 1, 2, 3
  • 0, 1, 0, 1, 2, 2
  • 0, 1, 2, 1, 2, 2

ধাঁচ ABABAC (Σ = {A, B, C})-এর string matching automaton state 5-এ (ABABA মিলেছে) আছে, আর পরের অক্ষর B. নতুন state কত?

  • 0
  • 2
  • 4
  • 6

দৈর্ঘ্য n-এর লেখায় KMP-এর মোট failure ধাপ (π ধরে পিছানো) বড়জোর n কেন?

  • State প্রতি অক্ষরে বড়জোর 1 বাড়ে আর প্রতিটি failure ধাপে কমে, তাই মোট কমা ≤ মোট বাড়া ≤ n
  • প্রতিটি অক্ষরে বড়জোর একটি failure ধাপ হয়
  • ধাঁচের সব অক্ষর আলাদা ধরে নেওয়া হয়
  • π-টেবিল দেখতে ধ্রুবক সময় লাগে

ধাঁচ {he, she, his, hers}-এর Aho–Corasick trie-তে node “she”-এর failure link কোন node-এ যায়?

  • root
  • he
  • h
  • sh

Σ = {a, b}-এর ওপর ধাঁচের সেট K = {a, ba}. এর Aho–Corasick trie-তে ৪টি node (ε, a, b, ba). শুধু “লেখাটি K-এর কোনো ধাঁচ দিয়ে শেষ হয় কি না” চেনার ক্ষুদ্রতম DFA-তে কয়টি state?

  • ৫
  • ৪
  • ৩
  • ২

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. ধাঁচ P খোঁজা = Σ∗P চেনা। String matching automaton: state 0…m, δ(q, a) = σ(Pqa), আর δ̂(0, x) = σ(x), induction দিয়ে প্রমাণিত।
  2. Failure function π[q] = Pq-এর সবচেয়ে লম্বা proper border. অমিলে δ(q, a) = δ(π[q], a); KMP এই সংকুচিত রূপে O(m) জায়গায় চলে।
  3. O(n + m): state প্রতি অক্ষরে বড়জোর 1 বাড়ে, প্রতিটি failure ধাপে কমে; তাই মোট failure ধাপ ≤ n, যদিও এক অক্ষরে m − 1টি পর্যন্ত হতে পারে।
  4. “P দিয়ে শেষ”-এর NFA-র subset construction ঠিক m + 1টি subset দেয়, আর Myhill–Nerode দেখায় m + 1-ই ক্ষুদ্রতম।
  5. Aho–Corasick: trie + failure link + output; লেখা একবার পড়ে সব ধাঁচ, O(n + M + z). বাস্তবে আগে normalization (বাংলায় NFC), তারপর automaton.

পরের পর্বে: পর্ব ২৪ “Software-এ state machine — protocol, UI আর workflow”: বাজারঘরের অর্ডার placed থেকে delivered পর্যন্ত একটি state machine, নিষিদ্ধ transition আটকানো, আর BFS দিয়ে deadlock আর পৌঁছানো যায় না এমন state খোঁজা।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান