Trie এর ধারণা এবং ব্যবহার

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

Trie এর ধারণা

ট্রি একটি অর্ডারড কিপ-ভ্যালু স্টোরেজ ডেটা স্ট্রাকচার যা একটি স্ট্রিং থেকে তথ্য বের করার জন্য ব্যবহৃত হয়। এটি prefix tree বা digital tree নামেও পরিচিত, কারণ ট্রাই স্ট্রিংগুলোর একটি বা একাধিক প্রিফিক্স বা পূর্ববর্তী অংশগুলো সংরক্ষণ করে। প্রতিটি নোড একটি স্ট্রিংয়ের একটি অক্ষর ধারণ করে এবং স্ট্রিংগুলোর পূর্ববর্তী অংশগুলোর মাধ্যমে অনুসন্ধান করা সহজ হয়।

ট্রাই স্ট্রিংগুলোর মধ্যে সম্পর্ক বজায় রাখে এবং অনুসন্ধান, ইনসার্ট, ডিলিট অপারেশনগুলো O(k) সময়ে সম্পন্ন করতে সাহায্য করে, যেখানে k হল স্ট্রিংয়ের দৈর্ঘ্য। এটি একটি অত্যন্ত কার্যকরী ডেটা স্ট্রাকচার বিশেষত ডিকশনারি বা অটো-কমপ্লিট সিস্টেমে ব্যবহৃত হয়।

Trie এর গঠন

ট্রির মূল ধারণা হলো প্রতিটি স্ট্রিংয়ের একটি প্রিফিক্সকে শেয়ার করা। স্ট্রিংগুলো একটি গাছের (tree) শাখার মতো সংরক্ষিত থাকে, যেখানে একটি শাখা অন্য শাখার অংশ হতে পারে।

• Root Node: ট্রির মূল নোড। এটি শূন্য বা কোনো অক্ষর ধারণ করে না।
• Children Nodes: প্রতিটি নোডের মধ্যে ছোট ছোট অক্ষর থাকে, যা পরবর্তী স্তরে অক্ষরের প্রতিনিধিত্ব করে।
• End Node: একটি স্ট্রিংয়ের শেষ অক্ষর যখন ট্রির মধ্যে পৌঁছায়, তখন আমরা সেই নোডটিকে একটি "end of string" চিহ্নিত করতে পারি, যাতে বুঝতে পারি যে এটি একটি পূর্ণ স্ট্রিংয়ের শেষ।

Trie এর ব্যবহার

ট্রির কিছু প্রধান ব্যবহার রয়েছে যা বিভিন্ন ধরণের ডেটা সংরক্ষণ ও অনুসন্ধানের ক্ষেত্রে কার্যকরী।

1. স্ট্রিং অনুসন্ধান (String Search)

ট্রির সবচেয়ে সাধারণ ব্যবহার হল স্ট্রিং অনুসন্ধান। আমরা একটি স্ট্রিংয়ের কোনো অংশের অনুসন্ধান করতে চাইলে, ট্রি আমাদের সেই অংশের প্রিফিক্সের মাধ্যমে দ্রুত সন্ধান করতে সাহায্য করে।

উদাহরণ:

ধরা যাক, আমাদের একটি ডিকশনারি আছে, এবং আমরা দ্রুত একটি স্ট্রিং খুঁজে বের করতে চাই।

2. অটো-কমপ্লিট (Auto-Completion)

ট্রি ব্যবহৃত হয় অটো-কমপ্লিট ফিচার তৈরির জন্য, যেখানে ব্যবহারকারী যখন কিছু টাইপ করে, তখন ট্রি তার টাইপ করা অক্ষরের প্রিফিক্স অনুসারে সম্ভাব্য শব্দগুলি প্রদান করে।

উদাহরণ:

যদি একটি ডিকশনারিতে "apple", "app", "bat", "ball" শব্দগুলি থাকে, তাহলে ব্যবহারকারী যখন "ap" টাইপ করবে, তখন ট্রি তাকে "apple", "app" শব্দগুলো দেখাতে পারবে।

3. ডিকশনারি (Dictionary)

ট্রি ব্যবহার করা হয় একটি ডিকশনারির শব্দ সংরক্ষণ এবং তার অনুসন্ধান করার জন্য। ডিকশনারি অপারেশন যেমন শব্দের উপস্থিতি চেক করা, শব্দের পদ্ধতি ঠিক করা ইত্যাদি দ্রুত করতে ট্রি ব্যবহার করা হয়।

4. এডিট ডিস্ট্যান্স (Edit Distance)

স্ট্রিংয়ের মধ্যে দুটি শব্দের পার্থক্য মাপতে (যেমন, কোন শব্দটিকে আরেকটি শব্দে পরিণত করতে কতগুলো অপারেশন লাগবে), ট্রি ব্যবহার করা হয়।

Trie এর জাভা ইমপ্লিমেন্টেশন

নিচে একটি সাধারণ ট্রি ইমপ্লিমেন্টেশন দেখানো হল, যেখানে একটি স্ট্রিং ইনসার্ট এবং অনুসন্ধান করা হয়েছে:

class TrieNode {
    TrieNode[] children = new TrieNode[26]; // A to Z letters
    boolean isEndOfWord = false;

    public TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = null;
        }
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Insert a word into the Trie
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a'; // Find the index for the character
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word in the Trie
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

    // Starts with prefix
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");

        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("app")); // true
        System.out.println(trie.search("appl")); // false
        System.out.println(trie.startsWith("app")); // true
    }
}

ব্যাখ্যা:

1. insert(): একটি শব্দ ট্রিতে ইনসার্ট করে।
2. search(): একটি শব্দ ট্রিতে আছে কি না তা চেক করে।
3. startsWith(): একটি প্রিফিক্স ট্রিতে আছে কি না তা চেক করে।

সারাংশ

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