स्ट्रिंग खोज एल्गोरिदम

लाइन में खोज समस्या का विवरण

अक्सर आपको एक विशिष्ट खोज से निपटना पड़ता है, तथाकथित स्ट्रिंग खोज (एक स्ट्रिंग में खोज)। चलो कुछ पाठ टी और एक शब्द (या छवि) डब्ल्यू है। संकेतित पाठ में इस शब्द की पहली घटना को खोजना आवश्यक है। यह क्रिया किसी भी वर्ड प्रोसेसिंग सिस्टम की खासियत है। (सरणियों T और W के तत्व कुछ परिमित वर्णमाला के प्रतीक हैं - उदाहरण के लिए, {0, 1}, या {a, ..., z}, या {a, ..., i}।)।



इस तरह के कार्य का सबसे विशिष्ट अनुप्रयोग दस्तावेजी खोज है: दस्तावेजों का एक संग्रह जिसमें ग्रंथसूची संदर्भों के अनुक्रम होते हैं, प्रत्येक लिंक एक "विवरणक" के साथ होता है जो संबंधित लिंक के विषय को दर्शाता है। हमें विवरणकर्ताओं के बीच पाए जाने वाले कुछ कीवर्ड खोजने होंगे। उदाहरण के लिए, अनुरोध "प्रोग्रामिंग" और "जावा" हो सकता है। इस तरह के अनुरोध की व्याख्या इस प्रकार की जा सकती है: क्या वर्णनकर्ता "प्रोग्रामिंग" और "जावा" वाले लेख हैं।



एक स्ट्रिंग खोज को औपचारिक रूप से निम्नानुसार परिभाषित किया गया है। N तत्वों की एक सरणी T और 0 <M .N के साथ M तत्वों की एक सरणी W दी जाए। एक स्ट्रिंग खोज डब्ल्यू में टी की पहली घटना का पता लगाता है, परिणाम सूचकांक मैं है, छवि (शब्द) के साथ लाइन की शुरुआत (सरणी टी की शुरुआत से) से पहला मैच दर्शाता है।

एक उदाहरण है। पाठ T = abcabaabcabca में पैटर्न W = abaa की सभी घटनाओं को खोजना आवश्यक है।



नमूना को केवल एक बार पाठ में शामिल किया गया है, जिसमें S = 3, इंडेक्स i = 4 का बदलाव है।

प्रत्यक्ष खोज एल्गोरिथ्म

एल्गोरिथ्म का विचार:

1. मैं = 1,

2. सरणी T के पहले वर्ण के साथ सरणी T के I-th वर्ण की तुलना करें,

3. मैच → दूसरे पात्रों और इतने पर तुलना करें,

4. बेमेल → I: = I + 1 और बिंदु 2 पर जाएं,



एल्गोरिथ्म समाप्ति की स्थिति:

1. एक पंक्ति में एम तुलना सफल रहे हैं,

2. I + M> N, अर्थात शब्द नहीं मिला।



एल्गोरिथम जटिलता:

सबसे खराब मामला। एक सरणी T → {AAA ... .AAAB}, एक लंबाई │T N = N, एक नमूना W → {A ... .AB}, एक लंबाई │W│ = M। जाहिर है, लाइन के अंत में एक मैच खोजने के लिए, आपको एन * एम तुलना, यानी ओ (एन * एम) का एक आदेश बनाने की आवश्यकता है।



एल्गोरिथ्म के नुकसान:

