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

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

ফিঙ্গারপ্রিন্ট দিয়ে বইয়ের ভেতর শব্দ খুঁজুন — কেবল ফিঙ্গারপ্রিন্ট মিললেই অক্ষর ধরে ধরে মিলিয়ে দেখুন
average case:দ্রুত (Fast) · \(O(n+m)\)worst case:ধীর (Slow) · \(O(nm)\)space:খুব সামান্য (Tiny) · \(O(1)\)

ধরুন আপনি ৫০০ পৃষ্ঠার একটি বইয়ে আপনার এক বন্ধুর নাম খুঁজছেন। প্রতিটি পৃষ্ঠার প্রতিটি অক্ষর ধরে ধরে পরীক্ষা করতে গেলে তো সারা জীবন লেগে যাবে! কিন্তু কেমন হবে যদি আপনি আপনার বন্ধুর নামের একটি ছোট ফিঙ্গারপ্রিন্ট (fingerprint) বা সংক্ষিপ্ত নম্বর তৈরি করে নেন, এবং প্রথমে শুধু ফিঙ্গারপ্রিন্টগুলো মিলিয়ে দেখেন? যখনই কোনো ফিঙ্গারপ্রিন্ট মিলবে, শুধুমাত্র তখনই আপনি আসল অক্ষরগুলো পড়ে দেখবেন।

রবিন-কার্প (Rabin-Karp) ঠিক এই কাজটিই করে থাকে। এটি প্যাটার্নের জন্য একটি ফিঙ্গারপ্রিন্ট (যাকে হ্যাশ বা hash বলা হয়) তৈরি করে, তারপর পুরো টেক্সটের ওপর দিয়ে একটি উইন্ডো স্লাইড করে নিয়ে যায় এবং উভয় ফিঙ্গারপ্রিন্ট তুলনা করে। বেশিরভাগ উইন্ডোই মুহূর্তের মধ্যে ফিঙ্গারপ্রিন্ট টেস্টে বাদ পড়ে যায়। খুব বিরল ক্ষেত্রেই যখন ফিঙ্গারপ্রিন্ট মিলে যায়, শুধু তখনই পুরো অক্ষরগুলো ধরে ধরে মেলানোর প্রয়োজন হয়।

রোলিং হ্যাশ ট্রিক (The Rolling Hash Trick)

এর আসল চাতুর্যটি হলো: যখন আপনি উইন্ডোটিকে এক ধাপ ডানে সরাবেন, তখন আপনাকে পুরো ফিঙ্গারপ্রিন্টটি শূন্য থেকে নতুন করে হিসাব করতে হবে না। এর বদলে আপনি এটিকে রোল (roll) করবেন — অর্থাৎ সবচেয়ে বামের অক্ষরের মানটি বিয়োগ করবেন, পুরোটাকে বামে শিফট করবেন (shift left), এবং নতুন যোগ হওয়া সবচেয়ে ডানদিকের অক্ষরের মানটি যোগ করবেন। এই কৌশলের কারণে উইন্ডো সরানোর প্রতিটি ধাপের জন্য \(O(m)\) এর বদলে মাত্র \(O(1)\) সময় লাগে। এটিকেই বলা হয় রোলিং হ্যাশ (rolling hash)।

গাণিতিকভাবে, টেক্সটের i অবস্থান থেকে শুরু হওয়া m দৈর্ঘ্যের একটি উইন্ডোর জন্য:
hash = (s[i]·b^(m-1) + s[i+1]·b^(m-2) + ... + s[i+m-1]) mod p
এক ধাপ স্লাইড বা সরানোর পর: new_hash = (old_hash - s[i]·b^(m-1)) × b + s[i+m]) mod p

স্পিউরিয়াস হিট (Spurious Hits): যখন ফিঙ্গারপ্রিন্ট ভুল কথা বলে

মাঝে মাঝে সম্পূর্ণ ভিন্ন দুটি স্ট্রিংয়ের ফিঙ্গারপ্রিন্ট একই হয়ে যেতে পারে — একে হ্যাশ কলিশন (hash collision) বলা হয়। যখন এমনটি ঘটে, তখন নিশ্চিত হওয়ার জন্য রবিন-কার্প অ্যালগরিদম প্রতিটি অক্ষর ধরে ধরে পুরো প্যাটার্নটি মিলিয়ে দেখে। মেলানোর পর যদি দেখা যায় সেগুলো আসলে এক নয়, তবে একে বলা হয় স্পিউরিয়াস হিট (spurious hit) বা মিথ্যা মিল। একটি ভালো মানের হ্যাশ এবং বেশ বড় একটি মৌলিক সংখ্যা বা প্রাইম মডুলাস (prime modulus) ব্যবহার করলে, স্পিউরিয়াস হিট প্রায় হয়ই না বললেই চলে এবং এর ফলে বাস্তবে অ্যালগরিদমটি প্রায় \(O(n+m)\) সময়ের কাছাকাছি থাকে।

একসাথে একাধিক প্যাটার্ন খোঁজা

এই জায়গাতেই রবিন-কার্প অ্যালগরিদম তার আসল জাদু দেখায়। আপনি যদি একসাথে k সংখ্যক ভিন্ন ভিন্ন প্যাটার্ন খুঁজতে চান, তবে আগে সবগুলোর (k) হ্যাশ বের করে একটি হ্যাশ সেটে (hash set) সংরক্ষণ করুন। এরপর উইন্ডো সরানোর সময় প্রতিটি উইন্ডোকে সেটের সাথে মাত্র একবার \(O(1)\) সময়ে মিলিয়ে দেখলেই হবে। এতে মোট সময় লাগবে: \(O(n + \Sigma m_i)\) — যা সবগুলো ইনপুট সাইজের যোগফলের সাপেক্ষে লিনিয়ার (linear)। অন্যদিকে, অন্যান্য অ্যালগরিদম (যেমন KMP) ব্যবহার করলে k সংখ্যক প্যাটার্নের জন্য পুরো কাজটি k বার আলাদাভাবে করতে হতো।

