🥚 🛀🏾 🧒 अहो-कोरसिक एल्गोरिथ्म की गलत व्याख्या 🏢 🤶 🤠

दूर में (या शायद बहुत दूर नहीं) 1975 अल्फ्रेड अहो और मार्गरेट कोरैसिक ने एक लेख प्रकाशित किया जिसमें एक दिए गए स्ट्रिंग में सभी नमूना तार के सभी घटनाओं के लिए प्रभावी खोज के लिए एल्गोरिथ्म का विस्तार से वर्णन किया गया है। भविष्य में, इस एल्गोरिथ्म को "अहो-कोरसिक एल्गोरिथ्म" कहा जाता था। यह आश्चर्य की बात नहीं है कि कुछ समय बाद रूसी में इस लेख के तकनीकी और "कलात्मक" अनुवाद दिखाई दिए। कभी-कभी मैं उस एल्गोरिथ्म के सार के मुक्त विस्तार में भी आया था जिसमें लेखक इसे समझता है। इसके अलावा, उत्तरार्द्ध, पाठ को देखते हुए, मूल स्रोत से दूर एल्गोरिथ्म के बारे में पता चला। मुझे नहीं पता कि क्या कोई अनुवाद था जो समस्या के प्राथमिक स्रोत के रूप में कार्य करता था, लेकिन अधिक से अधिक मैं अहो-कोरसिक एल्गोरिथ्म के वर्णन के साथ लेखों में आता हूं, जिसमें एक ही कार्डिनल त्रुटि हुई थी। अंतिम पुआल एक हब पर उपयोगकर्ता rmq का लेख था, जो यह त्रुटि पास नहीं हुई थी। दरअसल, मैं अपने लेख में इस गलती के बारे में जनता को बताना चाहूंगा।
नोट: rmq उपयोगकर्ता लेख , जैसा कि यह बाद में निकला, इसमें यह त्रुटि नहीं है। यह कैसे हल किया जाता है मैं नीचे बताऊंगा। और उसके लिए बहुत धन्यवाद, अगर उसके विषय के लिए नहीं, तो मैंने अपना खुद का लिखा नहीं होता और मुझे निमंत्रण नहीं दिया होता!
शुरू करने से पहले, लक्षित दर्शकों के बारे में कुछ शब्द: सबसे अधिक संभावना है, जो लंबे समय से अहो-कोरसिक एल्गोरिथ्म से परिचित हैं, वे मेरे लेख में दिलचस्पी नहीं लेंगे, क्योंकि वे लंबे समय से इसकी विशेषताओं के बारे में जानते हैं। कम से कम, मेरे सभी परिचित प्रोग्रामर एक से अधिक बार इस एल्गोरिथ्म का उपयोग करके इसकी गलत व्याख्याओं के अस्तित्व के बारे में जानते हैं। लेकिन शुरुआती लोगों के लिए और जो अक्सर अभ्यास में इसका उपयोग नहीं कर पाए हैं, उनके लिए यह लेख काफी उपयोगी हो सकता है।
तो चलो शुरू करते हैं।

