Java Technologies ট্রাই (Trie) গাইড ও নোট

ট্রাই (Trie) বা প্যাটার্ন-ম্যাচিং ট্রি একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা সাধারণত স্ট্রিং বা ক্যরেক্টারের সেট (characters set) সঞ্চয় করার জন্য ব্যবহৃত হয়। এটি একটি নোড-ভিত্তিক ডেটা স্ট্রাকচার যা prefix-based অনুসন্ধান বা স্ট্রিংয়ের প্যাটার্ন মেলানোর জন্য খুবই কার্যকর। সাধারণত এটি ডিকশনারি বা শব্দের সেটগুলির মধ্যে দ্রুত অনুসন্ধান করতে ব্যবহৃত হয়।

1. ট্রাই (Trie) এর মৌলিক ধারণা

• Prefix Tree: ট্রাইকে "prefix tree" বা "prefix-based tree" বলা হয়, কারণ এটি স্ট্রিং বা শব্দের পূর্ববর্তী অংশে ভিত্তি করে তৈরি হয়।
• Node Structure: প্রতিটি নোডে একটি ক্যারেক্টার এবং একটি children নোডের তালিকা (children list) থাকে, যা স্ট্রিং এর পরবর্তী ক্যারেক্টারগুলিকে ধারণ করে।
• Root Node: ট্রাইতে একটি রুট নোড থাকে যা কোনও ক্যারেক্টার ধারণ করে না, এবং এটি সমস্ত স্ট্রিং এর শুরু থেকে ট্রাভার্স করা শুরু হয়।
• Efficiency: ট্রাই স্ট্রিং গুলির মধ্যে অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশনগুলির জন্য খুবই দক্ষ।

2. ট্রাই স্ট্রাকচারের বৈশিষ্ট্য

1. Prefix Matching: ট্রাই ব্যবহার করে স্ট্রিং এর prefix matching সহজে করা যায়। উদাহরণস্বরূপ, শব্দের তালিকায় "cat", "cap", "can" থাকলে, আপনি ট্রাইয়ের মাধ্যমে দ্রুত "ca" দিয়ে সমস্ত শব্দ খুঁজে পেতে পারেন।
2. নোড এর মধ্যে ক্যারেক্টার: প্রতিটি নোডে একটি নির্দিষ্ট ক্যারেক্টার থাকে, এবং নোডগুলির মধ্যে children অ্যারের মাধ্যমে প্যারেন্ট-চাইল্ড সম্পর্ক স্থাপন করা হয়।
3. ডুপ্লিকেট এন্ট্রি: ট্রাই ডুপ্লিকেট এন্ট্রি সংরক্ষণ করে না; এটি ক্যারেক্টার এবং তার prefixes অনুযায়ী শ্রেণিবদ্ধ থাকে।

3. ট্রাই স্ট্রাকচার তৈরি (Java)

ট্রাই স্ট্রাকচারের কাস্টম ক্লাস তৈরি:

প্রথমে একটি ট্রাই ক্লাস তৈরি করি, যাতে স্ট্রিং সংযোজন, অনুসন্ধান এবং ডিলিট করা যায়।

import java.util.HashMap;

class TrieNode {
    // A map to store child nodes
    HashMap<Character, TrieNode> children;
    // A boolean to mark the end of a word
    boolean isEndOfWord;

    // Constructor to initialize TrieNode
    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

    // Constructor to initialize the Trie
    public Trie() {
        root = new TrieNode();
    }

