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

সাফিক্স অ্যারে কনস্ট্রাকশন (Suffix Array Construction)

সমস্ত সাফিক্স বা প্রত্যয় সাজানো — O(m log n) সাবস্ট্রিং সার্চ

naive build:ধীরগতিসম্পন্ন · O(n² log n)efficient build:খুব দ্রুত · O(n log n)search:O(m log n)LCP array:কাসাই (Kasai) এর অ্যালগরিদমের মাধ্যমে O(n)

"জাম" শব্দটি ধরুন। এবার এর সম্ভাব্য প্রতিটি সাফিক্স বা প্রত্যয় লিখুন — অর্থাৎ, একেবারে প্রথম দিক থেকে একটি একটি করে অক্ষর বাদ দিয়ে নতুন করে লিখুন:

"জাম"
"anana"
"nana"
"ana"
"na"
"a"

এবার এগুলোকে বর্ণানুক্রমিকভাবে সাজান:

"a" (ইনডেক্স 5 থেকে শুরু)
"ana" (ইনডেক্স 3 থেকে শুরু)
"anana" (ইনডেক্স 1 থেকে শুরু)
"জাম" (ইনডেক্স 0 থেকে শুরু)
"na" (ইনডেক্স 4 থেকে শুরু)
"nana" (ইনডেক্স 2 থেকে শুরু)

সাফিক্স অ্যারে (suffix array) মূলত, বর্ণানুক্রমিকভাবে শুরুর ইনডেক্সগুলোর একটি তালিকা: [5, 3, 1, 0, 4, 2]। ব্যস, এইটুকুই! কিন্তু এর মতো এই সাধারণ একটি সাজানো তালিকা অবিশ্বাস্য শক্তিশালী সব অপারেশন করতে সাহায্য করে।

সাফিক্স সাজানো (Sorting Suffixes) কেন উপকারী?

কারণ সাজানো জিনিসগুলোতে বাইনারি সার্চ (binary search) প্রয়োগ করা যায়! ধরুন আপনি "জাম" এর মধ্যে "ana" প্যাটার্নের সব অবস্থিতি (occurrences) খুঁজে পেতে চান, তাহলে আপনি কেবল সাজানো সাফিক্স তালিকায় বাইনারি সার্চ করে সেই এন্ট্রিগুলো খুঁজবেন যা "ana" দিয়ে শুরু হয়। আপনি সেগুলো O(m log n) সময়ে খুঁজে পাবেন — পুরো টেক্সট স্ক্যান করার কোনো প্রয়োজন নেই।

এটিকে অক্ষর ধরে টেক্সট স্ক্যান করার সাধারণ পদ্ধতির সাথে তুলনা করুন: যেখানে O(nm) সময় লাগে। সাফিক্স অ্যারে মূলত টেক্সট খোঁজার কাজটিকে একটি সর্টেড-লুকআপ (sorted-lookup) সমস্যায় পরিণত করে।

এটি দক্ষতার সাথে তৈরি করা: প্রিফিক্স ডাবলিং (Prefix Doubling)

সাধারণভাবে n সংখ্যক সাফিক্স সাজাতে O(n² log n) সময় লাগে — দুটি সাফিক্স তুলনা করতে O(n) সময় লাগতে পারে, এবং আপনি O(n log n) সংখ্যক এমন তুলনা করেন। ১ এমবি (1 MB) ফাইলের জন্য এটি অনেক ধীর।

চমৎকার O(n log n) সমাধানটি হলো প্রিফিক্স ডাবলিং (prefix doubling):

রাউন্ড ০: প্রতিটি সাফিক্সকে কেবল এর প্রথম অক্ষর দিয়ে র‍্যাংক বা সাজান।
রাউন্ড ১: পূর্ববর্তী রাউন্ডের (রাউন্ড-০) র‍্যাংকগুলোর সাথে মিল রেখে প্রতিটি সাফিক্সকে তার প্রথম ২ অক্ষর দিয়ে সাজান।
রাউন্ড ২: রাউন্ড-১ এর র‍্যাংক ব্যবহার করে প্রথম ৪টি অক্ষর দিয়ে সাজান। প্রতিটি রাউন্ডে তুলনার সীমানা দ্বিগুণ হয়।

log n সংখ্যক রাউন্ডের পর, সীমানা পুরো সাফিক্সকে কভার করে ফেলবে এবং আপনার সাজানো ক্রম তৈরি হয়ে যাবে। প্রতিটি রাউন্ড র্যাডিক্স সর্ট (radix sort) (O(n)) ব্যবহার করে, তাই মোট সময় লাগে O(n log n)।

এলসিপি অ্যারে (The LCP Array): বাড়তি সুপারপাওয়ার

