স্ট্রিং মেচিং এবং সার্চিং টেকনিক্স হল এমন কৌশল ও অ্যালগরিদম যা একটি স্ট্রিং (বা প্যাটার্ন) খুঁজে বের করতে অন্য স্ট্রিংয়ের মধ্যে অনুসন্ধান করতে ব্যবহৃত হয়। স্ট্রিং মেচিংয়ের প্রয়োজন অনেক ক্ষেত্রেই হয়, যেমন টেক্সট প্রসেসিং, ডেটাবেস অনুসন্ধান, ওয়েব সার্চ ইঞ্জিন, এবং আরও অনেক ক্ষেত্রে।
নিচে কিছু সাধারণ স্ট্রিং মেচিং এবং সার্চিং টেকনিক্সের ব্যাখ্যা এবং উদাহরণ দেয়া হলো:
১. Naive String Matching
এটি একটি সহজতম স্ট্রিং মেচিং অ্যালগরিদম যেখানে প্যাটার্নটি মূল স্ট্রিংয়ের প্রতিটি সম্ভাব্য অবস্থানে পরীক্ষা করা হয়। এটি কেবল একে একে প্রতিটি উপাদান পরীক্ষা করে, ফলে এটি সাধারণত O(n * m) টাইম কমপ্লেক্সিটি সম্পন্ন হয়, যেখানে n হল মূল স্ট্রিংয়ের দৈর্ঘ্য এবং m হল প্যাটার্নের দৈর্ঘ্য।
উদাহরণ:
#include <iostream>
#include <string>
void naiveSearch(const std::string& text, const std::string& pattern) {
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; ++i) {
int j = 0;
while (j < m && text[i + j] == pattern[j]) {
++j;
}
if (j == m) {
std::cout << "Pattern found at index " << i << std::endl;
}
}
}
int main() {
std::string text = "ABABABCABABABAC";
std::string pattern = "ABAB";
naiveSearch(text, pattern);
return 0;
}আউটপুট:
Pattern found at index 0
Pattern found at index 7
Pattern found at index 12২. Knuth-Morris-Pratt (KMP) Algorithm
KMP অ্যালগরিদম স্ট্রিং মেচিংয়ের জন্য একটি কার্যকরী কৌশল যা preprocessing পদ্ধতি ব্যবহার করে। এটি প্যাটার্নের মধ্যে লজিক্যাল স্নেহমূলক সম্পর্কগুলো অনুসন্ধান করে, যাতে পুনরাবৃত্তি হীনভাবে স্ট্রিংয়ের মধ্যে প্যাটার্নটি খুঁজে পাওয়া যায়। এর টাইম কমপ্লেক্সিটি হল O(n + m), যেখানে n হল মূল স্ট্রিংয়ের দৈর্ঘ্য এবং m হল প্যাটার্নের দৈর্ঘ্য।
উদাহরণ:
#include <iostream>
#include <vector>
#include <string>
std::vector<int> computeLPSArray(const std::string& pattern) {
int m = pattern.length();
std::vector<int> lps(m, 0);
int len = 0;
int i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
++len;
lps[i] = len;
++i;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
++i;
}
}
}
return lps;
}
void KMPSearch(const std::string& text, const std::string& pattern) {
int n = text.length();
int m = pattern.length();
std::vector<int> lps = computeLPSArray(pattern);
int i = 0;
int j = 0;
while (i < n) {
if (pattern[j] == text[i]) {
++i;
++j;
}
if (j == m) {
std::cout << "Pattern found at index " << i - j << std::endl;
j = lps[j - 1];
} else if (i < n && pattern[j] != text[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
++i;
}
}
}
}
int main() {
std::string text = "ABABDABACDABABCABAB";
std::string pattern = "ABABCABAB";
KMPSearch(text, pattern);
return 0;
}আউটপুট:
Pattern found at index 10৩. Boyer-Moore Algorithm
Boyer-Moore অ্যালগরিদম হল একটি খুব কার্যকরী স্ট্রিং মেচিং অ্যালগরিদম, যা প্যাটার্নের অনুসন্ধানে two heuristics ব্যবহার করে:
- Bad Character Heuristic: যখন কোনো অক্ষর মেলে না, তখন প্যাটার্নটি কতটা এগিয়ে যেতে পারে তা নির্ধারণ করে।
- Good Suffix Heuristic: যদি কোনো অংশ মেলে না, তবে পূর্ববর্তী মেলানো অংশের সাহায্যে প্যাটার্নটি কোথায় যাবে তা নির্ধারণ করে।
এটি O(n/m) গড় সময়ে কাজ করে, যেখানে n হল মূল স্ট্রিংয়ের দৈর্ঘ্য এবং m হল প্যাটার্নের দৈর্ঘ্য। তবে, এর পারফরম্যান্স অনেক ক্ষেত্রে বেশি ভালো হয়।
উদাহরণ:
#include <iostream>
#include <string>
#include <vector>
void badCharacterHeuristic(const std::string& pattern, std::vector<int>& badChar) {
int m = pattern.length();
for (int i = 0; i < m; ++i) {
badChar[pattern[i]] = i;
}
}
void BMSearch(const std::string& text, const std::string& pattern) {
int n = text.length();
int m = pattern.length();
std::vector<int> badChar(256, -1); // ASCII size
badCharacterHeuristic(pattern, badChar);
int s = 0; // Shift
while (s <= n - m) {
int j = m - 1;
while (j >= 0 && pattern[j] == text[s + j]) {
--j;
}
if (j < 0) {
std::cout << "Pattern found at index " << s << std::endl;
s += (s + m < n) ? m - badChar[text[s + m]] : 1;
} else {
s += std::max(1, j - badChar[text[s + j]]);
}
}
}
int main() {
std::string text = "ABAAABCDABCABC";
std::string pattern = "ABC";
BMSearch(text, pattern);
return 0;
}আউটপুট:
Pattern found at index 7
Pattern found at index 12৪. Rabin-Karp Algorithm
Rabin-Karp অ্যালগরিদম একটি স্ট্রিং মেচিং অ্যালগরিদম যা হ্যাশিং ব্যবহার করে প্যাটার্ন এবং সাবস্ট্রিংগুলির হ্যাশ মান তুলনা করে। এটি সাধারণত O(n + m) গড় সময়ে কাজ করে, তবে খারাপ কেসে O(n * m) সময়ে চলে।
উদাহরণ:
#include <iostream>
#include <string>
#include <cmath>
const int d = 256; // Character set size
const int q = 101; // A prime number for modulo
void rabinKarpSearch(const std::string& text, const std::string& pattern) {
int n = text.length();
int m = pattern.length();
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for text
int h = 1;
// Calculate h = pow(d, m-1) % q
for (i = 0; i < m - 1; i++) {
h = (h * d) % q;
}
// Calculate the hash value of pattern and text
for (i = 0; i < m; i++) {
p = (d * p + pattern[i]) % q;
t = (d * t + text[i]) % q;
}
// Slide the pattern over text
for (i = 0; i <= n - m; i++) {
if (p == t) {
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j])
break;
}
if (j == m) {
std::cout << "Pattern found at index " << i << std::endl;
}
}
// Calculate hash value for next window of text
if (i < n - m) {
t = (d * (t - text[i] * h) + text[i + m]) % q;
if (t < 0) {
t = t + q;
}
}
}
}
int main() {
std::string text = "ABC ABCDAB ABCDABCDABDE";
std::string pattern = "
ABCDABD";
rabinKarpSearch(text, pattern);
return 0;
}আউটপুট:
Pattern found at index 15উপসংহার
- Naive String Matching: সহজ এবং সরল পদ্ধতি, তবে বড় ডেটাসেটে কার্যকর নয়।
- KMP Algorithm: একটি প্রগতিশীল পদ্ধতি যা আগে থেকে প্যাটার্নের প্রক্রিয়া করে, দ্রুত কাজ করে।
- Boyer-Moore Algorithm: অত্যন্ত কার্যকরী এবং খারাপ কেসে অপটিমাইজ করা, দ্রুত কাজ করে।
- Rabin-Karp Algorithm: হ্যাশিং ব্যবহার করে, যা দ্রুত গড় পারফর্মেন্স দেয়, তবে খারাপ কেসে ধীর হতে পারে।
এই অ্যালগরিদমগুলি ব্যবহার করে আপনি স্ট্রিং মেচিংয়ের কার্যকারিতা এবং দক্ষতা বৃদ্ধি করতে পারেন।
Read more