    // Insert a word into the Trie
    public void insert(String word) {
        TrieNode currentNode = root;

        for (char c : word.toCharArray()) {
            currentNode.children.putIfAbsent(c, new TrieNode());
            currentNode = currentNode.children.get(c);
        }

        currentNode.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word in the Trie
    public boolean search(String word) {
        TrieNode currentNode = root;

        for (char c : word.toCharArray()) {
            if (!currentNode.children.containsKey(c)) {
                return false; // Word not found
            }
            currentNode = currentNode.children.get(c);
        }

        return currentNode.isEndOfWord; // Check if it's the end of the word
    }

    // Delete a word from the Trie
    public boolean delete(String word) {
        return deleteRec(root, word, 0);
    }

    private boolean deleteRec(TrieNode currentNode, String word, int index) {
        if (index == word.length()) {
            if (!currentNode.isEndOfWord) {
                return false; // Word not found
            }
            currentNode.isEndOfWord = false;
            return currentNode.children.isEmpty(); // If no more children, return true
        }

        char ch = word.charAt(index);
        TrieNode node = currentNode.children.get(ch);
        if (node == null) {
            return false; // Word not found
        }

        boolean canDeleteCurrentNode = deleteRec(node, word, index + 1);

        // If true is returned, delete the mapping of character and node
        if (canDeleteCurrentNode) {
            currentNode.children.remove(ch);
            return currentNode.children.isEmpty() && !currentNode.isEndOfWord;
        }

        return false;
    }

    // Print all words in the Trie
    public void printWords() {
        printWordsRec(root, "");
    }

    private void printWordsRec(TrieNode currentNode, String word) {
        if (currentNode.isEndOfWord) {
            System.out.println(word);
        }

        for (Character c : currentNode.children.keySet()) {
            printWordsRec(currentNode.children.get(c), word + c);
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();

        // Insert words into the trie
        trie.insert("apple");
        trie.insert("app");
        trie.insert("banana");

        // Search words
        System.out.println("Searching for 'apple': " + trie.search("apple"));
        System.out.println("Searching for 'app': " + trie.search("app"));
        System.out.println("Searching for 'bat': " + trie.search("bat"));

        // Delete word and search again
        System.out.println("Deleting 'app': " + trie.delete("app"));
        System.out.println("Searching for 'app' after deletion: " + trie.search("app"));

        // Print all words in the trie
        System.out.println("Words in the Trie:");
        trie.printWords();
    }
}

4. ব্যাখ্যা

• TrieNode ক্লাস: এটি ট্রাইয়ের একটি নোড যা children (একটি HashMap) ধারণ করে এবং isEndOfWord নামে একটি বুলিয়ান ফিল্ড ধারণ করে, যা ইঙ্গিত দেয় যে এই নোডটি কোনো শব্দের শেষ কিনা।
• insert() পদ্ধতি: একটি শব্দ ট্রাইতে যোগ করার জন্য এটি প্রতিটি চরিত্রের জন্য একটি নতুন নোড তৈরি করে, যদি সেই চরিত্রটি পূর্বে না থাকে।
• search() পদ্ধতি: এটি চেক করে যে একটি নির্দিষ্ট শব্দ ট্রাইতে রয়েছে কিনা।
• delete() পদ্ধতি: এটি একটি নির্দিষ্ট শব্দ ট্রাই থেকে মুছে ফেলতে সহায়ক। এই প্রক্রিয়া রিকার্সিভভাবে কাজ করে এবং যদি কোনো নোডে আর কোনো শব্দ না থাকে তবে সেটি সরিয়ে দেয়।
• printWords() পদ্ধতি: এটি ট্রাই থেকে সমস্ত শব্দ প্রিন্ট করতে ব্যবহার করা হয়।

আউটপুট:

Searching for 'apple': true
Searching for 'app': true
Searching for 'bat': false
Deleting 'app': true
Searching for 'app' after deletion: false
Words in the Trie:
apple
banana

5. ট্রাই এর প্রধান বৈশিষ্ট্যসমূহ

1. Prefix Matching: ট্রাই স্ট্রিংয়ের prefix অনুসন্ধান দ্রুত করতে সহায়ক। এটি একটি শব্দের পুরো শব্দ বা তার অংশ খুঁজে বের করার জন্য খুবই কার্যকরী।
2. অত্যন্ত দ্রুত অনুসন্ধান: একটি স্ট্রিংয়ের সকল ক্যারেক্টারের জন্য একে একে পরীক্ষা করার পরিবর্তে, ট্রাই প্রতিটি চরিত্রের জন্য একটি নির্দিষ্ট নোডে চলে যায় এবং খুব দ্রুত একটি শব্দ খুঁজে পেতে সহায়ক।
3. কমপ্লেক্সিটিতে উন্নতি: অন্যান্য ডেটা স্ট্রাকচারের তুলনায়, যেমন অ্যারে বা লিঙ্কড লিস্ট, ট্রাই একটি স্ট্রিং অনুসন্ধান করার জন্য O(n) সময় জটিলতার সাথে কাজ করতে পারে যেখানে n হলো স্ট্রিংটির দৈর্ঘ্য।

6. ট্রাই এর ব্যবহারক্ষেত্র

1. Autocompletion: টেক্সট ইনপুট সিস্টেমে যেমন, গুগল সার্চ বা মোবাইল কিপ্যাডে স্বয়ংক্রিয় পূর্ণতা প্রস্তাব করার জন্য ট্রাই ব্যবহার করা হয়।
2. স্পেল চেকিং: ডিকশনারির শব্দ সন্নিবেশ করার জন্য ট্রাই ব্যবহৃত হয়, যেখানে দ্রুত শব্দ চেক করা সম্ভব হয়।
3. প্রিফিক্স অনুসন্ধান: অনেক ধরণের অনুসন্ধান এবং প্যাটার্ন ম্যাচিং সমস্যা ট্রাইয়ের সাহায্যে সমাধান করা যেতে পারে।

সারাংশ

ট্রাই (Trie) একটি শক্তিশালী ডেটা স্ট্রাকচার যা প্রধানত স্ট্রিং বা শব্দের সেটে কার্যকরীভাবে কাজ করে। এটি prefix matching, **spell

checking**, autocomplete, এবং pattern matching এর মতো সমস্যা সমাধানে খুবই কার্যকর। Java তে ট্রাই বাস্তবায়ন করতে, একটি TrieNode ক্লাসের মাধ্যমে চরিত্র এবং তাদের সম্পর্কিত নোডগুলি সংগঠিত করা হয়। ট্রাই এর অপারেশন যেমন insert, search, delete এবং prefix search দ্রুত এবং কার্যকরীভাবে কাজ করে।

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 হলো স্ট্রিংয়ের দৈর্ঘ্য, যা এটিকে স্ট্রিংয়ের সাথে সম্পর্কিত অপারেশনগুলোর জন্য অত্যন্ত কার্যকরী ডেটা স্ট্রাকচার তৈরি করে।

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

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

Trie এর কার্যপ্রণালী

ট্রাই ডাটা স্ট্রাকচারের প্রধান সুবিধা হলো:

• স্ট্রিং অনুসন্ধান: স্ট্রিং বা শব্দের মধ্যে দ্রুত অনুসন্ধান।
• কমন প্রিফিক্স সংরক্ষণ: ট্রাই একাধিক শব্দের কমন প্রিফিক্সের জন্য একটাই নোড ব্যবহার করে, যার ফলে মেমরি ব্যবহার কমে।
• প্রিফিক্স অনুসন্ধান: এটি প্রিফিক্স অনুসন্ধান করার জন্য খুবই কার্যকরী।

Trie এর কাঠামো

1. Root Node: ট্রাইয়ের মূল নোড, এটি কোনো শব্দ ধারণ করে না। এটি সব শব্দের জন্য একটি স্টার্টিং পয়েন্ট।
2. Child Node: প্রতিটি নোডের একটি বা একাধিক চাইল্ড নোড থাকতে পারে, এবং প্রতিটি চাইল্ড নোড একটি চরিত্র ধারণ করে।
3. Leaf Node: এটি এমন একটি নোড যা একটি সম্পূর্ণ শব্দ বা স্ট্রিং নির্দেশ করে।

Java তে Trie ইমপ্লিমেন্টেশন

ট্রাই ইমপ্লিমেন্টেশনের জন্য প্রথমে একটি TrieNode ক্লাস তৈরি করা হয়, যা প্রতিটি নোডের জন্য একটি চরিত্র এবং তার চাইল্ড নোডের লিস্ট ধারণ করবে। এরপর একটি Trie ক্লাস তৈরি করা হয় যা ট্রাই এর অপারেশন যেমন insert, search, এবং startsWith ইমপ্লিমেন্ট করবে।

১. TrieNode ক্লাস

class TrieNode {
    TrieNode[] children;  // চাইল্ড নোডের জন্য অ্যারে
    boolean isEndOfWord;  // এটি একটি পূর্ণ শব্দ কিনা

    // কন্সট্রাক্টর
    public TrieNode() {
        children = new TrieNode[26];  // ইংরেজি বর্ণমালার ২৬টি অক্ষর
        isEndOfWord = false;  // শুরুতে কোন শব্দ নেই
    }
}

২. Trie ক্লাস

public class Trie {
    private TrieNode root;

    // কন্সট্রাক্টর
    public Trie() {
        root = new TrieNode();  // ট্রাইয়ের মূল নোড তৈরি
    }

    // শব্দ ইনসার্ট করা
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';  // 'a' থেকে 'z' পর্যন্ত ইনডেক্স
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();  // নতুন নোড তৈরি
            }
            node = node.children[index];  // চাইল্ড নোডে যাওয়া
        }
        node.isEndOfWord = true;  // শব্দ শেষ হওয়া
    }

    // শব্দটি ট্রাই-এ আছে কিনা তা চেক করা
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;  // শব্দ পাওয়া যায়নি
            }
            node = node.children[index];
        }
        return node.isEndOfWord;  // যদি শব্দের শেষের নোড 'true' হয়, তবে শব্দটি ট্রাই-এ আছে
    }

    // কোনো শব্দের প্রিফিক্স রয়েছে কিনা তা চেক করা
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;  // প্রিফিক্স পাওয়া যায়নি
            }
            node = node.children[index];
        }
        return true;  // প্রিফিক্স পাওয়া গেছে
    }
}

