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

বয়ার-মুর (Boyer-Moore)

প্যাটার্নটি পিছন থেকে পড়ুন, এবং বড় বড় অংশ বাদ দিয়ে যান — বাস্তবে সাবলিনিয়ার (sublinear) পারফরম্যান্স

best case:অবিশ্বাস্য দ্রুত (Blazing) · \(O(n/m)\)worst case:ধীরগতির (Slow) · \(O(nm)\)preprocessing:\(O(m + \sigma)\)

ধরুন আপনি একটি ডকুমেন্টের মধ্যে "CHAMPION" শব্দটি খুঁজছেন। বাম থেকে ডান দিকে প্রতিটি অক্ষর একটা একটা করে পড়ার পরিবর্তে, আপনি যদি প্রতিটি ৮-অক্ষরের উইন্ডোর শেষ অক্ষরটির দিকে একবার এক পলক তাকান। যদি আপনি সেখানে একটি 'Q' দেখতে পান, তবে আপনি সাথে সাথেই বুঝে যাবেন যে সঠিক অবস্থানে ওই ৮ টি অক্ষরের কোনোটিই 'N' থেকে 'A' হতে পারবে না — তখন আপনি পুরো উইন্ডোটাকেই বা অংশটিকেই স্কিপ করে বা বাদ দিয়ে যেতে পারেন! এটাই হলো বয়ার-মুর (Boyer-Moore) অ্যালগরিদমের পেছনের মূল ধারণা।

ডান-থেকে-বামে (right-to-left) প্যাটার্ন স্ক্যান বা পরীক্ষা করার মাধ্যমে, প্যাটার্নের একেবারে শেষের দিকে একটি মাত্র অমিল বা মিসম্যাচ পুরো উইন্ডোটাকেই স্কিপ করে যেতে পারে। বাস্তবের ইংরেজি টেক্সটের ক্ষেত্রে, বয়ার-মুর অ্যালগরিদম প্রায়ই প্রতি m সংখ্যক অক্ষরের মধ্যে মাত্র ১টি অক্ষর পড়ে — যা একটি সাবলিনিয়ার (sublinear) পারফরম্যান্স।

খারাপ অক্ষরের নিয়ম (The Bad Character Rule)

যখন টেক্সটের c অক্ষরের সাথে প্যাটার্নের j অবস্থানে একটি অমিল বা মিসম্যাচ দেখা দেয়, তখন ব্যাড ক্যারেক্টার রুল (bad character rule) বা খারাপ অক্ষরের নিয়মটি এই প্রশ্নটি করে: এই c অক্ষরটি কি প্যাটার্নে j অবস্থানের বামদিকে কোথাও আছে?

যদি উত্তর হয় না (no): তাহলে প্যাটার্নটিকে c এর থেকে পুরোপুরি সরিয়ে নিন — সর্বোচ্চ m সংখ্যক পজিশন বা অবস্থান পর্যন্ত স্কিপ করা যায়!
যদি উত্তর হয় হ্যাঁ (yes): তাহলে প্যাটার্নটিকে ডান দিকে সরাতে থাকুন যতক্ষণ না পর্যন্ত প্যাটার্নের সবচেয়ে ডানদিকের c এর উপস্থিতিটি টেক্সটের c এর সাথে পুরোপুরি মিলে যায় বা অ্যালাইন (align) হয়।

প্রি-প্রসেসিং (Preprocessing): bc[c] = শেষবার যেখানে c অক্ষরটি প্যাটার্নে উপস্থিত ছিল তার অবস্থান (না থাকলে -1) নিয়ে একটি টেবিল বা সারণি তৈরি করুন। এর জন্য \(O(m + \sigma)\) সময় লাগে, যেখানে \(\sigma\) হলো বর্ণমালা বা অ্যালফাবেটের (alphabet) আকার।

ভালো সাফিক্স বা প্রত্যয়ের নিয়ম (The Good Suffix Rule)

