पाठ खोज एल्गोरिथ्म पाठ प्रसंस्करण और सूचना पुनर्प्राप्ति में एक मौलिक विधि है। यह एल्गोरिदम हमें पाठ के एक बड़े टुकड़े के भीतर एक सबस्ट्रिंग(या पैटर्न) की घटनाओं का पता लगाने और पहचानने की अनुमति देता है।
यह काम किस प्रकार करता है
- पाठ के एक बड़े टुकड़े(या दस्तावेज़) और खोजने के लिए एक सबस्ट्रिंग से प्रारंभ करें।
- पाठ के प्रत्येक अक्षर को क्रमिक रूप से दोहराएँ।
- सबस्ट्रिंग की तुलना पाठ के उस हिस्से से करें जिसकी लंबाई सबस्ट्रिंग के समान है। यदि कोई मेल मिलता है, तो वर्तमान स्थिति रिकॉर्ड करें।
- अगली स्थिति पर जाएँ और तुलना जारी रखें।
उदाहरण
पाठ पर विचार करें: "आइए इस पाठ के भीतर एक सबस्ट्रिंग खोजें और देखें कि एल्गोरिदम कैसे काम करता है।"
और खोजने के लिए सबस्ट्रिंग: "सबस्ट्रिंग"
- स्थिति 0 से प्रारंभ करें।
Let'
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 1 पर जाएँ।
et's
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 2 पर जाएँ।
t's
" सबस्ट्रिंग" के साथ तुलना करें। कोई मेल नहीं। - स्थिति 3 पर जाएँ।
's s
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 4 पर जाएँ।
se
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 5 पर जाएँ।
sea
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 6 पर जाएँ।
earc
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 7 पर जाएँ।
arch
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 8 पर जाएँ।
rch
" सबस्ट्रिंग" के साथ तुलना करें। कोई मेल नहीं। - स्थिति 9 पर जाएँ।
ch w
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 10 पर जाएँ।
h wi
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 11 पर जाएँ।
wit
" सबस्ट्रिंग" के साथ तुलना करें। कोई मेल नहीं। - स्थिति 12 पर जाएँ।
with
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 13 पर जाएँ।
ithi
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 14 पर जाएँ।
thin
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 15 पर जाएँ।
hinn
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 16 पर जाएँ।
in t
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 17 पर जाएँ।
n th
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 18 पर जाएँ।
thi
" सबस्ट्रिंग" के साथ तुलना करें। कोई मेल नहीं। - स्थिति 19 पर जाएँ।
this
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 20 पर जाएँ।
his
" सबस्ट्रिंग" के साथ तुलना करें। कोई मेल नहीं। - स्थिति 21 पर जाएँ।
is t
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 22 पर जाएँ।
s te
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 23 पर जाएँ।
ubst
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 24 पर जाएँ।
bstr
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 25 पर जाएँ।
stre
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 26 पर जाएँ।
trin
"सबस्ट्रिंग" से तुलना करें। कोई मुकाबला नहीं। - स्थिति 27 पर जाएँ।
ring
"सबस्ट्रिंग" से तुलना करें। मैच मिला, रिकॉर्ड स्थिति 27.
सबस्ट्रिंग "सबस्ट्रिंग" पाठ के भीतर 27वें स्थान पर पाई जाती है।
C++ में उदाहरण कोड
#include <iostream>
#include <string>
#include <vector>
std::vector<int> textSearch(const std::string& text, const std::string& query) {
std::vector<int> positions;
for(int i = 0; i <= text.length()- query.length(); ++i) {
int j = 0;
while(j < query.length() && text[i + j] == query[j]) {
++j;
}
if(j == query.length()) {
positions.push_back(i);
}
}
return positions;
}
int main() {
std::string text = "Let's search for a substring within this text to see how the algorithm works.";
std::string query = "substring";
std::vector<int> result = textSearch(text, query);
std::cout << "Substring found at positions: ";
for(int pos: result) {
std::cout << pos << ";
}
std::cout << std::endl;
return 0;
}
इस उदाहरण में, textSearch
फ़ंक्शन का उपयोग टेक्स्ट के भीतर सबस्ट्रिंग "सबस्ट्रिंग" की स्थिति खोजने के लिए किया जाता है। परिणाम एक वेक्टर होगा जिसमें मैचों की शुरुआती स्थिति शामिल होगी।