৩. Main Method Example

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

        // শব্দটি খুঁজে পাওয়া
        System.out.println(trie.search("apple"));  // true
        System.out.println(trie.search("app"));    // true
        System.out.println(trie.search("banana")); // true
        System.out.println(trie.search("bat"));    // false

        // প্রিফিক্স চেক করা
        System.out.println(trie.startsWith("ban")); // true
        System.out.println(trie.startsWith("bana")); // true
        System.out.println(trie.startsWith("bat"));  // false
    }
}

আউটপুট:

true
true
true
false
true
true
false

সারাংশ

Trie (ট্রাই) একটি বিশেষ ধরনের ডাটা স্ট্রাকচার যা স্ট্রিং বা শব্দের স্টোরেজ এবং অনুসন্ধান সমাধানে খুবই কার্যকরী। এটি সাধারণত স্ট্রিংস, প্রিফিক্স অনুসন্ধান, ডিকশনারি তৈরি, এবং প্যাটার্ন ম্যাচিং এর জন্য ব্যবহৃত হয়। ট্রাইয়ে insert, search, এবং startsWith এর মতো অপারেশন দ্রুত কার্যকরভাবে সম্পন্ন হয়, এবং এটি সাধারণত নেটওয়ার্কিং, সার্চ ইঞ্জিন, অটো কমপ্লিট ফিচার এবং স্পেল চেকিং এর মতো অ্যাপ্লিকেশনে ব্যবহৃত হয়।

