एक स्ट्रिंग में एक विकल्प खोजने के लिए Shift- या एल्गोरिथ्म का विवरण

1. प्रवेश के बदले।

हाल ही में, मुझे Shift- या एल्गोरिथ्म के संचालन को समझना था, जो हमें स्ट्रिंग में एक विकल्प खोजने की अनुमति देता है। इस विश्लेषण के परिणामों के आधार पर, मैंने इस पोस्ट को इस उम्मीद में लिखने का फैसला किया कि इससे किसी को यह समझने में मदद मिलेगी कि यह एल्गोरिथम कैसे काम करता है, मुझसे तेज।

दरअसल, एल्गोरिथ्म और मुख्य उदाहरण के बीच, "भोली तुलना", इस तथ्य में निहित है कि यह तार्किक संचालन पर आधारित है, अर्थात् तार्किक गुणन (उर्फ और उर्फ ​​संयोजन)।

2. एल्गोरिदम को काम करने के लिए क्या आवश्यक है।

पहले आपको कुछ संकेतन दर्ज करने की आवश्यकता है। हमें पी - यह वह नमूना होगा जिसे हम पाठ में देखेंगे, और टी - यह वास्तव में स्वयं पाठ है, जिसके द्वारा खोज होगी। P की लंबाई n है और T की लंबाई m है।

एल्गोरिथ्म में, एक निश्चित मैट्रिक्स एम का निर्माण किया जाता है (यह अभी भी स्पष्ट नहीं है कि यह कैसे बनता है)। यह मैट्रिक्स अनिवार्य रूप से केवल एक द्विआधारी सरणी है (केवल 0 और 1 के होते हैं)। M के आयाम nx (m + 1) हैं। इस मैट्रिक्स में, i-th इंडेक्स 1 से n तक के मानों से चलता है, और j-th इंडेक्स में 0 से m तक मान होता है। औपचारिक रूप से, "एक तत्व M (i, j) = 1 यदि और केवल यदि P का पहला i अक्षर T के i अक्षर से बिल्कुल मेल खाता है, तो स्थिति j पर समाप्त होती है"। तदनुसार, चूंकि सरणी बाइनरी है, अन्य सभी मामलों में तत्व 0. है। बेहतर यह समझने के लिए कि मैट्रिक्स एम क्या है, एक उदाहरण पर विचार करें:

पाठ को T = "CALIFORNIA" दें और हम इस पाठ में P = "FOR" के पैटर्न को खोजना चाहते हैं। (स्वाभाविक रूप से, इस तरह के एक संक्षिप्त "पाठ" उदाहरण की सादगी के लिए लिया जाता है)। हम देखते हैं कि "CALIFORNIA" पाठ में हमारे पास 10 वर्ण हैं, जिसका अर्थ है m = 10. नमूना P में हमारे 3 वर्ण हैं, इसलिए n = 3. तदनुसार, मैट्रिक्स M का आयाम 3x11 होगा। तो, हमें निम्न तालिका मिलती है:


आप यह भी देख सकते हैं कि हमारे लिए मुख्य बात केवल तालिका की अंतिम पंक्ति है। वास्तव में, इसमें केवल इकाइयाँ होती हैं, यदि पैटर्न P पूरी तरह से पाठ T में शामिल हो।

3. तो इस मैट्रिक्स एम का निर्माण कैसे किया जाता है?

इस तरह के मैट्रिक्स के निर्माण के कार्यक्रम के लिए, दो और संचालन शुरू किए जाने चाहिए।

3.1। बाइनरी वेक्टर यू (एक्स)।

यह वेक्टर केवल लंबाई n (पैटर्न P की तरह) का एक द्विआधारी स्ट्रिंग है, जिसमें समान पदों में इकाइयाँ हैं जहां अक्षर P पैटर्न P में है।
उदाहरण के लिए, हमारे पास P = "ABACDEAB" है। इसके लिए, वेक्टर यू (ए) = 10100010:

3.2। ऑपरेशन बिट-शिफ्ट (जे)

