স্ট্রিং অ্যালগরিদম৯ মিনিট পড়া

আহো-কোরাসিক (Aho-Corasick)

একসাথে সব প্যাটার্ন খুঁজুন — এক পাস, O(n + matches)
build trie:O(Σ|Pi|)search text:O(n + মোট ম্যাচ)space:O(σ · Σ|Pi|)

কল্পনা করুন আপনি ১০ মেগাবাইটের একটি নথিতে ১,০০০টি নিষিদ্ধ শব্দ খুঁজতে চান। সাধারণ পদ্ধতি — প্রতিটি শব্দের জন্য একবার করে অনুসন্ধান চালানো — নথিটিকে ১,০০০ বার পড়বে। ১০ এমবির ফাইলের জন্য সেটি হবে ১০ জিবি পড়া।

আহো-কোরাসিক এটি এক পাসে করে। আপনার সমস্ত শব্দ থেকে একটি স্মার্ট লুকআপ কাঠামো তৈরি করুন, তারপর নথিটি ঠিক একবার পড়ুন। প্রতিটি অক্ষরে, কাঠামোটি তাৎক্ষণিকভাবে আপনাকে বলে দেয় কোন শব্দগুলো (যদি থাকে) এখানে শেষ হয়েছে। টেক্সটের দৈর্ঘ্য এবং মোট ম্যাচের সমানুপাতিক সময়ে কাজ শেষ।

ধাপ ১: ট্রাই (Trie) তৈরি করুন

একটি ট্রাই হলো এমন একটি ট্রি যেখানে রুট থেকে নোড পর্যন্ত প্রতিটি পথ একটি প্রিফিক্স তৈরি করে। আপনার সমস্ত প্যাটার্ন ট্রাই-তে যোগ করুন। একটি সম্পূর্ণ শব্দের শেষের নোডগুলোকে আউটপুট নোড হিসেবে চিহ্নিত করা হয়। M মোট দৈর্ঘ্যের k টি প্যাটার্ন সন্নিবেশ করার পর, ট্রাই-তে সর্বাধিক M নোড থাকবে।

এপর্যন্ত, ট্রাই আপনাকে একে একে প্যাটার্ন মেলাতে সাহায্য করে। মূল চমকটি এরপরে আসছে।

ধাপ ২: ফেইলিওর লিংক (Failure Links) যোগ করুন (ট্রাই-তে KMP কৌশল)

যখন আপনি ট্রাই বরাবর এগোচ্ছেন এবং পরবর্তী অক্ষরের জন্য কোনো এজ (edge) নেই, তখন আপনাকে একটি ছোট ম্যাচে ফিরে যেতে হবে — ঠিক KMP এর ফেইলিওর ফাংশনের মতো। একটি নোড v এর ফেইলিওর লিংক সেই ট্রাই নোডের দিকে নির্দেশ করে যা v এর স্ট্রিংয়ের সর্ববৃহৎ সঠিক সাফিক্স (suffix) উপস্থাপন করে, যা আবার অন্য কোনো প্যাটার্নের প্রিফিক্স।

BFS এর মাধ্যমে (লেভেল অনুযায়ী) ফেইলিওর লিংক গণনা করুন: রুট নিজের কাছে ফিরে যায়। a অক্ষরের উপর v নোডের চাইল্ড c এর জন্য — যদি v এর ফেইলিওর নোডেও a এর উপর কোনো এজ থাকে, তবে c এর ফেইলিওর লিংক সেখানে যায়; অন্যথায় v এর ফেইলিওর লিংকের ফেইলিওর লিংক অনুসরণ করুন, এবং এভাবেই চলতে থাকে। এটি মূলত পুরো ট্রাই-এর উপর KMP ধারণার প্রয়োগ।

ধাপ ৩: আউটপুট লিংক (Output Links) যোগ করুন (সাফিক্স-প্যাটার্ন ম্যাচ ধরা)