• TrieNode: এটি প্রতিটি নোডের জন্য একটি ক্লাস যা চরিত্র এবং চাইল্ড নোড ধারণ করে।
• Trie: এটি ট্রাই ডাটা স্ট্রাকচারটি পরিচালনা করে এবং এর অপারেশনগুলোর জন্য ফাংশন সরবরাহ করে।

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

String Searching এবং Autocomplete Features হল দুটি গুরুত্বপূর্ণ টেকনিক যা সাধারণত প্রোগ্রামিং, সার্চ ইঞ্জিন, এবং ইউজার ইনপুট প্রক্রিয়ায় ব্যবহৃত হয়। String Searching টেকনিক ব্যবহার করে একটি স্ট্রিংয়ের মধ্যে নির্দিষ্ট শব্দ বা প্যাটার্ন খোঁজা হয় এবং Autocomplete ফিচার ব্যবহার করে ব্যবহারকারীর ইনপুটের ভিত্তিতে প্রস্তাবিত শব্দ বা বাক্য সম্পূর্ণ করা হয়।

এখানে আমরা String Searching এবং Autocomplete Features নিয়ে আলোচনা করব এবং জাভাতে কীভাবে এগুলি বাস্তবায়িত করা যায়, তা দেখব।

১. String Searching

String Searching বা Pattern Matching একটি টেকনিক যা একটি স্ট্রিং (তথ্য) এর মধ্যে একটি নির্দিষ্ট প্যাটার্ন বা শব্দ খুঁজে বের করে। এর জন্য বেশ কিছু অ্যালগরিদম রয়েছে, যেমন:

1. Naive Search: একটি সহজ পদ্ধতি, যেখানে স্ট্রিংয়ের প্রতিটি পজিশনে প্যাটার্নটি মেলানো হয়।
2. KMP (Knuth-Morris-Pratt) Algorithm: এই অ্যালগরিদমটি স্ট্রিংয়ের মধ্যে দ্রুত প্যাটার্ন খুঁজে বের করার জন্য ডিজাইন করা হয়েছে।
3. Rabin-Karp Algorithm: হ্যাশিংয়ের ভিত্তিতে দ্রুত প্যাটার্ন খোঁজা যায়।
4. Boyer-Moore Algorithm: এটি আরও উন্নত প্যাটার্ন ম্যাচিং অ্যালগরিদম।

এখানে আমরা Naive String Searching এবং KMP Algorithm ব্যবহার করে স্ট্রিং সার্চিং দেখব।

উদাহরণ ১: Naive String Searching

public class NaiveStringSearch {
    public static int naiveSearch(String text, String pattern) {
        int m = pattern.length();
        int n = text.length();

        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i;  // Match found, return starting index
            }
        }
        return -1;  // No match found
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int result = naiveSearch(text, pattern);
        
        if (result != -1) {
            System.out.println("Pattern found at index: " + result);
        } else {
            System.out.println("Pattern not found.");
        }
    }
}

ব্যাখ্যা:

• Naive Search: এটি সহজভাবে প্রতিটি ইনডেক্স থেকে প্যাটার্নের সাথে তুলনা করে। যদি ম্যাচ হয়, তবে স্ট্রিংয়ের ইন্ডেক্স ফেরত দেয়।

আউটপুট:

Pattern found at index: 10

উদাহরণ ২: KMP Algorithm

public class KMPStringSearch {

    // Method to compute the Longest Prefix Suffix (LPS) array
    public static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // Method for KMP pattern matching
    public static int KMPSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPSArray(pattern);
        int i = 0;
        int j = 0;

        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                return i - j;  // Match found
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1;  // No match found
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int result = KMPSearch(text, pattern);

        if (result != -1) {
            System.out.println("Pattern found at index: " + result);
        } else {
            System.out.println("Pattern not found.");
        }
    }
}

ব্যাখ্যা:

• KMP Algorithm: এটি Prefix Function বা LPS (Longest Prefix Suffix) অ্যারে তৈরি করে যাতে গ্রন্থনা (matching) করার সময় পুনরায় তুলনা না করতে হয়। এটি মোটামুটি O(n + m) সময় জটিলতায় কাজ করে, যেখানে n হল টেক্সটের দৈর্ঘ্য এবং m হল প্যাটার্নের দৈর্ঘ্য।

