🎂 🧥 🏂 अहो-कोरसिक एल्गोरिथम 👩🏾‍🤝‍👩🏽 👩🏿‍🚀 👨🏿‍🍳

प्रविष्टि

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

प्रारंभिक विवरण

अहो-कोरसिक एल्गोरिथ्म एक दिए गए स्ट्रिंग में सभी नमूना तार के सभी घटनाओं के लिए एक प्रभावी खोज को लागू करता है। इसे 1975 में अल्फ्रेड अहो और मार्गरेट कोरासिक द्वारा विकसित किया गया था।
हम समस्या की स्थिति का औपचारिक रूप से वर्णन करते हैं। इनपुट कई लाइनों पैटर्न प्राप्त करता है [i] और लाइन s। हमारा कार्य पैटर्न की सभी संभावित घटनाओं को खोजना है [i] एस में तार।

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

नमूना तार के एक सेट पर बोरान निर्माण

बोरान की संरचना

बोरॉन क्या है? सख्ती से बोलना, बोरान एक पेड़ है जिसमें प्रत्येक शीर्ष एक पंक्ति को दर्शाता है (मूल एक शून्य पंक्ति - otes) को दर्शाता है। 1 अक्षर कोने के बीच किनारों पर लिखा गया है (यह प्रत्यय के पेड़ के साथ इसका मूलभूत अंतर है, आदि), इस प्रकार, जड़ के साथ किनारों से कुछ शीर्ष तक पहुंचने और ट्रैवर्सल क्रम में किनारों से अक्षरों को संवारना, हमें इस शीर्ष के अनुरूप एक रेखा मिलती है । एक पेड़ के रूप में बोरॉन की परिभाषा से, रूट और किसी भी शीर्ष के बीच के पथ की विशिष्टता भी अनुसरण करती है, इसलिए - बिल्कुल एक पंक्ति प्रत्येक शीर्ष से मेल खाती है (भविष्य में हम वर्टेक्स और उस रेखा की पहचान करेंगे जो इसे दर्शाता है)।
हम स्रोत लाइनों को जोड़कर क्रमिक रूप से बोरॉन का निर्माण करेंगे। प्रारंभ में, हमारे पास 1 शीर्ष है, मूल (रूट) एक खाली स्ट्रिंग है। एक पंक्ति जोड़ना इस तरह होता है: जड़ में शुरू, हम अपने पेड़ के साथ चलते हैं, प्रत्येक बार पंक्ति के अगले अक्षर के अनुरूप एक किनारे का चयन करते हैं। यदि ऐसा कोई किनारा नहीं है, तो हम इसे शीर्ष के साथ मिलकर बनाते हैं। यहाँ तार के लिए एक निर्मित बोरॉन का उदाहरण दिया गया है: 1) अकब, 2) एसीसी, 3) एसीएसी, 4) बाका, 5) एबीबी, 6) जेड, 7) एसी।

^{(चित्र १)}

पंक्ति 7 के जोड़ पर ध्यान दें। यह नए सिरे और किनारों को नहीं बनाता है, और इसे जोड़ने की प्रक्रिया आंतरिक शीर्ष पर रुकती है। इससे पता चलता है कि प्रत्येक पंक्ति के लिए अतिरिक्त रूप से यह संकेत देना आवश्यक है कि क्या यह स्थिति से एक रेखा है या नहीं (लाल वृत्त)।

^{(चित्र 2)}

हम यह भी ध्यान देते हैं कि एक बोर में दो पंक्तियों में सामान्य किनारे होते हैं, बशर्ते कि उनके पास एक सामान्य उपसर्ग हो। एक चरम मामला - जोड़े में नमूनों की सभी पंक्तियों में एक ही प्रारंभिक भाग नहीं है। तो बोर में कोने की संख्या के लिए ऊपरी सीमा सभी लाइनों + 1 (रूट) की लंबाई का योग है।

कार्यान्वयन

हम बोरॉन को वर्टिकल की एक सरणी के रूप में संग्रहीत करेंगे, जहां प्रत्येक शीर्ष की अपनी विशिष्ट संख्या होती है, और रूट का शून्य मान (मूल = 0) होता है। शीर्ष संरचना का संभावित विवरण:

//k -   struct bohr_vrtx{ int next_vrtx[k],pat_num; bool flag; };