দ্রষ্টব্য: রোলিং হ্যাশ অনেকটা মুদি দোকানের কনভেয়র বেল্ট স্কেলের (conveyor belt scale) মতো — যখন কোনো জিনিস বেল্ট থেকে নেমে যায় এবং নতুন আরেকটি জিনিস এসে পড়ে, তখন আপনি শুরু থেকে সবকিছুর ওজন নতুন করে মাপেন না। আপনি শুধু নেমে যাওয়া জিনিসটির ওজন বাদ দেন এবং নতুনটির ওজন যোগ করেন।

রবিন-কার্প প্যাটার্ন সার্চ (Rabin-Karp Pattern Search)

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    BASE, MOD = 31, 10**9 + 7
    # Precompute base^(m-1) mod MOD
    power = pow(BASE, m - 1, MOD)


    def char_val(c):
        return ord(c) - ord('a') + 1


    # Compute initial hashes
    ph = th = 0
    for i in range(m):
        ph = (ph * BASE + char_val(pattern[i])) % MOD
        th = (th * BASE + char_val(text[i])) % MOD


    results = []
    for i in range(n - m + 1):
        if th == ph and text[i:i+m] == pattern:  # check spurious hits
            results.append(i)
        if i < n - m:
            th = (th - char_val(text[i]) * power) % MOD
            th = (th * BASE + char_val(text[i + m])) % MOD
    return results


print(rabin_karp("abcabcabc", "abc"))  # [0, 3, 6]
print(rabin_karp("hello world", "world"))  # [6]
Output
[0, 3, 6]
[6]

কখন আপনার রবিন-কার্প ব্যবহার করা উচিত?

  • একসাথে একাধিক প্যাটার্ন খোঁজার ক্ষেত্রে — এটিই এর মূল শক্তি বা সুপারপাওয়ার
  • যখন আপনি ভালো গড় সময়ের (average-case behavior) জন্য একটি সাধারণ ইমপ্লিমেন্টেশন খুঁজছেন
  • ২ডি (2D) প্যাটার্ন ম্যাচিংয়ের ক্ষেত্রে (যেখানে হ্যাশিংকে গ্রিডে সম্প্রসারিত করা যায়)

মাত্র একটি প্যাটার্ন খোঁজার ক্ষেত্রে, ওয়ার্স্ট কেসে (worst case) KMP বা Boyer-Moore অপেক্ষাকৃত দ্রুততর হতে পারে। কিন্তু যখন আপনার কাছে ডজন খানেক বা শত শত প্যাটার্ন থাকে, তখন রবিন-কার্পের হ্যাশ-সেট কৌশলকে হারিয়ে দেওয়া বেশ কঠিন কাজ।

Complexity

🚀 গড়ের ক্ষেত্রে / প্রত্যাশিত (Average / expected case)
প্যাটার্ন হ্যাশ করতে \(O(m)\), এবং পুরো উইন্ডো স্লাইড করতে \(O(n)\) লাগে — একটি ভালো মানের হ্যাশের সাহায্যে স্পিউরিয়াস হিট বা ফলস পজিটিভ (spurious hits) একেবারে নগণ্য হয়ে যায়
বিদ্যুৎ বেগে চলে (Lightning fast) \(O(n+m)\)
💀 ওয়ার্স্ট কেস (খারাপ হ্যাশ হলে)
যদি প্রতিটি উইন্ডোতেই স্পিউরিয়াস হিট হয়, তবে প্রতিবার \(O(m)\) সময় ধরে যাচাই করতে হয় — একটি বড় প্রাইম নম্বর (prime) ব্যবহার করলে এটি ঘটার সম্ভাবনা খুবই বিরল
ধীর — প্রতিটি উইন্ডোতেই কলিশন (collision) ঘটে \(O(nm)\)
💾 মেমরি বা স্পেস (Space)
এটি শুধু কয়েকটি হ্যাশ ভ্যালু এবং একটি পূর্ব-হিসাবকৃত পাওয়ার (power) সংরক্ষণ করে — KMP এর মতো কোনো \(O(m)\) সাইজের অ্যারের প্রয়োজন হয় না
প্রায় শূন্যের কাছাকাছি (Barely anything) \(O(1)\)
🎯 একাধিক প্যাটার্ন (k সংখ্যক প্যাটার্ন)
সবগুলো প্যাটার্নের হ্যাশগুলো একত্রে একটি সেটে রাখুন; প্রতিটি উইন্ডো কেবল একটিমাত্র \(O(1)\) সেট লুকআপ (lookup) করবে — বাড়তি কোনো পাসের (pass) প্রয়োজন হয় না
তারপরেও পুরো টেক্সট একবার স্ক্যান করলেই চলে \(O(n + \Sigma m_i)\)

ছোট কুইজ

আপনি ৫ সাইজের একটি উইন্ডোকে কোনো টেক্সটের ওপর দিয়ে স্লাইড করে নিচ্ছেন। যখন উইন্ডোটি ডানদিকে এক ধাপ সরে যায়, তখন একটি রোলিং হ্যাশ (rolling hash) কীভাবে আপডেট হয়?

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