আউটপুট:

Pattern found at index: 10

২. Autocomplete Features

Autocomplete ফিচারটি একটি টুল বা অ্যাপ্লিকেশন যা ব্যবহারকারী যেই ইনপুট দিচ্ছে, তার উপর ভিত্তি করে সম্ভাব্য সম্পূর্ণ শব্দ বা বাক্য প্রস্তাব করে। Autocomplete ফিচার সাধারণত Prefix Matching বা Pattern Matching পদ্ধতি ব্যবহার করে কাজ করে, যা একটি Trie Data Structure অথবা HashMap এর মাধ্যমে বাস্তবায়িত হয়।

উদাহরণ: Autocomplete using Trie Data Structure

Trie হল একটি বিশেষ ডেটা স্ট্রাকচার যা স্ট্রিং বা প্যাটার্নের জন্য খুবই উপযোগী। এটি স্ট্রিং অনুসন্ধানকে দ্রুত করে এবং অটোকমপ্লিটের মতো ফিচারগুলো সহজে বাস্তবায়ন করতে সাহায্য করে।

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

public class TrieAutocomplete {
    private TrieNode root;

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

    // Method to insert a word into the Trie
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    // Method to get suggestions for a given prefix
    public List<String> getSuggestions(String prefix) {
        TrieNode node = root;
        List<String> suggestions = new ArrayList<>();

        // Traverse through the Trie for the prefix
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return suggestions; // No suggestions found
            }
            node = node.children.get(c);
        }

        // Collect all words with the given prefix
        collectWords(node, prefix, suggestions);
        return suggestions;
    }

    // Helper method to collect words starting from a given TrieNode
    private void collectWords(TrieNode node, String prefix, List<String> suggestions) {
        if (node.isEndOfWord) {
            suggestions.add(prefix);
        }

        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            collectWords(entry.getValue(), prefix + entry.getKey(), suggestions);
        }
    }

    public static void main(String[] args) {
        TrieAutocomplete trie = new TrieAutocomplete();

        // Inserting words into the Trie
        trie.insert("apple");
        trie.insert("app");
        trie.insert("application");
        trie.insert("bat");
        trie.insert("ball");

        // Getting autocomplete suggestions for prefix "app"
        System.out.println("Suggestions for 'app': " + trie.getSuggestions("app"));
    }
}

ব্যাখ্যা:

• Trie Node: প্রতিটি TrieNode একটি মানচিত্র (map) ধারণ করে যা একটি চরিত্র (character) এবং তার পরবর্তী নোডের প্রতি নির্দেশ করে।
• Insert Method: একটি নতুন শব্দ (word) ইনসার্ট করার জন্য, প্রতিটি চরিত্র ট্রাইতে এক এক করে যুক্ত করা হয়।
• Autocomplete Method: ব্যবহারকারীর প্রিফিক্সের উপর ভিত্তি করে সম্ভাব্য শব্দগুলির তালিকা সংগ্রহ করা হয়।

আউটপুট:

Suggestions for 'app': [app, apple, application]

সারাংশ

String Searching এবং Autocomplete ফিচার দুটি গুরুত্বপূর্ণ টেকনিক যা ডেটা সঞ্চয় এবং অনুসন্ধানে ব্যাপকভাবে ব্যবহৃত হয়। String Searching প্যাটার্ন খোঁজার জন্য বিভিন্ন অ্যালগরিদম যেমন Naive Search, KMP, Rabin-Karp ইত্যাদি ব্যবহার করা হয়। অপরদিকে, Autocomplete ফিচার সাধারণত Trie Data Structure বা HashMap ব্যবহার করে বাস্তবায়িত করা হয়, যা দ্রুত ইনপুট অনুসন্ধান এবং প্রস্তাবনা দিতে সাহায্য করে।

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

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