पाठकों का समय बर्बाद न करने के लिए, मैं एल्गोरिथ्म का एक विस्तृत विवरण याद करूंगा (यह मूल लेख में पढ़ा जा सकता है) और उदाहरणों और एक तस्वीर के साथ शुरू करें ताकि जल्दी से शर्तों पर जा सकें और आगे "एक भाषा में" बात कर सकें।
आइए हम नमूना स्ट्रिंग्स की निम्न सूची देखें: {"HE", "SHE", "HIS", "HER"}। सबसे पहले, हमें एक ऑटोमेटन बनाने की आवश्यकता है। राज्यों और संक्रमणों के साथ बहुत परिमित राज्य मशीन, जिसके आधार पर अहो-कोरसिक एल्गोरिथ्म का निर्माण किया जाता है। ब्लैक सर्कल ऑटोमेटन की प्रारंभिक स्थिति को इंगित करता है। ब्लू सर्कल ऑटोमोटन की अगली स्थिति का संकेत देंगे, जिनमें से उपलब्धि नमूना स्ट्रिंग का पता लगाने के तथ्य का मतलब नहीं है। और अंत में, एक क्रॉसहेयर के साथ नीले घेरे - यह मशीन की अगली स्थिति है, जिसकी उपलब्धि का मतलब लाइन-पैटर्न का पता लगाने का तथ्य है। स्वाभाविक रूप से, उनके बीच संक्रमण फैलता है - अक्षरों के साथ हस्ताक्षरित काले तीर, जो संक्रमण के लिए स्थिति हैं। हम उन्हें मुख्य बदलाव कहेंगे। यदि अगले इनपुट प्रतीक के लिए कोई मुख्य संक्रमण नहीं है, तो मशीन अपनी प्रारंभिक स्थिति में जाती है। हम उन्हें शून्य संक्रमण कहते हैं। मैं इन बदलावों को विशेष रूप से इंगित नहीं करता हूं, ताकि तस्वीर को अव्यवस्थित न करें। शून्य संक्रमण के बारे में, यह ध्यान देने योग्य है कि जब आप उन पर क्लिक करते हैं, तो इनपुट प्रतीक अवशोषित नहीं होता है, अर्थात यह इनपुट लाइन में रहता है और संक्रमण के बाद फिर से उपयोग किया जाएगा। अपवाद प्रारंभिक अवस्था से शून्य संक्रमण है, जहां, वास्तव में, राज्य नहीं बदलता है, और इनपुट प्रतीक अवशोषित होता है।

आकृति एक क्रॉसहेयर के साथ चार नीले घेरे दिखाती है, जिनमें से प्रत्येक नमूने की एक पंक्ति से मेल खाती है। वास्तव में, यह बहुत ही त्रुटि इस उदाहरण में पहले से ही अंतर्निहित है। मूल एल्गोरिथ्म ऑटोमेटन को थोड़ा अलग तरीके से वर्णन करता है। लेकिन सबसे पहली बात।
तथाकथित प्रत्यय लिंक को याद करें। ये संक्रमण हैं जो इंगित करते हैं कि इनपुट लाइन के अगले चरित्र के लिए मुख्य संक्रमण न होने पर किस स्थिति में स्विच किया जाए। निम्नलिखित आकृति में, उन्हें बिंदीदार काले तीर द्वारा इंगित किया गया है। हम उन्हें प्रत्यय संक्रमण या प्रत्यय लिंक कहेंगे। एक शून्य संक्रमण के साथ सादृश्य द्वारा प्रत्यय लिंक से गुजरना, इनपुट चरित्र को अवशोषित नहीं करता है। जैसा कि पहले मामले में, मैं मुख्य संक्रमण की अनुपस्थिति में प्रारंभिक अवस्था के लिए संक्रमण का चित्रण नहीं करता हूं।