1. उच्च जटिलता - ओ (एन * एम), सबसे खराब स्थिति में - (((एन-एम + 1) * एम);

2. एक मिसमैच के बाद, देखना हमेशा नमूने के पहले चरित्र से शुरू होता है और इसलिए इसमें टी अक्षर शामिल हो सकते हैं जो पहले देखे गए थे (यदि स्ट्रिंग को द्वितीयक मेमोरी से पढ़ा जाता है, तो ऐसे रिटर्न में बहुत समय लगता है);

3. इस शिफ्ट S की जाँच करके प्राप्त पाठ T के बारे में जानकारी किसी भी तरह से उपयोग नहीं की जाती है जब बाद की पाली की जाँच की जाती है।

डी। नुथ, डी। मौरिस और वी। प्रैट (केएमपी-खोज) का एल्गोरिथम

केएमपी खोज एल्गोरिदम को वास्तव में केवल एन तुलना के आदेश की आवश्यकता होती है यहां तक ​​कि सबसे खराब स्थिति में भी।

एक उदाहरण है।

(तुलना पात्रों को रेखांकित किया गया है।)





स्ट्रिंग T के संगत वर्णों के साथ छवि W के प्रारंभिक भाग के आंशिक संयोग के बाद, हम वास्तव में स्ट्रिंग के उत्तीर्ण भाग को जानते हैं और कुछ जानकारी (डब्ल्यू खुद की छवि के आधार पर) की "गणना" कर सकते हैं, जिसकी मदद से हम पाठ के माध्यम से जल्दी से आगे बढ़ेंगे।



केएमपी खोज का विचार यह है कि पाठ और छवि के दो पात्रों के बीच प्रत्येक बेमेल के साथ, छवि को पूरी दूरी की यात्रा द्वारा स्थानांतरित कर दिया जाता है, क्योंकि छोटी पारियों से पूर्ण मैच नहीं हो सकता है।



KMP खोज की विशेषताएं:

1. परिणाम प्राप्त करने के लिए (एन + एम) वर्ण तुलना की आवश्यकता होती है;

2. केएमपी-खोज योजना वास्तविक लाभ तभी देती है जब कुछ निश्चित संख्या में मैच असफलता से पहले होते हैं। केवल इस मामले में छवि एक से अधिक बदलाव करती है। दुर्भाग्य से, संयोग बेमेल से बहुत कम हैं। इसलिए, केएमपी खोज से ग्रंथों के अधिकांश मामलों में लाभ बहुत ही महत्वहीन है।

आर। बोवर और डी। मूर का एल्गोरिथ्म (बीएम खोज)

व्यवहार में, BM खोज एल्गोरिथ्म सबसे प्रभावी है यदि पैटर्न W लंबा है और वर्णमाला की शक्ति काफी बड़ी है।



BM खोज का विचार यह है कि वर्णों की तुलना पैटर्न के अंत से शुरू होती है, न कि शुरुआत से, अर्थात् व्यक्तिगत वर्णों की तुलना दाएं से बाएं होती है। फिर, एक निश्चित हेयुरिस्टिक प्रक्रिया का उपयोग करके, दाईं ओर की शिफ्ट की गणना की जाती है। फिर से, पैटर्न के अंत में पात्रों की तुलना शुरू की जाती है।



यह विधि न केवल सबसे खराब स्थिति से निपटने में सुधार करती है, बल्कि मध्यवर्ती स्थितियों में एक जीत भी देती है।

लगभग हमेशा, विशेष रूप से निर्मित उदाहरणों को छोड़कर, बीएम खोज को काफी कम एन तुलना की आवश्यकता होती है। सबसे अनुकूल परिस्थितियों में, जब नमूने का अंतिम वर्ण हमेशा पाठ के बेमेल चरित्र पर पड़ता है, तो तुलना की संख्या (N / M) होती है, सबसे खराब स्थिति में, O ((N-M + 1) * M + p), जहां p वर्णमाला की शक्ति है ।

राबिन-कार्प एल्गोरिथ्म (आरके-खोज)

वर्णमाला D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, अर्थात्, वर्णमाला में प्रत्येक वर्ण एक d - दशमलव अंक है, जहां d = │D│।



एक उदाहरण है। नमूने के पास W = 3 1 4 1 5 है

हम लंबाई की खिड़की से संख्याओं के मूल्यों की गणना करते हैं | W = = 5 के साथ mod q, q एक अभाज्य है।





23590 (मॉड 13) = 8, 35902 (मॉड 13) = 9, 59023 (मॉड 13) = 9, ...

k1 = 314157 (मॉड 13) - नमूने का प्रवेश,

k2 = 673997 (मॉड 13) - निष्क्रिय संचालन।



यह समानता ki = kj (mod q) से अनुसरण नहीं करता है कि ki = kj (उदाहरण के लिए, 31415 = 67399 (mod 13)), लेकिन इसका मतलब यह नहीं है कि 31415 = 67399)। यदि ki = kj (mod q), तो हमें अभी भी यह जांचने की आवश्यकता है कि क्या लाइनें W [1 ... m] और T [s + 1 ... s + m] वास्तव में मेल खाती हैं।

यदि प्राइम क्यू काफी बड़ा है, तो निष्क्रिय प्रतिक्रियाओं का विश्लेषण करने की अतिरिक्त लागत छोटी होगी।

सबसे खराब स्थिति में, आरके एल्गोरिथ्म का रनटाइम (((एन-एम + 1) * एम) है, औसतन, यह काफी तेजी से काम करता है - ओ (एन + एम) समय के दौरान।



उदाहरण: आरके एल्गोरिथ्म कितने रिक्त स्थान का निर्माण करेगा

q = 11, 13, 17. Let W = {2 6}



26 mod 11 = 4 → k = 3 निष्क्रिय यात्राएं,

26 mod 13 = 0 → k = 1 निष्क्रिय,

26 mod 17 = 9 → k = 0 निष्क्रिय समय।



स्पष्ट रूप से, ब्लैंक k की संख्या अभाज्य संख्या का एक फ़ंक्शन है (यदि नमूना प्रसंस्करण फ़ंक्शन mod q है) और, सामान्य स्थिति में, नमूना W और पाठ T को संसाधित करने के लिए फ़ंक्शन का प्रकार।