String Searching এবং Autocomplete Features গাইড ও নোট

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 ব্যবহার করে বাস্তবায়িত করা হয়, যা দ্রুত ইনপুট অনুসন্ধান এবং প্রস্তাবনা দিতে সাহায্য করে।

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