আপনার কাছে সাফিক্স অ্যারে থাকলে আপনি খুব সহজেই এলসিপি অ্যারে (LCP array বা Longest Common Prefix) হিসেব করতে পারেন। LCP[i] আপনাকে বলে দেয় সাফিক্স SA[i] এবং সাফিক্স SA[i-1] এর শুরুতে কয়টি অক্ষর একই বা শেয়ার করা আছে — সহজ কথায় তাদের ওভারল্যাপের দৈর্ঘ্য কত।

এলসিপি অ্যারে যেন সাফিক্স অ্যারেকে এক্স-রে ভিশন (X-ray vision) দিয়ে পড়ার মতো। এটি O(n) সময়ে সবচেয়ে বড় পুনরাবৃত্ত সাবস্ট্রিং (longest repeated substring), আলাদা বা ডিফরেন্ট সাবস্ট্রিংগুলোর সংখ্যা এবং রেঞ্জ কোয়েরিকে অত্যন্ত দক্ষ করে তোলে। কাসাই (Kasai) অ্যালগরিদম পুরো এলসিপি অ্যারেকে O(n) সময়ে হিসেব করে।

দ্রষ্টব্য: অধিকাংশ বাস্তব প্রয়োগের ক্ষেত্রে সাফিক্স অ্যারে সাফিক্স ট্রির (suffix tree) জায়গা দখল করেছে। তাত্ত্বিকভাবে সাফিক্স ট্রি একই কাজ করলেও এটি অনেক পয়েন্টার-নির্ভর জটিল কোড এবং বড় ধ্রুবক (constant factors) চায়। অন্যদিকে একটি সাফিক্স অ্যারে শুধুমাত্র একটি ইন্টিজার অ্যারে — এটি ক্যাশ-বান্ধব (cache-friendly), তৈরি করা সোজা এবং মেমরিতে খুব কম জায়গা খায়।

সাফিক্স অ্যারে + বাইনারি সার্চ (Suffix Array + Binary Search)

def build_suffix_array(s):
    n = len(s)
    # Start: rank by first character
    sa = sorted(range(n), key=lambda i: s[i:])
    return sa

def search_suffix_array(text, sa, pattern):
    """Find all occurrences of pattern in text using binary search."""
    m = len(pattern)
    # Binary search for leftmost match
    lo, hi = 0, len(sa)
    while lo < hi:
        mid = (lo + hi) // 2
        if text[sa[mid]:sa[mid]+m] < pattern:
            lo = mid + 1
        else:
            hi = mid
    left = lo
    # Binary search for rightmost match
    lo, hi = left, len(sa)
    while lo < hi:
        mid = (lo + hi) // 2
        if text[sa[mid]:sa[mid]+m] <= pattern:
            lo = mid + 1
        else:
            hi = mid
    # Collect all matches in [left, lo)
    return sorted(sa[left:lo])

text = "jam"
sa = build_suffix_array(text)
print("SA:", sa)  # [5, 3, 1, 0, 4, 2]
print("Suffixes:", [text[i:] for i in sa])
print(search_suffix_array(text, sa, "ana"))  # [1, 3]

Output

SA: [5, 3, 1, 0, 4, 2]
Suffixes: ['a', 'ana', 'anana', 'jam', 'na', 'nana']
[1, 3]

সাফিক্স অ্যারে দিয়ে আপনি কী করতে পারবেন

প্যাটার্ন খোঁজা (Pattern search): O(m log n) সময়ে একটি প্যাটার্নের সমস্ত উপস্থিতির জন্য বাইনারি সার্চ
দীর্ঘতম পুনরাবৃত্ত সাবস্ট্রিং (Longest repeated substring): এলসিপি অ্যারের সর্বোচ্চ মানটি এর দৈর্ঘ্য নির্ধারণ করে — শুধু এলসিপি অ্যারেকে একবার স্ক্যান করুন
আলাদা বা ডিস্টিং সাবস্ট্রিং (distinct substrings) গণনা: n(n+1)/2 থেকে সমস্ত এলসিপি মানগুলোর যোগফল বাদ দিন
বারোজ-হুইলার ট্রান্সফর্ম (Burrows-Wheeler Transform): এটি কম্প্রেস করা টেক্সট ইনডেক্সের ভিত্তি (ডিএনএ অ্যাসেম্বলার এবং bzip2 এর মতো ফাইল কম্প্রেসরে ব্যবহৃত হয়)

সাফিক্স অ্যারে স্ট্রিং স্ট্রাকচারগুলোর মধ্যে সবচেয়ে বহুমুখী একটি ব্যবস্থা — এবং তাত্ত্বিকভাবে সমান সাফিক্স ট্রির বিপরীতে এটি একটি সাধারণ ইন্টিজার অ্যারে, যা কয়েক লাইনের কোড দিয়েই তৈরি করা সম্ভব।