কখন কখনও একটি ছোট প্যাটার্ন একটি বড় প্যাটার্নের সাফিক্স হতে পারে। যখন আপনি একটি লম্বা শব্দের শেষ উপস্থাপনকারী নোডে পৌঁছান, তখন একটি ছোট শব্দও একই অবস্থানে শেষ হতে পারে। আউটপুট লিংক এই ধরনের সমস্ত শেষ খুঁজে পেতে সাফিক্স-লিংকের চেইন অনুসরণ করে। প্রতিটি নোড তার নিকটতম পূর্বপুরুষের (সাফিক্স লিংকের মাধ্যমে) শর্টকাট সংরক্ষণ করে যা নিজে একটি আউটপুট নোড।

ধাপ ৪: এক পাসে অনুসন্ধান

টেক্সটের ভেতর দিয়ে অক্ষর অনুযায়ী চলুন, অটোমেটনে একটি বর্তমান নোড বজায় রাখুন। প্রতিটি অক্ষরে: যদি ট্রাই এজ থাকে তবে সেটি অনুসরণ করুন, অন্যথায় সম্ভব হওয়া পর্যন্ত ফেইলিওর লিংক অনুসরণ করুন। তারপর বর্তমান নোডে শেষ হওয়া প্রতিটি প্যাটার্ন (আউটপুট লিংকের মাধ্যমে) আউটপুট করুন। প্রতিটি অক্ষর O(1) অ্যামর্টাইজড (amortized) ট্রানজিশন ঘটায় — KMP এর মতো একই যুক্তি। মোট অনুসন্ধানের সময়: O(n + মোট ম্যাচ)।

দ্রষ্টব্য: আহো-কোরাসিক বাস্তব বিশ্বের সিকিউরিটি টুলস চালায়। স্নোর্ট (Snort) এবং সুরিকাটা (Suricata) এটি ব্যবহার করে জীবন্ত নেটওয়ার্ক ট্র্যাফিকের বিরুদ্ধে হাজার হাজার আক্রমণ স্বাক্ষর মেলাতে — সেকেন্ডে লক্ষ লক্ষ প্যাকেট — একটি মাত্র পাসে।

আহো-কোরাসিক মাল্টি-প্যাটার্ন অনুসন্ধান

from collections import deque


class AhoCorasick:
    def __init__(self):
        self.goto = [{}]  # trie nodes
        self.fail = [0]
        self.output = [[]]


    def add_pattern(self, pattern, idx):
        node = 0
        for ch in pattern:
            if ch not in self.goto[node]:
                self.goto.append({})
                self.fail.append(0)
                self.output.append([])
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.output[node].append(idx)


    def build(self):
        q = deque()
        for ch, child in self.goto[0].items():
            self.fail[child] = 0
            q.append(child)
        while q:
            node = q.popleft()
            for ch, child in self.goto[node].items():
                f = self.fail[node]
                while f and ch not in self.goto[f]:
                    f = self.fail[f]
                self.fail[child] = self.goto[f].get(ch, 0)
                if self.fail[child] == child:
                    self.fail[child] = 0
                self.output[child] += self.output[self.fail[child]]
                q.append(child)


    def search(self, text):
        node = 0
        results = []
        for i, ch in enumerate(text):
            while node and ch not in self.goto[node]:
                node = self.fail[node]
            node = self.goto[node].get(ch, 0)
            for pat_idx in self.output[node]:
                results.append((i, pat_idx))
        return results


ac = AhoCorasick()
patterns = ["he", "she", "his", "hers"]
for i, p in enumerate(patterns):
    ac.add_pattern(p, i)
ac.build()
matches = ac.search("ushers")
for pos, idx in matches:
    p = patterns[idx]
    print(f"'{p}' ends at position {pos}")
Output
'she' ends at position 4
'he' ends at position 4
'hers' ends at position 5
'he' ends at position 5