যখন মিসম্যাচ বা অমিল হওয়ার আগে প্যাটার্নের কিছু অংশের সাফিক্স (suffix) মিলে যায়, তখন গুড সাফিক্স রুল (good suffix rule) বা ভালো সাফিক্স নিয়মটি প্যাটার্নের অন্য কোথাও আগে থেকে মিলে যাওয়া সাফিক্সটির সবচেয়ে ডানদিকের কপি বা অনুলিপিটিকে খুঁজতে চেষ্টা করে — এর সাথে শর্ত থাকে বা নিশ্চিত করে যে এর আগে একটি ভিন্ন অক্ষর থাকতে হবে (তা না হলে একই অমিলের পুনরাবৃত্তি ঘটবে)। যদি এমন কোনো কপি খুঁজে পাওয়া না যায়, তবে আমরা প্যাটার্নের সবচেয়ে বড় বা লম্বা প্রফিক্সটি (prefix) খুঁজি যা ওই মিলে যাওয়া অংশের সাফিক্সও বটে।

বয়ার-মুর অ্যালগরিদমটি সব সময় এই দুটো নিয়মের মধ্যে যেখানে বা যেটিতে সর্বোচ্চ বা ম্যাক্সিমাম (maximum) শিফট বা লাফ দেওয়া যায়, সেটিকে বেছে নেয়। আর ঠিক এই কারণেই এটি এত দ্রুতগতির — এর যেকোনো একটি নিয়ম একাই অনেক কিছু স্কিপ করতে পারে, আর ম্যাক্সিমামটি বেছে নিলে তা আরও বহুগুণে বেশি স্কিপ বা বাদ দিয়ে যেতে পারে।

বয়ার-মুর-হর্সপুল: এর একটি সহজ সংস্করণ (Boyer-Moore-Horspool: The Simpler Cousin)

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

দ্রষ্টব্য: বয়ার-মুর (Boyer-Moore) অ্যালগরিদমটি অনেকটা একজন স্পিড রিডারের (speed reader) মতো কাজ করে যিনি প্রতিটি লাইনের একেবারে শেষ শব্দটির দিকে প্রথমে এক নজর বুলিয়ে নেন। যদি শেষ শব্দটিই ভুল হয়, তবে তিনি না পড়েই পুরো লাইনটিকে বা অংশটিকে স্কিপ করে বা বাদ দিয়ে যেতে পারেন। ইংরেজির মতো সমৃদ্ধ বা বৃহৎ অ্যালফাবেটগুলোর ক্ষেত্রে, বেশিরভাগ মিসম্যাচ বা অমিলই এমন অক্ষরে গিয়ে হয় যেগুলো প্যাটার্নে একেবারেই থাকে না — যার ফলে প্রায় সবসময়েই সাথে সাথে পুরো উইন্ডো স্কিপ বা লাফ দিয়ে পার হওয়া যায়।

বয়ার-মুর-হর্সপুল (ব্যাবহারিক ধরন বা Practical Variant)

