ট্রাই (Trie) এবং এর অ্যাপ্লিকেশন

ট্রাই (Trie) হল একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা মূলত স্ট্রিং বা ক্যারেক্টারের সেটকে সংরক্ষণ এবং অনুসন্ধান করার জন্য ব্যবহৃত হয়। এটি একটি ডিসিসন ট্রীর মতো কাজ করে, যেখানে প্রতিটি নোড একটি ক্যারেক্টারকে প্রতিনিধিত্ব করে এবং নোডের পথ একটি শব্দের আকারে গঠন করে।

ট্রির মূল বৈশিষ্ট্য

স্ট্রিং সংগ্রহ: ট্রি ডেটা স্ট্রাকচার স্ট্রিংগুলিকে ক্যারেক্টার ভিত্তিক সংরক্ষণ করে, যা দ্রুত অনুসন্ধান নিশ্চিত করে।

শব্দের সংরক্ষণ: ট্রিতে সাধারণত একটি শব্দের প্রতিনিধিত্বকারী সমস্ত ক্যারেক্টারগুলি তাদের নিজ নিজ স্তরে থাকে।

আনুভূমিক অ্যাক্সেস: শব্দের আকারে অনুসন্ধানের সময়, একাধিক শব্দকে একসাথে পরিচালনা করা যায়।

স্মৃতি দক্ষতা: যদি একই সাবস্ট্রিংগুলি প্রায়ই থাকে, তবে এটি মেমরি সঞ্চয় করতে পারে, কারণ কমন ক্যারেক্টারগুলি একসাথে সঞ্চিত থাকে।

ট্রির কাজের পদ্ধতি

• ইনসার্ট (Insert): একটি নতুন শব্দ ট্রিতে যুক্ত করা হয়। প্রতিটি ক্যারেক্টার ট্রির একটি নোডে সংরক্ষণ করা হয়।
• সার্চ (Search): একটি শব্দ ট্রিতে আছে কিনা তা পরীক্ষা করতে, ট্রির প্রতিটি স্তরে শব্দের ক্যারেক্টারগুলোকে অনুসন্ধান করা হয়।
• ডিলিট (Delete): একটি শব্দ ট্রি থেকে মুছে ফেলার প্রক্রিয়া, যেখানে শুধুমাত্র প্রয়োজনীয় নোডগুলি মুছে ফেলা হয়।

ট্রির অ্যাপ্লিকেশন

ট্রির বিভিন্ন বাস্তব জীবনের ব্যবহারে ব্যবহৃত হয়, যেমন:

লুকআপ টেবিল: শব্দ বা স্ট্রিং লুকআপ করতে ব্যবহৃত হয়, যেমন অভিধানে শব্দ খুঁজে বের করা।

অটোকমপ্লিট ফিচার: ব্যবহারকারীর টাইপ করার সময় সম্ভাব্য শব্দের পরামর্শ দেওয়ার জন্য ব্যবহৃত হয়, যেমন সার্চ ইঞ্জিন এবং টাইপিং অ্যাপ্লিকেশন।

প্যাটার্ন ম্যাচিং: শব্দ বা প্যাটার্ন ম্যাচ করার জন্য, বিশেষত যখন বড় টেক্সট ডেটা পরিচালনা করা হয়।

ডিকশনারি সংরক্ষণ: শব্দের একটি সংগ্রহ (dictionary) পরিচালনা করার জন্য ট্রি ব্যবহার করা হয়, যা দ্রুত অনুসন্ধান এবং ইনসার্টের সুবিধা দেয়।

কম্পিউটার নেটওয়ার্ক: IP অ্যাড্রেস বা DNS নামের ক্ষেত্রে, ট্রি ব্যবহৃত হয়, যেখানে প্রতিটি স্তর একটি অংশকে প্রতিনিধিত্ব করে।

উদাহরণ (পাইথনে)

নীচে একটি সাধারণ ট্রি ডেটা স্ট্রাকচার তৈরি এবং ব্যবহার করার উদাহরণ দেওয়া হলো।

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_end_of_word = True

    def search(self, word):
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.is_end_of_word

    def starts_with(self, prefix):
        current = self.root
        for char in prefix:
            if char not in current.children:
                return False
            current = current.children[char]
        return True

# ব্যবহার
trie = Trie()
trie.insert("hello")
trie.insert("hell")
trie.insert("helicopter")

print(trie.search("hello"))      # আউটপুট: True
print(trie.search("hell"))       # আউটপুট: True
print(trie.search("helicopter")) # আউটপুট: True
print(trie.search("helix"))      # আউটপুট: False
print(trie.starts_with("he"))    # আউটপুট: True

উপসংহার

ট্রাই একটি শক্তিশালী এবং কার্যকরী ডেটা স্ট্রাকচার যা স্ট্রিং বা ক্যারেক্টার ভিত্তিক তথ্যকে সংরক্ষণ এবং অনুসন্ধানের জন্য ব্যবহৃত হয়। এর কার্যকরী পদ্ধতি এবং দ্রুত অনুসন্ধান ক্ষমতার কারণে এটি বিভিন্ন বাস্তব জীবনের অ্যাপ্লিকেশনগুলিতে ব্যাপকভাবে ব্যবহৃত হয়।