Trie একটি শক্তিশালী ডাটা স্ট্রাকচার, যা স্ট্রিং সংক্রান্ত অপারেশনগুলিকে দ্রুত করতে সহায়তা করে। Trie তে প্রতিটি নোড একটি অক্ষর প্রতিনিধিত্ব করে এবং এটি স্ট্রিংয়ের প্রিফিক্স ভিত্তিক স্টোরেজ এবং অনুসন্ধান পরিচালনা করে।

এই টিউটোরিয়ালে আমরা Trie এর তিনটি মৌলিক অপারেশন - Insertion, Searching, এবং Deletion সম্পর্কে আলোচনা করব।

1. Trie Data Structure

Trie হল একটি বৃক্ষ (Tree) ভিত্তিক ডাটা স্ট্রাকচার যেখানে প্রতিটি নোড একটি অক্ষর প্রতিনিধিত্ব করে এবং স্ট্রিং সংরক্ষণের জন্য একটি কমপ্যাক্ট পদ্ধতি প্রস্তাব করে। এটি একটি Prefix Tree হিসাবে কাজ করে এবং একটি স্ট্রিংয়ের প্রতিটি অক্ষরকে একটি নির্দিষ্ট স্তরে সংরক্ষণ করে।

2. Trie Node Structure

একটি Trie Node সাধারণত দুটি প্রধান অংশে বিভক্ত:

• children: একটি ডেটা স্ট্রাকচার (যেমন, Map বা Array) যা বর্তমান নোডের পুত্র (children) প্রতিনিধিত্ব করে।
• isEndOfWord: একটি বুলিয়ান মান যা চিহ্নিত করে যে এই নোডটি একটি পূর্ণ স্ট্রিংয়ের শেষ নোড কিনা।

3. Insertion in Trie

Insertion অপারেশনটি একটি নতুন স্ট্রিং Trie তে যুক্ত করার জন্য ব্যবহৃত হয়। এই প্রক্রিয়াতে স্ট্রিংটির প্রতিটি অক্ষর Trie তে ইনসার্ট করা হয় এবং isEndOfWord ফ্ল্যাগটি সেই অক্ষরের জন্য true করা হয়, যদি তা স্ট্রিংয়ের শেষ হয়।

উদাহরণ: Insertion in Trie

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
        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++) {
            char ch = word.charAt(i);
            int index = ch - 'a';

            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;  // Mark the end of the word
    }

    // Display the Trie (optional)
    public void display() {
        displayHelper(root, "");
    }

    private void displayHelper(TrieNode node, String word) {
        if (node.isEndOfWord) {
            System.out.println(word);
        }
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                displayHelper(node.children[i], word + (char) (i + 'a'));
            }
        }
    }
}

public class TrieExample {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        trie.insert("banana");
        
        // Display the inserted words
        trie.display();
    }
}

ব্যাখ্যা:

1. Insertion: insert() ফাংশনে প্রতিটি অক্ষরকে TrieNode তে ইনসার্ট করা হয়। শেষের নোডে isEndOfWord true করা হয়, যা নির্দেশ করে যে এটি একটি পূর্ণ স্ট্রিং।
2. display(): এটি ট্রি ডেটা স্ট্রাকচারটি প্রদর্শন করার জন্য একটি সহায়ক ফাংশন।

আউটপুট:

apple
app
banana

4. Searching in Trie

Searching অপারেশনটি স্ট্রিংটি Trie তে উপস্থিত কিনা তা যাচাই করার জন্য ব্যবহৃত হয়। এটি স্ট্রিংটির প্রতিটি অক্ষরের জন্য চেক করে এবং শেষে isEndOfWord ফ্ল্যাগটি চেক করে।

উদাহরণ: Searching in Trie

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++) {
            char ch = word.charAt(i);
            int index = ch - 'a';

            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    // Search for a word in the Trie
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';

            if (node.children[index] == null) {
                return false;  // Word does not exist
            }
            node = node.children[index];
        }
        return node.isEndOfWord;  // Return true if it's the end of a word
    }
}

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

        System.out.println("Search for 'apple': " + trie.search("apple")); // true
        System.out.println("Search for 'app': " + trie.search("app")); // true
        System.out.println("Search for 'banana': " + trie.search("banana")); // false
    }
}