কোথায় আহো-কোরাসিক ব্যবহৃত হয়?

  • নেটওয়ার্ক নিরাপত্তা (Network security): স্নোর্ট (Snort) এবং সুরিকাটা (Suricata) এটি ব্যবহার করে জীবন্ত নেটওয়ার্ক ট্র্যাফিকের বিরুদ্ধে হাজার হাজার আক্রমণ স্বাক্ষর মেলাতে
  • স্প্যাম এবং সামগ্রী ফিল্টারিং: বার্তাগুলোর মধ্যে থেকে নিষিদ্ধ কীওয়ার্ড শনাক্ত করতে
  • বায়োইনফরমেটিক্স: একাধিক জিন ক্রম একইসাথে জিনোমে অনুসন্ধান করতে
  • সার্চ ইঞ্জিন: এক পাসে একটি নথিতে একাধিক কোয়েরি পদ হাইলাইট করতে

আপনি যদি কেবল একটি মাত্র প্যাটার্ন অনুসন্ধান করতে চান, তবে KMP বা বোয়ার-মুর (Boyer-Moore) সহজতর। কিন্তু যখন আপনার কাছে একাধিক প্যাটার্ন এবং একটি মাত্র বড় টেক্সট থাকে, তখন আহো-কোরাসিক হলো সঠিক টুল।

Complexity

🏗️ ট্রাই নির্মাণ
প্রতিটি প্যাটার্ন অক্ষর অনুযায়ী সন্নিবেশ করুন — মোট নোড ≤ সমস্ত প্যাটার্ন জুড়ে মোট অক্ষর
মোট প্যাটার্নের দৈর্ঘ্যের সমানুপাতিক (Linear) O(Σ|Pi|)
🔗 ফেইলিওর লিংক BFS
BFS প্রতিটি ট্রাই নোডকে ঠিক একবার পরিদর্শন করে; ফেইলিওর লিংক গণনাটি নোড প্রতি O(1) হয়
মোট প্যাটার্নের দৈর্ঘ্যের সমানুপাতিক O(Σ|Pi|)
🔍 অনুসন্ধান পর্ব
প্রতিটি অক্ষর O(1) অ্যামর্টাইজড অটোমেটন ট্রানজিশন ঘটায় — টেক্সটটি ঠিক একবার পড়া হয়
টেক্সট + ম্যাচ-এর সমানুপাতিক O(n + total matches)
💾 স্পেস (Space)
প্রতিটি ট্রাই নোড একটি বর্ণমালা অক্ষরের জন্য একটি এজ সংরক্ষণ করে; O(Σ|Pi|) এ কমাতে হ্যাশ ম্যাপ ব্যবহার করুন
বর্ণমালা (Alphabet) × ট্রাই সাইজ O(σ · Σ|Pi|)

ছোট কুইজ

আপনাকে ১ জিবি লগ ফাইলে ৫০০টি কীওয়ার্ড খুঁজে বের করতে হবে। কেন আহো-কোরাসিক ৫০০ বার KMP চালনার চেয়ে ভালো?

পড়া চালিয়ে যান

কেএমপি অ্যালগরিদম (KMP Algorithm)
স্ট্রিং বা লেখা খোঁজার সময় কখনোই পিছনে ফিরবেন না — পুরনো জ্ঞান কাজে লাগিয়ে এগিয়ে যান
→
সাফিক্স অ্যারে কনস্ট্রাকশন (Suffix Array Construction)
সমস্ত সাফিক্স বা প্রত্যয় সাজানো — O(m log n) সাবস্ট্রিং সার্চ
→
রবিন-কার্প (Rabin-Karp)
ফিঙ্গারপ্রিন্ট দিয়ে বইয়ের ভেতর শব্দ খুঁজুন — কেবল ফিঙ্গারপ্রিন্ট মিললেই অক্ষর ধরে ধরে মিলিয়ে দেখুন
→