বর্নী স্ট্রিং সমস্যা (Suffix Tree and Suffix Array)

বর্নী স্ট্রিং সমস্যা হলো স্ট্রিং থেকে বিভিন্ন উপাদান বা উপস্ট্রিং খোঁজার একটি ক্ষেত্র, যেখানে Suffix Tree এবং Suffix Array দুটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার।

১. Suffix Tree

Suffix Tree হলো একটি বিশেষ গাছের গঠন যা একটি স্ট্রিংয়ের সমস্ত সম্ভাব্য suffix (শেষাংশ) গুলি ধারণ করে। এটি একটি ট্রাই ধরনের ডেটা স্ট্রাকচার যেখানে প্রতিটি পাতা একটি suffix উপস্থাপন করে।

বৈশিষ্ট্য:

• O(n) সময়ে স্ট্রিংয়ের সকল suffix তৈরি করা যায়।
• অনুসন্ধান করা এবং substring matching করার জন্য খুবই কার্যকর।
• সংক্ষেপিত এবং স্মৃতি দক্ষ।

Suffix Tree তৈরি করার জন্য অ্যালগরিদম:

Suffix Tree নির্মাণের জন্য Ukkonen's Algorithm ব্যবহৃত হয়, যা O(n)O(n) সময়ে গাছ তৈরি করতে সক্ষম।

উদাহরণ (Python Implementation):

class SuffixTreeNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class SuffixTree:
    def __init__(self, text):
        self.root = SuffixTreeNode()
        self.build_suffix_tree(text)

    def build_suffix_tree(self, text):
        for i in range(len(text)):
            self.insert_suffix(text[i:])

    def insert_suffix(self, suffix):
        node = self.root
        for char in suffix:
            if char not in node.children:
                node.children[char] = SuffixTreeNode()
            node = node.children[char]
        node.is_end = True

    def search(self, pattern):
        node = self.root
        for char in pattern:
            if char not in node.children:
                return False
            node = node.children[char]
        return True if node.is_end else False

# উদাহরণ ব্যবহার
text = "banana"
suffix_tree = SuffixTree(text)
print("Searching for 'ana':", suffix_tree.search('ana'))
print("Searching for 'nan':", suffix_tree.search('nan'))

২. Suffix Array

Suffix Array হলো একটি sorted array যা একটি স্ট্রিংয়ের সকল suffix এর সূচক ধারণ করে। এটি Suffix Tree- এর তুলনায় অনেক বেশি স্থান অর্থনৈতিক এবং সহজে তৈরি করা যায়।

বৈশিষ্ট্য:

• Suffix Array স্ট্রিংটির প্রস্থ বাড়ানোর জন্য স্মৃতির প্রয়োজনীয়তা কমায়।
• এটি সাধারণত একটি সাঁকোডেড গাছের সাথে ব্যবহৃত হয় যা substring অনুসন্ধানের জন্য দ্রুত।

Suffix Array তৈরি করার জন্য অ্যালগরিদম:

Suffix Array নির্মাণের জন্য কয়েকটি অ্যালগরিদম আছে, যেমন:

1. Naive Approach: O(n^2 log n) সময়ের মধ্যে তৈরি করা হয়।
2. O(n log n) এবং O(n) টাইম অ্যালগরিদম।

উদাহরণ (Python Implementation):

def build_suffix_array(text):
    suffixes = [(text[i:], i) for i in range(len(text))]
    suffixes.sort()  # Sort the suffixes
    return [suffix[1] for suffix in suffixes]

# উদাহরণ ব্যবহার
text = "banana"
suffix_array = build_suffix_array(text)
print("Suffix Array:", suffix_array)

সারসংক্ষেপ

Suffix Tree:

• একটি গাছের গঠন যা স্ট্রিংয়ের সমস্ত suffix ধারণ করে।
• substring matching এবং অনুসন্ধানের জন্য কার্যকর।
• O(n) সময়ে তৈরি করা যায়।

Suffix Array:

• একটি sorted array যা suffix এর সূচক ধারণ করে।
• Suffix Tree এর তুলনায় স্থান সংরক্ষণ করে।
• সাধারণভাবে O(n log n) বা O(n) সময়ে তৈরি করা যায়।

Suffix Tree এবং Suffix Array উভয়ই টেক্সট প্রক্রিয়াকরণ, কম্পিউটেশনাল বায়োলজি এবং ডেটা কম্প্রেশন সহ বিভিন্ন ক্ষেত্রে ব্যবহার করা হয়।