ব্যাখ্যা:

1. search(): এই ফাংশনটি একটি শব্দের প্রতিটি অক্ষরের জন্য ট্রি অনুসন্ধান করে এবং শেষের নোডে isEndOfWord চেক করে, যদি এটি true হয়, তবে স্ট্রিংটি পাওয়া গেছে।

আউটপুট:

Search for 'apple': true
Search for 'app': true
Search for 'banana': false

5. Deletion in Trie

Deletion অপারেশনটি একটি শব্দ Trie থেকে মুছে ফেলার জন্য ব্যবহৃত হয়। এটি একটি রিকার্সিভ অপারেশন, যেখানে আমরা প্রথমে শব্দটি খুঁজে বের করি এবং তারপর নোডগুলো থেকে প্রয়োজনীয় পরিবর্তন করি।

উদাহরণ: Deletion in Trie

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++) {
            char ch = word.charAt(i);
            int index = ch - 'a';

            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    // Delete a word from the Trie
    public boolean delete(String word) {
        return deleteHelper(root, word, 0);
    }

    private boolean deleteHelper(TrieNode node, String word, int index) {
        if (index == word.length()) {
            if (!node.isEndOfWord) {
                return false;  // Word does not exist
            }
            node.isEndOfWord = false;  // Unmark the end of word
            return node.childrenAreEmpty();  // Check if it can be deleted
        }

        char ch = word.charAt(index);
        int childIndex = ch - 'a';
        TrieNode childNode = node.children[childIndex];

        if (childNode == null) {
            return false;  // Word does not exist
        }

        boolean canDeleteCurrentNode = deleteHelper(childNode, word, index + 1);

        if (canDeleteCurrentNode) {
            node.children[childIndex] = null;  // Delete the reference to child
            return node.childrenAreEmpty() && !node.isEndOfWord;
        }
        return false;
    }

    // Utility function to check if a node has no children
    private boolean childrenAreEmpty() {
        for (TrieNode child : children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }
}

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

        System.out.println("Delete 'apple': " + trie.delete("apple")); // true
        System.out.println("Search for 'apple': " + trie.search("apple")); // false
    }
}

ব্যাখ্যা:

1. deleteHelper(): এটি রিকার্সিভভাবে শব্দটি মুছে ফেলে, এবং যখন সমস্ত অংশ মুছে ফেলা হয়ে যায়, তখন পুরনো নোড গুলি ধীরে ধীরে মুছে ফেলে দেওয়া হয়।
2. childrenAreEmpty(): এটি একটি সহায়ক ফাংশন যা চেক করে যে কোন নোডের কোনও শিশু নেই কি না।

আউটপুট:

Delete 'apple': true
Search for 'apple': false

সারাংশ

Trie একটি কার্যকরী ডাটা স্ট্রাকচার যা স্ট্রিং সংরক্ষণের জন্য ব্যবহৃত হয় এবং এটি স্ট্রিংয়ের প্রিফিক্স অনুসারে ডেটা প্রক্রিয়াকরণ করে। এতে তিনটি মৌলিক অপারেশন হল:

1. Insertion: স্ট্রিংটি Trie তে ইনসার্ট করা হয়।
2. Searching: Trie তে স্ট্রিংটি খোঁজা হয়।
3. Deletion: Trie থেকে স্ট্রিংটি মুছে ফেলা হয়।

Java তে Trie ব্যবহারের মাধ্যমে আমরা দ্রুত স্ট্রিং অনুসন্ধান এবং সংরক্ষণ করতে পারি, এবং এটি বিভিন্ন প্রোগ্রামিং সমস্যার সমাধানে অত্যন্ত কার্যকরী।