next_vrtx [i] वह शीर्ष रेखा है, जिस वर्ण से हम वर्णमाला में संख्या i के साथ पहुंचते हैं, ध्वज एक संकेत है कि क्या हमारा शीर्ष स्रोत स्ट्रिंग है, pat_num इस शीर्ष द्वारा नामित नमूने का नंबर है।
सभी अतिरिक्त लाइनों की लंबाई की पूर्व-गणना एक अतिरिक्त मेमोरी लागत है। हम एसटीएल - वेक्टर से डेटा संरचना का उपयोग करेंगे। इसमें, स्मृति को गतिशील रूप से आवंटित किया जाता है, इसलिए, अतिरिक्त लागत शून्य होगी। स्पष्ट रूप से एक पंक्ति जोड़ने की प्रक्रिया इस प्रकार है (हम एक 26-अक्षर के निचले अक्षर लैटिन वर्णमाला => k = 26) का उपयोग करते हैं।

एक नया शीर्ष बनाने और बोरान को आरम्भ करने के लिए कार्य:

 vector<bohr_vrtx> bohr; bohr_vrtx make_bohr_vrtx(){ bohr_vrtx v; //(255)=(2^8-1)=(     )=(-1     4-  int) memset(v.next_vrtx, 255, sizeof(v.next_vrtx)); v.flag=false; return v; } void bohr_ini(){ //   -  bohr.push_back(make_bohr_vrtx()); }

बोरान में एक नमूना स्ट्रिंग जोड़ने की प्रक्रिया:

 void add_string_to_bohr(const string& s){ int num=0; //   for (int i=0; i<s.length(); i++){ char ch=s[i]-'a'; //    if (bohr[num].next_vrtx[ch]==-1){ //-1 -    bohr.push_back(make_bohr_vrtx()); bohr[num].next_vrtx[ch]=bohr.size()-1; } num=bohr[num].next_vrtx[ch]; } bohr[num].flag=true; pattern.push_back(s); bohr[num].pat_num=pattern.size()-1; }

एक बोर में एक स्ट्रिंग की उपस्थिति की जाँच:

 bool is_string_in_bohr(const string& s){ int num=0; for (int i=0; i<s.length(); i++){ char ch=s[i]-'a'; if (bohr[num].next_vrtx[ch]==-1){ return false; } num=bohr[num].next_vrtx[ch]; } return true; }

बोरॉन मशीन का निर्माण

ऑपरेशन के सिद्धांत का विवरण

हमारा काम एक परिमित निर्धारक ऑटोमेटोन का निर्माण करना है। यहाँ ऐसा क्या देखा जा सकता है । संक्षेप में, एक ऑटोमेटन की स्थिति एक बोरान के कुछ प्रकार की चोटी है। राज्यों से परिवर्तन 2 मापदंडों के अनुसार किया जाता है - वर्तमान शीर्ष v और प्रतीक ch। जिसके द्वारा हमें इस शिखर से जाने की आवश्यकता है। अधिक विशेष रूप से, आपको वर्टेक्स यू को खोजने की आवश्यकता है, जो लाइन वी के प्रत्यय (संभवतः शून्य) + वर्ण ch से मिलकर सबसे लंबी रेखा को दर्शाता है। यदि यह बोर में नहीं है, तो हम जड़ तक जाते हैं।

हमें इसकी आवश्यकता क्यों है? मान लीजिए कि हम निरंतर समय में, जल्दी से इस तरह की एक शीर्ष गणना कर सकते हैं। मान लीजिए कि हम स्ट्रिंग एस के प्रतिस्थापन [i..j] के अनुरूप बोरॉन के एक निश्चित शीर्ष पर खड़े हैं, वे घटनाएँ जिनमें हम खोज रहे हैं। अब हम बोरोन की सभी पंक्तियों को खोजते हैं, प्रत्यय है [i..j]। यह आरोप लगाया जाता है कि उन्हें जल्दी से खोजा जा सकता है (बाद में वर्णित)। उसके बाद, हम बस आटोमैटन वी की स्थिति से राज्य u तक प्रतीक s [j + 1] से जाते हैं और खोज जारी रखते हैं।

^{(चित्र 3)}
ऑटोमेटन को लागू करने के लिए, हमें शीर्ष से एक प्रत्यय लिंक की अवधारणा की आवश्यकता है।

प्रत्यय लिंक

हमें पॉइंटर को वर्टेक्स यू पर कॉल करते हैं जैसे कि स्ट्रिंग यू स्ट्रिंग वी का सबसे बड़ा उचित प्रत्यय है, या, अगर बोर में ऐसा कोई वर्टेक्स नहीं है, तो पॉइंटर को रूट करें। विशेष रूप से, रूट से एक लिंक इसकी ओर जाता है। हमें बोर में प्रत्येक शीर्ष के लिए प्रत्यय लिंक की आवश्यकता होगी, इसलिए हम एक अतिरिक्त चर प्रत्यय को शुरू करके शीर्ष की संरचना और शीर्ष बनाने की प्रक्रिया को थोड़ा संशोधित करेंगे।

कोड परिवर्तन:

 struct bohr_vrtx{ //... int suff_link; //suff_link -   }; bohr_vrtx make_bohr_vrtx(){ bohr_vrtx v; //... v.suff_link=-1; // - .   return v; }

यहाँ एक प्रत्यय व्यवस्था का एक उदाहरण है। अंजीर में बोरॉन के लिए लिंक। 1:

^{(चित्र 4)}

स्वचालन कार्यान्वयन

एक ऑटोमेटन के राज्यों के बीच एक त्वरित संक्रमण की समस्या पर लौटते हैं। जाहिर है, सभी संभावित बदलावों के बाद, bohr.size () * k है, क्योंकि प्रत्येक संभव शीर्ष और वर्णमाला के प्रत्येक संभावित प्रतीक के लिए, आपको संक्रमण को जानने की आवश्यकता है। पूर्व-गणना एल्गोरिदम के औसत चलने के समय को काफी कम कर देगी, इसलिए हम आलसी गतिकी के विचारों का उपयोग करेंगे - हम इसे आवश्यक मानेंगे और पहले से गणना किए गए मानों को याद रखेंगे।
हम संक्रमण (v, ch) के लिए परिकलित फ़ंक्शन का परिचय देते हैं। यहां यह विचार है: यदि वर्तमान शीर्ष से प्रतीक ch के साथ कोई बढ़त है, तो हम इसका अनुसरण करेंगे, अन्यथा हम प्रत्यय लिंक का अनुसरण करेंगे और नए शीर्ष से पुनरावृत्ति शुरू करेंगे। इस काम का अनुमान लगाना मुश्किल क्यों नहीं है।

^{(चित्र 5)}

एकमात्र सवाल प्रत्यय को सही ढंग से प्राप्त कर रहा है। ऊपर से लिंक। इस कार्य में, आप आलसी गतिकी का भी उपयोग कर सकते हैं। प्रत्यय इस प्रकार है: प्रत्यय प्राप्त करने के लिए। वर्टेक्स v (लिंक s [i..j]) के लिंक इसके पूर्वज समांतर तक जाते हैं, प्रत्यय के माध्यम से जाते हैं। लिंक बराबर और प्रतीक सिम्ब द्वारा वर्तमान शीर्ष टी से संक्रमण शुरू, जो किनारे से v तक लिखा है। जाहिर है, सबसे पहले हम सबसे बड़े प्रत्यय s [i..j-1] में आते हैं, जैसे कि यह प्रतीक सिंबल के साथ बढ़त रखता है, फिर हम इस किनारे पर जाते हैं। परिभाषा के अनुसार, परिणामी शीर्ष वर्टिक्स v से एक प्रत्यय लिंक है।

^{(चित्र 6)}

तो, यह स्पष्ट है कि ऑटोमेटन की स्थिति से प्रत्यय लिंक और संक्रमण प्राप्त करने के कार्य आपस में जुड़े हुए हैं। उनका सुविधाजनक कार्यान्वयन 2 कार्यों का प्रतिनिधित्व करता है, जिनमें से प्रत्येक एक दूसरे को पुन: कॉल करता है। दोनों पुनरावर्ती का आधार सूफ है। जड़ से या जड़ के बेटे से एक संदर्भ जड़ की ओर जाता है।

सबसे पहले, हम वर्टेक्स की संरचना और नई वर्टेक्स बनाने की प्रक्रिया को बदलेंगे:

 struct bohr_vrtx{ //... int auto_move[k],par; //auto_move -   , par - -   char symb; //    par    }; bohr_vrtx make_bohr_vrtx(int p,char c){ //         bohr_vrtx v; //... memset(v.auto_move, 255, sizeof(v.auto_move)); v.par=p; v.symb=c; return v; }

ऑटोमेटन के पूर्ण कार्यान्वयन के लिए घोषित किए जाने वाले कार्यों में से एक की आवश्यकता होती है:

 int get_auto_move(int v, char ch); int get_suff_link(int v){ if (bohr[v].suff_link==-1) //    if (v==0||bohr[v].par==0) // v -    v -  bohr[v].suff_link=0; else bohr[v].suff_link=get_auto_move(get_suff_link(bohr[v].par), bohr[v].symb); return bohr[v].suff_link; } int get_auto_move(int v, char ch){ if (bohr[v].auto_move[ch]==-1) if (bohr[v].next_vrtx[ch]!=-1) bohr[v].auto_move[ch]=bohr[v].next_vrtx[ch]; else if (v==0) bohr[v].auto_move[ch]=0; else bohr[v].auto_move[ch]=get_auto_move(get_suff_link(v), ch); return bohr[v].auto_move[ch]; }

"अच्छा" प्रत्यय लिंक को पहचानें

एक स्वचालित मशीन के साथ एल्गोरिथ्म को निर्धारित करना मुश्किल नहीं है: हम लाइन पढ़ते हैं, लाइन के पात्रों द्वारा राज्य से राज्य में स्थानांतरित करते हैं, प्रत्येक राज्य में हम प्रत्यय द्वारा चलते हैं। मशीन की स्थिति में लाइन के प्रत्ययों द्वारा लिंक द्वारा, जबकि बोर में उनकी उपस्थिति के लिए जाँच की जाती है।
सबकुछ ठीक हो जाएगा, लेकिन यह पता चला है कि अहो-कोरसिक के इस संस्करण में एन के संबंध में द्विघात स्पर्शोन्मुख है - रीड स्ट्रिंग एस की लंबाई। दरअसल, राज्य v से एक लाइन के लिए v.length () प्रत्यय मिल सकता है, और राज्य से एक संक्रमण इस रेखा की लंबाई 1 तक बढ़ा सकता है। Tsimes souf के माध्यम से बढ़ रहा है। लिंक केवल उन लोगों में आते हैं जो नमूना स्ट्रिंग्स के बीच स्पष्ट रूप से उपलब्ध हैं। हम "अच्छे" suf की अवधारणा का परिचय देते हैं। suff_flink लिंक। तो, बोह्र [v] .suff_flink बोर में निकटतम प्रत्यय है जिसके लिए ध्वज = सत्य है। ऐसे लिंक का उपयोग करने पर "कूद" की संख्या कम हो जाएगी और इस स्थिति में समाप्त होने वाली खोज की गई प्रविष्टियों की संख्या के लिए आनुपातिक होगी।

^{(चित्र 7)}

फिर से हम वर्टेक्स की संरचना और अतिरिक्त प्रक्रिया को बदलेंगे:

 struct bohr_vrtx{ //... int suff_flink; //suff_flink - "" .  }; bohr_vrtx make_bohr_vrtx(int p,char c){ bohr_vrtx v; //... v.suff_flink=-1; return v; }

उनकी गणना करना काफी सरल है, सभी एक ही आलसी गतिशीलता। हम "अच्छा" योग गिनने के कार्य का परिचय देते हैं। लिंक। यदि ऊपर से पीड़ित के लिए। लिंक ध्वज = सही है, तो यह वांछित शीर्ष है, अन्यथा, हम पुनरावृत्ति उसी शीर्ष से शुरू करते हैं।

एक अच्छे योग की गणना। लिंक:

 int get_suff_flink(int v){ if (bohr[v].suff_flink==-1){ int u=get_suff_link(v); if (u==0) // v - ,  .  v    bohr[v].suff_flink=0; else bohr[v].suff_flink=(bohr[u].flag)?u:get_suff_flink(u); } return bohr[v].suff_flink; }

स्वचालित खोज का कार्यान्वयन

खोज को मामूली रूप से लागू किया जाता है। हमें "अच्छे" योगी पर चलने के लिए एक प्रक्रिया की आवश्यकता है। लिंक चेक (v, i) ऑटोमेटन v की वर्तमान स्थिति से दिया गया है कि यह स्थिति शब्द में i-th अक्षर में समाप्त होती है।

जांच (v, i)

 void check(int v,int i){ for(int u=v;u!=0;u=get_suff_flink(u)){ if (bohr[u].flag) cout<<i-pattern[bohr[u].pat_num].length()+1<<" "<<pattern[bohr[u].pat_num]<<endl; } }

यहाँ खोज ही है:

 void find_all_pos(const string& s){ int u=0; for(int i=0;i<s.length();i++){ u=get_auto_move(u,s[i]-'a'); check(u,i+1); } }

और यहाँ काम का एक उदाहरण है:

  bohr_ini(); add_str_to_bohr("abc"); add_str_to_bohr("bcdc"); add_str_to_bohr("cccb"); add_str_to_bohr("bcdd"); add_str_to_bohr("bbbc"); find_all_pos("abcdcbcddbbbcccbbbcccbb");

चल रहा है:
1 एबीसी
2 बी.डी.सी.सी.
6 bcdd
10 बीबीसीबी
13 सीसीबीबी
16 बी.बी.सी.
19 सी.सी.बी.

जटिलता और भंडारण विधियों का आकलन

एल्गोरिथ्म का मौजूदा संस्करण लंबाई s (N = s.length ()) के साथ एक चक्र से गुजरता है, जहां से इसे पहले से ही O (N * O (चेक)) के रूप में अनुमानित किया जा सकता है, लेकिन चूंकि चेक केवल झंडे के लिए जानबूझकर चिह्नित खामियों पर कूदता है। , फिर सामान्य एसिम्पोटिक्स को ओ (एन + टी) के रूप में अनुमान लगाया जा सकता है, जहां टी एस में सभी नमूना स्ट्रिंग्स के सभी संभावित घटनाओं की संख्या है। सटीक होने के लिए और ऑटोमेटन और प्रत्यय की गणना को ध्यान में रखें। लिंक, तब एल्गोरिथ्म O (M * k + N + t) चलाता है, जहां M = bohr.size ()। मेमोरी - बोरॉन के प्रत्येक शीर्ष के लिए आकार k की निरंतर सरणियाँ, अनुमान O (M * k) से आती है।

यह पता चला है कि भंडारण का एक और तरीका, और विशेष रूप से, वर्णमाला तक पहुंच, इस मूल्यांकन को बदल सकता है। हम सरणी के बजाय मानचित्र <char, int> मैपिंग का उपयोग करेंगे। हम यहां और यहां पढ़ते हैं , हम देखते हैं कि एसटीएल से नक्शा डेटा संरचना एक लाल-काले पेड़ द्वारा कार्यान्वित की जाती है, और इसके तत्वों तक पहुंचने का समय तत्वों की संख्या के लघुगणक के लिए आनुपातिक है। हमारे मामले में, वर्णमाला k (जो लगभग स्थिर है) के आकार का द्विआधारी लघुगणक है। कुल समय O ((M + N) * log k + t) है। व्यवहार में, यह एक सरणी से काफी तेज है। मानचित्र तत्वों के लिए अतिरिक्त मेमोरी कोशिकाओं को संग्रहीत नहीं करता है, इसलिए मेमोरी बोर में किनारों की संख्या के लिए आनुपातिक है (और इसलिए बोर में कोने की संख्या के लिए, क्योंकि एम कोने वाले पेड़ में एम -1 किनारे हैं)। मशीन संक्रमण गणना की संख्या स्पष्ट रूप से स्ट्रिंग की लंबाई के लिए आनुपातिक है। परिणामी अनुमान O (M + N) है।

	सरणियों के साथ विकल्प next_vrtx [k], auto_move [k]	लाल-काले पेड़ के नक्शे के साथ वेरिएंट <char, int>
समय की जटिलता	O (M * k + N + t)	O ((M + N) * लॉग k + t)
अंतरिक्ष की जटिलता	O (M * k)	O (M + N)

_{पुनश्च : यहाँ एक पूरी तरह से कार्यान्वित कार्य एल्गोरिथ्म का लिंक दिया गया है: अहो-कोरसिक एल्ग} ।

अहो-कोरसिक एल्गोरिथम