यह ऑपरेशन बाइनरी कॉलम j पर किया जाता है। यह बहुत सरल है और केवल कॉलम 1 स्थिति को नीचे स्थानांतरित करने और ऊपर से एक असाइन करने में शामिल है। स्तंभ की लंबाई नहीं बदलती है; तदनुसार, हम स्तंभ के अंतिम मान को खो देते हैं।
उदाहरण के लिए, हमारे पास 10: 0011010101 लंबाई का एक कॉलम है। हम बिट-शिफ्ट ऑपरेशन को तीन बार लागू करते हैं:

ऊपर दिए गए आंकड़े में, मूल स्तंभ से बने रहने वाले तत्वों को अंधेरे फ़िरोज़ा में हाइलाइट किया गया है, और बिट-शिफ्ट ऑपरेशन को लागू करने के परिणामस्वरूप जोड़ा गया है।

दरअसल, इन दो ऑपरेशनों को शुरू करने के बाद, सबसे सरल और महत्वपूर्ण हिस्सा बने रहे: मैट्रिक्स का निर्माण।
इसकी गणना बहुत सरलता से की जाती है। और मैं इस निर्माण पर विचार करने का प्रस्ताव करता हूं।
हमारे पास नमूना P = "ABAAC" (n = 5) और पाठ T = "XABXABAAXA" (m = 10) है।
प्रारंभ में, शून्य कॉलम को शून्य से भरें:

बाद के सभी स्तंभों की गणना पिछले एक के आधार पर की जाती है। फिर हम बिट-शिफ्ट ऑपरेशन को नल कॉलम पर लागू करते हैं। हमें स्तंभ मिलता है:

और हम कॉलम U (x) की गणना करते हैं। यहाँ "x" पाठ का पहला वर्ण है जिसे T की जाँच की जा रही है। हमें पूरी तरह से शून्य कॉलम मिलता है, क्योंकि P में अक्षर "x" नहीं होता है। फिर हम इन स्तंभों के लिए AND तार्किक गुणन ऑपरेशन लागू करते हैं:

अब तक, मैट्रिक्स M इस तरह दिखता है:

मैट्रिक्स में आगे भरना बिल्कुल समान है। दूसरे कॉलम के लिए, U (A) = 10110, और Bit-Shift (1) = 10000. तो दूसरा कॉलम, हम 10000 नंबर, आदि। प्रत्येक बाद का कॉलम पिछले एक के आधार पर भरा जाता है। मैट्रिक्स M के jth कॉलम को भरने का सामान्य सूत्र इस प्रकार है:

परिणामस्वरूप, सभी स्तंभों पर इस ऑपरेशन को करने के बाद, हमें एक तैयार मैट्रिक्स M प्राप्त होता है:

जैसा कि आप देख सकते हैं, हमारे पास T में P की पूर्ण घटना नहीं है, क्योंकि मैट्रिक्स की अंतिम पंक्ति में इकाइयां नहीं हैं। लेकिन फिर आंशिक प्रविष्टियां हैं (यदि हमें अचानक उनकी आवश्यकता है)।

4. निष्कर्ष के बजाय।

इस एल्गोरिथ्म की जटिलता हे (एमएन) है, जो सिद्धांत रूप में, इतनी छोटी नहीं है। लेकिन एल्गोरिथ्म में कुछ अच्छे पक्ष हैं। सबसे पहले, इसे लागू करना और यह समझना आसान है कि यह कैसे काम करता है। दूसरे, चूंकि मैट्रिक्स एम के प्रत्येक कॉलम की गणना पिछले एक के आधार पर की जाती है, हमें पूरे मैट्रिक्स को मेमोरी में स्टोर करने की आवश्यकता नहीं है, लेकिन यह केवल दो कॉलम रखने के लिए पर्याप्त है। व्यवहार में, एल्गोरिथ्म पी के छोटे नमूनों को खोजने का एक अच्छा काम करता है, जैसे कि, एक अंग्रेजी शब्द। इस एल्गोरिथ्म का थोड़ा संशोधित संस्करण यूनिक्स यूटिलिटी एग्रीप के काम को रेखांकित करता है जो पाठ में दिए गए कई त्रुटियों के साथ एक नमूना की तलाश करता है।

पुनश्च

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

संदर्भ।

1. डैन गैसफील्ड। एल्गोरिदम में लाइनें, पेड़ और क्रम। 2003।
2. बिटप
3. गूगल।