def horspool(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    # Build bad-character shift table
    shift = {c: m for c in set(text)}
    for i in range(m - 1):
        shift[pattern[i]] = m - 1 - i

    results = []
    i = m - 1  # index of rightmost char in window
    while i < n:
        j = m - 1
        k = i
        while j >= 0 and text[k] == pattern[j]:
            j -= 1
            k -= 1
        if j == -1:
            results.append(k + 1)
        i += shift.get(text[i], m)
    return results

print(horspool("HERE IS A SIMPLE EXAMPLE", "EXAMPLE"))  # [17]
print(horspool("abcabcabc", "abc"))  # [0, 3, 6]

Output

[17]
[0, 3, 6]

বয়ার-মুর (Boyer-Moore) কখন ব্যবহার করা সবচেয়ে ভালো?

বড় আকারের অ্যালফাবেটের (Large alphabets) ক্ষেত্রে (ইংরেজি টেক্সট, সোর্স কোড): ব্যাড ক্যারেক্টার রুল অনেক বড় বড় স্কিপ বা লাফ দেয় — কারণ টেক্সটের বেশিরভাগ অক্ষর প্যাটার্নে একেবারেই থাকে না বা খুব কম থাকে
বড় লম্বা প্যাটার্নের (Long patterns) ক্ষেত্রে: একসাথে m পজিশন পরিমাণ স্কিপ করা বা বাদ দেওয়ার অর্থ হলো অনেক কম উইন্ডো বা অংশ চেক করতে হবে
বাস্তব দুনিয়ার টেক্সট সার্চের (Real-world text search) ক্ষেত্রে: grep কমান্ড, প্রায় সব টেক্সট এডিটর এবং সার্চ ইঞ্জিনগুলোতে মূলত বয়ার-মুরের বিভিন্ন ধরন বা সংস্করণ ব্যবহার করা হয়

ছোট অ্যালফাবেটের (small alphabets) ক্ষেত্রে (যেমন ডিএনএ/DNA যেখানে শুধু A/C/G/T থাকে), ব্যাড ক্যারেক্টার টেবিল অনেক ছোট ছোট স্কিপ দেয় এবং এক্ষেত্রে কেএমপি (KMP) বেশ ভালো প্রতিযোগী হতে পারে। তবে একসাথে একাধিক প্যাটার্ন (multiple patterns) খোঁজার জন্য অবশ্যই আহো-কোরাসিক (Aho-Corasick) অ্যালগরিদমটি ব্যবহার করুন।

Complexity

🚀 বেস্ট কেস বা সেরা পরিস্থিতি (বড় অ্যালফাবেটের বা alphabets ক্ষেত্রে)

প্যাটার্নের প্রতিবার শেষের দিকের মিসম্যাচে m অক্ষর পরিমাণ স্কিপ বা বাদ দেওয়া যায় — ইংরেজি টেক্সটের ক্ষেত্রে এটি খুবই সাধারণ একটি বিষয়

সাবলিনিয়ার (Sublinear) — অধিকাংশ টেক্সটই স্কিপ বা বাদ দিয়ে যায় \(O(n/m)\)

💀 ওয়ার্স্ট কেস বা সবচেয়ে খারাপ পরিস্থিতি (অ্যাডভারসারিয়াল ইনপুট বা adversarial input এর ক্ষেত্রে)

এমনটা তখন ঘটে যখন ইনপুটে বারবার একই অক্ষর থাকে এবং প্যাটার্নটিও দেখতে 'aaab'-এর মতো হয় — ব্যাড ক্যারেক্টার রুলের (bad char rule) শিফটগুলো তখন অতি ক্ষুদ্র হয়

কোয়াড্রাটিক বা দ্বিঘাতী (Quadratic) — চরম অস্বস্তিকর বা প্যাথলজিক্যাল (pathological) \(O(nm)\)

🔧 প্রি-প্রসেসিং (Preprocessing)

\(\sigma\) = অ্যালফাবেট বা বর্ণমালার আকার (ASCII-এর জন্য 256); ব্যাড ক্যারেক্টার টেবিলের জন্য \(O(\sigma)\), আর গুড সাফিক্স টেবিলের জন্য \(O(m)\)

প্যাটার্ন এবং অ্যালফাবেট বা বর্ণমালার ওপর ভিত্তি করে লিনিয়ার (Linear) \(O(m+\sigma)\)

💾 মেমরি বা স্পেস (Space)

হর্সপুলের জন্য শুধুমাত্র ব্যাড ক্যারেক্টার টেবিলের \(O(\sigma)\) মেমরি লাগে — যা অত্যন্ত লাইটওয়েট বা হালকা ওজনের

প্যাটার্ন + অ্যালফাবেটের বা বর্ণমালার টেবিলগুলো \(O(m+\sigma)\)

ছোট কুইজ

বয়ার-মুর (Boyer-Moore) প্যাটার্নটিকে ডান-থেকে-বামে (right-to-left) স্ক্যান করে। এটি কীভাবে সাবলিনিয়ার (sublinear) সার্চকে সম্ভব করে তোলে?

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

কেএমপি অ্যালগরিদম (KMP Algorithm)

স্ট্রিং বা লেখা খোঁজার সময় কখনোই পিছনে ফিরবেন না — পুরনো জ্ঞান কাজে লাগিয়ে এগিয়ে যান

→

জেড-অ্যালগরিদম (Z-Algorithm)

জেড-অ্যারে (Z-array): প্রতিটি অবস্থানে হিসাব মেলানোর দৈর্ঘ্য — লিনিয়ার প্যাটার্ন ম্যাচিং

→

রবিন-কার্প (Rabin-Karp)

ফিঙ্গারপ্রিন্ট দিয়ে বইয়ের ভেতর শব্দ খুঁজুন — কেবল ফিঙ্গারপ্রিন্ট মিললেই অক্ষর ধরে ধরে মিলিয়ে দেখুন

→