प्रत्यय लिंक के बिना उदाहरण में, लेकिन शून्य बदलाव के साथ, सभी घटनाएं ("HE", "HER", "HE", "HIS") "HERHEHIS" लाइन में मिल जाएंगी। लेकिन इनपुट स्ट्रिंग "HISHER" में केवल तीन प्रविष्टियाँ ही मिलेंगी ("HIS", "HE", "HER") और मशीन पैटर्न स्ट्रिंग "SHE" की घटना का पता नहीं लगाएगी, जिसे सत्यापित करना आसान है। स्ट्रिंग "HERHEHIS" के लिए प्रत्यय लिंक के मामले में परिणाम समान होगा, और स्ट्रिंग "HISHER" के लिए परिणाम चार पाया प्रविष्टियों की एक सूची होगी: ("HIS", "SHE", "HE HE," HER ")। यही है, बाद के मामले में, सभी घटनाएं पाई गईं। नहीं, नहीं, यह वह गलती नहीं है जिसके बारे में मैं बात करना चाहता था। किसी भी मामले में ऐसा मत सोचो। किसी को प्रत्यय लिंक के बारे में भूल जाने के लिए, मैंने ऐसा पहले नहीं देखा है। अभी भी आना है।
मैंने एक ऑटोमेटन के निर्माण के लिए एल्गोरिथ्म का विस्तार से वर्णन करना शुरू नहीं किया, लेकिन हम ऊपर वर्णित मामलों के लिए खोज एल्गोरिथ्म पर अधिक विस्तार से विचार करेंगे। ऐसा करने के लिए, सुविधा के लिए, हम पहले प्रत्यय लिंक के बिना एक ऑटोमेटन देंगे, जिसमें हम इसके राज्यों (संबंधित हलकों के पास नीले नंबर) को नंबर देते हैं।

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

0 H -> 1 ERHEHIS 1 E -> 2 RHEHIS (“HE”) 2 R -> 3 HEHIS (“HER”) 3 H -> 0 HEHIS //  ,         0 H -> 1 EHIS 1 E -> 2 HIS (“HE”) 2 H -> 0 HIS //    0 H -> 1 IS 1 I -> 7 S 7 S -> 8 (“HIS”)

यहाँ वे हैं - सभी चार घटनाएँ। अब "HISHER" लाइन के साथ भी ऐसा ही करें:

 0 H -> 1 ISHER 1 I -> 7 SHER 7 S -> 8 HER (“HIS”) 8 H -> 0 HER 0 H -> 1 ER 1 E -> 2 R (“HE”) 2 R -> 3 (“HER”)

जैसी कि उम्मीद थी, केवल तीन घटनाएं हुईं। अब आप उदाहरणों के सार में तल्लीन कर सकते हैं और निम्नलिखित कथन तैयार कर सकते हैं: "सभी आवृत्तियों को मशीन में बिना प्रत्यय के नमूना स्ट्रिंग के अतिव्यापी लिंक के बिना मशीन में नहीं मिलेगा।" हम "HISHE" में ओवरलैपिंग ("HIS" और "SHE") के बारे में बात कर रहे हैं, लेकिन एक दूसरे ("HE" और "HER" को "HER") में दर्ज नहीं कर रहे हैं।
प्रत्यय लिंक वाली मशीन में, निश्चित रूप से, ऐसा नहीं होता है। आइए उन्हीं उदाहरणों पर जांच करते हैं। हम प्रत्यय के राज्यों की संख्या प्रत्यय लिंक के साथ रखते हैं:

इनपुट स्ट्रिंग "HERHEHIS" लें:

 0 H -> 1 ERHEHIS 1 E -> 2 RHEHIS (“HE”) 2 R -> 3 HEHIS (“HER”) 3 H -> 0 HEHIS //      0 H -> 1 EHIS 1 E -> 2 HIS (“HE”) 2 H -> 0 HIS //      0 H -> 1 IS 1 I -> 7 S 7 S -> 8 (“HIS”)

इस इनपुट लाइन के लिए, मशीन की प्रगति ठीक उसी तरह है जैसे मशीन के लिए प्रत्यय लिंक के बिना। अब मशीन पर "HISHER" लाइन खिसकाएँ:

 0 H -> 1 ISHER 1 I -> 7 SHER 7 S -> 8 HER (“HIS”) 8 H -> 4 HER //    4 H -> 5 ER 5 E -> 6 R (“SHE”) 6 R -> 2 R (“HE”) //    2 R -> 3 (“HER”)

वास्तव में, सभी चार घटनाओं की खोज की गई थी। यहां क्या तैयार किया जा सकता है: "प्रत्यय लिंक के बिना, नमूना तार के सभी घटनाओं को खोजने की आशा शून्य हो जाती है।"
अक्सर मुझे अहो-कोरसिक एल्गोरिथ्म का वर्णन आता था, जो इस पर बिल्कुल समाप्त हुआ। पेड़ के निर्माण के लिए एल्गोरिथ्म को विस्तार से लिखा गया था, और यह खोज एल्गोरिथ्म के बारे में लिखा गया था: "यह प्राथमिक है - हम राज्यों के माध्यम से जाते हैं और परिणाम देते हैं।" और इन कार्यों के लेखक बिल्कुल सही होंगे यदि उन्हें गलत नहीं किया गया था। के साथ शुरू करने के लिए, मैं एक उदाहरण दिखाऊंगा कि प्रत्यय लिंक के साथ एक ऑटोमेटन भी नहीं संभाल सकता है। हम एक समान ऑटोमेटन का निर्माण करेंगे, लेकिन इसमें दो अतिरिक्त नमूना स्ट्रिंग्स पेश करेंगे: "I" और "IS"। योजनाबद्ध रूप से, इस तरह के एक ऑटोमेटन को इसके मुख्य और प्रत्यय संक्रमणों के रूप में दर्शाया जा सकता है:

एक इनपुट लाइन के रूप में हम अपने लिए जाने जाने वाले सभी “HISHER” को लेते हैं। तो, चलिए चलते हैं:

 0 H -> 1 ISHER 1 I -> 7 SHER 7 S -> 8 HER (“HIS”) 8 H -> 10 HER (“IS”) 10 H -> 4 HER 4 H -> 5 ER 5 E -> 6 R (“SHE”) 6 R -> 2 R (“HE”) 2 R -> 3 (“HER”)

कुल मिलाकर, हमारे पास पाँच घटनाएं हैं। लेकिन उनमें से कोई पैटर्न स्ट्रिंग "I" नहीं है। मामला क्या है? यह कैसे हुआ? वास्तव में, सब कुछ प्राथमिक है। प्रत्यय लिंक का अनुसरण करते समय, हमने राज्य 9 पास किया, जिसे हम केवल 7 और 0. राज्यों से देख सकते थे, इसलिए जहां भी कोई विकल्प "HIS" है, नमूना स्ट्रिंग "I" नहीं मिलेगा। इसी प्रकार, इनपुट लाइन "HISHER" में, हम केवल एक बार नमूना स्ट्रिंग "H" ढूंढेंगे, जो पहले इसे सूची में जोड़ा गया था और संबंधित ऑटोमेटन का निर्माण किया था। और यहाँ बिंदु यह नहीं है कि लाइनें "I" और "H" एक वर्ण से मिलकर बनती हैं। अपने लिए जाँच करें: सूची में "HIS" के साथ "HIS", "IS" को "IPS", "I" के साथ "IP" से बदलें, और मशीन को इनपुट लाइन "HIPSHER" को खिलाएं। पैटर्न स्ट्रिंग "आईपी" समान कारणों से नहीं मिलेगा। तो क्या गलत था: ऑटोमेटन की संरचना या खोज एल्गोरिदम?
इस समस्या को हल करने के विकल्पों में एक स्पष्ट पसंदीदा है। इसी तरह के उदाहरण के साथ सामना किया और कारण को सुलझाते हुए, डेवलपर्स सबसे स्पष्ट ललाट समाधान चुनते हैं: "प्रत्यय लिंक के माध्यम से जाने के बाद, प्रारंभिक अवस्था में मुख्य संक्रमणों के माध्यम से वापस जाएं"। वास्तव में, यह हमें समस्या से बचाता है, और इस तरह के कार्यान्वयन से जीवन का अधिकार है। यहां केवल दो नोट किए जा सकते हैं:

एल्गोरिथ्म की जटिलता (इसके समय की लागत) का आकलन बदतर के लिए बदल रहा है;
वास्तव में कोई समस्या नहीं थी।

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

राज्य 6 पर पहुंचने पर, हम "SHE" और "HE" की घटनाओं को ठीक करते हैं। यह 6 राज्य पर है, और प्रत्यय लिंक का अनुसरण करने के बाद नहीं। इसी तरह, राज्य 7 पैटर्न स्ट्रिंग "I" और राज्य 8 - "HIS" और "IS" की घटना को दर्ज करेगा। इस मामले में, खोज एल्गोरिथ्म को प्रत्यय लिंक का अनुसरण करने के बाद प्रविष्टि के निर्धारण को हटाना होगा, अन्यथा उसी प्रविष्टि को दो बार तय किया जाएगा। उदाहरण के लिए, 6 राज्य से दूसरे राज्य में संक्रमण के बाद, "HE" की घटना को ठीक करने के लिए आवश्यक नहीं है; हमने 5 वें राज्य से 6 वें राज्य में संक्रमण के बाद पहले ऐसा किया था। अब प्रारंभिक अवस्था में किसी भी तरह के बैकट्रैक की जरूरत नहीं है। खोज वास्तव में सरल और सीधी है। इनपुट स्ट्रिंग "HISHER" को पार्स करना अब इस तरह दिखेगा:

 0 H -> 1 ISHER 1 I -> 7 SHER (“I”) 7 S -> 8 HER (“HIS”, “IS”) 8 H -> 10 HER 10 H -> 4 HER 4 H -> 5 ER 5 E -> 6 R (“SHE”, “HE”) 6 R -> 2 R 2 R -> 3 (“HER”)

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

अहो-कोरसिक एल्गोरिथ्म की गलत व्याख्या

More articles: