🕵🏻 👩🏽‍🤝‍👨🏾 😿 एक प्रत्यय का पेड़ बनाना: उककोन एल्गोरिथ्म 📇 🏧 🤨

श्रमिकों के अनुरोध पर, मैं उककोन एल्गोरिथ्म का वर्णन और प्रमाण पोस्ट करता हूं ।

कार्य विवरण

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

बोरों की एक मनमानी सेट के लिए बोरॉन का निर्माण ओ (इन लाइनों की लंबाई का योग) के लिए किया गया है। जाहिर है, एक स्ट्रिंग के सभी प्रत्ययों की लंबाई का योग स्ट्रिंग की लंबाई के वर्ग के समानुपाती होता है। इस प्रकार, एक तुच्छ एल्गोरिथ्म के साथ एक प्रत्यय पेड़ का निर्माण ओ (एन ² ) के लिए काम करता है। और यहां एक उचित सवाल उठता है: क्या प्रत्यय का पेड़ तेजी से बनाना संभव है?

वास्तव में यह संभव है।

और इसलिए, चलो शुरू से ही शुरू करते हैं। स्ट्रिंग की लंबाई S = s ₁ ... s _{n है} , जिसके लिए हम एक प्रत्यय वृक्ष का निर्माण करते हैं, _{N के} बराबर हो। कल्पना करें कि वृक्ष नीचे बढ़ता है, अर्थात। जड़ शीर्ष चोटी है, और पसलियां ऊपर, पूर्वज से, वंश के नीचे से जाती हैं। भविष्य में, मैं कभी-कभी शीर्षकों को प्रत्यय कहूंगा, और इसके विपरीत, प्रत्यय प्रत्ययों को लागू करते हुए, यदि वे प्रत्ययों के लिए कोने हैं, या संबंधित सब्सट्रिंग्स।

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

सबसे पहले, हम दिखाते हैं कि संपीड़ित पेड़ में मौजूदा संख्याओं की कुल संख्या O (N) है।

लेम्मा: एक संकुचित प्रत्यय O (N) में कोने की संख्या

आइए देखें कि किस प्रकार की चोटियां हैं। सबसे पहले, ये पत्ते हैं। दूसरे, ये "कांटे" हैं - एक से अधिक बच्चों के साथ चोटियाँ। जड़ भी सबसे ऊपर है।

केवल एक जड़ है।

प्रत्येक शीट में केवल एक प्रत्यय हो सकता है। शीट के शीर्ष को T = s _l ... s _r - s में एक विकल्प है जो प्रत्यय नहीं है के अनुरूप है। तब S में एक पंक्ति Ts _{r + 1} मौजूद है, जिसका अर्थ है कि हमारी शीट से एक किनारा होना चाहिए। इस प्रकार, चादरों की संख्या N से अधिक नहीं है।

पहली नज़र में, यह स्पष्ट नहीं है कि कितने कांटे हो सकते हैं। ऐसा करने के लिए, जब वे बनाए जाते हैं तो एक संपीड़ित पेड़ के निर्माण स्थलों पर विचार करें। एक प्रत्यय जोड़ते समय, हम पहले पेड़ से गुजरते हैं, और फिर 3 मामले संभव हैं:

1) हमने प्रत्यय जोड़ना समाप्त कर दिया, पहले से निर्मित पेड़ से बाहर निकलने की कोशिश नहीं की। तब कांटे नहीं बने थे

2) हम एक अकल्पनीय शिखर पर पेड़ से बाहर निकलना चाहते थे। फिर इस शीर्ष से प्रत्यय के अंत तक एक बढ़त बनाई जाती है। नया कांटा भी नहीं बन रहा है।

3) हम एक काल्पनिक चोटी के एक पेड़ से बाहर निकलना चाहते थे। फिर हमें इस किनारे को दो हिस्सों में विभाजित करना चाहिए, इस जगह में एक कांटा बनाना चाहिए, और एक किनारे उस किनारे के शेष हिस्से के अनुरूप होगा, जिस पर हम रुके थे, और दूसरा होगा

प्रत्यय के अंत से मेल खाते हैं। इस मामले में, हमने केवल एक कांटा बनाया है।

हम पाते हैं कि कांटा N से अधिक नहीं है।

परिणामस्वरूप, संपीडित वृक्ष में कोने की संख्या O (N) है।

हमारे द्वारा माना गया एल्गोरिथ्म ऑनलाइन मोड में काम करेगा, अर्थात। एल्गोरिथ्म के kth कदम के बाद, हम लंबाई k की एक स्ट्रिंग के उपसर्ग के लिए एक प्रत्यय पेड़ प्राप्त करना चाहते हैं। इस मामले में, हम बाद में थोड़े समय के लिए आवश्यकतानुसार स्ट्रिंग की लंबाई बढ़ा सकते हैं। क्योंकि हमारे पास N प्रत्यय हैं, O (N) अक्षर जोड़ते हैं, हमें O (N ² ) रनटाइम मिलता है। कार्य को गति देने के लिए, हम पेड़ से प्रत्यय लिंक जोड़ेंगे और 3 अनुकूलन करेंगे।

प्रत्यय लिंक - वर्टेक्स (काल्पनिक सहित) का पॉइंटर (या संख्या), जो वर्तमान वर्टेक्स के अनुरूप लाइन के सबसे बड़े उचित (लाइन के बराबर नहीं) प्रत्यय से मेल खाता है। चूँकि हम सभी प्रत्ययों को संग्रहीत करते हैं, और इसलिए सभी स्ट्रिंग का, एक स्ट्रिंग का, तो स्ट्रिंग T = s _l ... का प्रत्यय लिंक स्ट्रिंग T '= s _{l + 1} ... _r , i.e. एक-एक करके स्ट्रिंग की लंबाई कम करता है। हम केवल कांटे और रूट के लिए प्रत्यय लिंक स्टोर करेंगे। मामलों पर विचार नहीं करने के लिए, हम एक "खाली" वर्टेक्स रिक्त जोड़ देंगे, जिसमें से वर्णमाला के सभी वर्णों के किनारों को जड़ तक ले जाया जाता है, और जड़ से एक प्रत्यय लिंक इसकी ओर जाता है। तथ्य यह है कि कांटे से प्रत्यय लिंक एक अकल्पनीय चोटी की ओर जाता है, मैं सबूत के बिना छोड़ दूंगा, क्योंकि मैं इसे स्पष्ट मानता हूं। चादरों के लिए, एक समान कथन सत्य नहीं है। एक शीट से प्रत्यय लिंक एक काल्पनिक शीर्ष पर भी इंगित कर सकते हैं, इसलिए हमने उन्हें शीट के लिए स्टोर नहीं किया। इसलिए, प्रत्यय लिंक के कारण अकल्पनीय कार्य होते हैं और उनकी संख्या O (N) है।

अब अनुकूलन के बारे में

अनुकूलन नंबर 1: एक शीट थी, एक शीट थी और आप रहेंगे

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

अनुकूलन नंबर 2: यदि हम बस किनारे के साथ चले गए, तो छोटे प्रत्ययों में हम किनारे के साथ भी जाएंगे

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

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

1) हम किनारे के साथ निकटतम पूर्वज-कांटा पर जाते हैं और उस प्रतिस्थापन को याद करते हैं जिसके साथ हम ऊपर चढ़े थे;

2) कांटा से प्रत्यय लिंक का पालन करें;

3) नीचे जाओ जब तक हम सब याद किया सबस्ट्रिंग के माध्यम से नहीं जाते। शायद हमें कई कांटों से गुजरना पड़ता है, फिर हमें बस दाहिने किनारे पर जाने की ज़रूरत है;

4) शिखर, संभवतः काल्पनिक, जिस पर हम रुकेंगे, और मूल के लिए एक "प्रत्यय लिंक" होगा।

तथ्य यह है कि वंश के दौरान हम पेड़ से बाहर निकलने की कोशिश नहीं करेंगे, मैं स्पष्ट रूप से सबूत के बिना छोड़ देता हूं।

और इसलिए, हमारे पास प्रतीक जोड़ते समय 3 कार्य होते हैं:

1) शीट विस्तार (एक शीट के लिए प्रदर्शन)

2) एक कांटा का निर्माण (एक काल्पनिक शीर्ष या कांटा के लिए प्रदर्शन किया गया, जिसमें से इस प्रतीक के साथ कोई बढ़त नहीं है)

3) बस किनारे के साथ गुजरें (एक काल्पनिक चोटी या कांटा के लिए प्रदर्शन किया जाता है, जिसमें से एक ऐसी धार है)

यह तर्क दिया जाता है कि यदि हम लंबाई कम करने के लिए प्रत्ययों पर विचार करते हैं, तो उनके साथ इस क्रम 11 ... 12 ... 23..33 में कार्रवाई की जाएगी। (यह इस तथ्य से निम्नानुसार है कि इस शीर्ष के प्रत्यय के शीर्ष से इस शीर्ष से किनारों के समान कम से कम सभी किनारे हैं, लेकिन अभी भी अन्य किनारे हो सकते हैं)। इसके अलावा, कार्रवाई के परिवर्तन की स्थिति 1 से 2 और 2 से 3 केवल बाईं ओर चलती है (यह मत भूलो कि प्रत्येक चरण के बाद हमारे पास इस अनुक्रम की लंबाई 1 से बढ़ जाती है, क्योंकि एक नया प्रत्यय जोड़ा जाता है)।

हम पहले शीर्ष का नाम देते हैं जो स्टार्ट-पॉइंट (एसपी) के रूप में एक पत्ता नहीं है। यह शीर्ष इस क्रम में 2 की पहली घटना से मेल खाती है। सच है, किसी भी प्रकार की 2 क्रियाएं नहीं हो सकती हैं, फिर एसपी 3. की पहली घटना है। और 3 की पहली घटना के अनुरूप शीर्ष को सक्रिय-बिंदु (एपी) कहा जाता है। पहले दो अनुकूलन के बाद हमें क्या मिला? इस चरण में अनुक्रम को सपा से शुरू करने और एपी में आने पर समाप्त होने पर विचार किया जा सकता है। अब वाजिब सवाल खड़ा हो गया है, अगले चरण के लिए एसपी को जल्दी कैसे ढूंढा जाए? इसके लिए एक तीसरा अनुकूलन है।

अनुकूलन नंबर 3: अगले चरण के लिए एसपी वर्तमान चरण के एपी का वंशज है

इसके साथ शुरू करने के लिए, एसपी इस चरण से पहले प्रत्ययों के एक कोने का वंशज है। चरण के निष्पादन के दौरान, कुछ कार्रवाई की गई थी, और फिर वर्तमान प्रतीक के साथ किनारे के साथ वंश। इसलिए, मैं वंशजों के साथ नहीं, बल्कि पिछले चरण के शीर्षकों के साथ काम करूंगा।

स्पष्ट तथ्य: अगला एसपी वह प्रत्यय नहीं हो सकता है जिसके साथ वर्तमान कदम पर पहले प्रकार की कार्रवाई की गई थी। इसके अलावा, एसपी एक प्रत्यय नहीं हो सकता है जिसके लिए दूसरे प्रकार की कार्रवाई की गई थी, क्योंकि उसी समय, हमने एक कांटा बनाया और, पत्ती की ओर जाने वाले किनारे के साथ चलते हुए, पत्ती से टकराया। प्रत्यय पिछले AP के अनुरूप क्यों है? एपी से, हम केवल इसे से कम से कम कुछ रिब करना चाहते हैं। सपा के अनुरूप प्रत्यय टी पर विचार करें। चूंकि इसमें इस चिन्ह के साथ कम से कम एक छोर है, तो टी को एस में गैर-प्रत्यय के रूप में सामना किया गया था। इसलिए, एस में एक विकल्प टी _{कश्मीर} है (मुझे याद है कि हमने इस चरण में प्रतीक के के को जोड़ा था)। फिर एक नई लाइन में, जोड़ा गया प्रतीक के के साथ, एक सब्स्ट्रिंग Ts _k c होगा, जहां c कुछ वर्ण है। तो, शीर्ष पर _k (सपा का एक वंशज), AP के लिए शर्त पूरी हो गई है, और जिस शिखर की हमने अभी जांच की है वह जल्द से जल्द संभव है, जिसका अर्थ है कि यह अगला AP होगा।

परिणामस्वरूप, हमें यह मिलता है कि हमारे लिए केवल एपी को स्टोर करना और इसे स्थानांतरित करना पर्याप्त है। एपी को स्थानांतरित करते समय लंबवत प्रसंस्करण (क्रॉसहेयर बनाना या किसी मौजूदा एक किनारे को जोड़ना) एक पेड़ बनाने के लिए पर्याप्त होगा।

बधाई! यदि आप इस बिंदु तक पढ़ चुके हैं और लगभग सब कुछ समझ गए हैं, तो आप स्वयं उकोनोन एल्गोरिथ्म का एक कार्यशील कार्यान्वयन लिख सकते हैं। एक बेहतर समझ के लिए, मैं इस एल्गोरिथ्म का छद्म कोड पोस्ट करता हूं:

....   .....  root  blank     ; SP <- root; k = 0; while (c =  k-  ) { while ( SP     c) {   SP    [k,oo]; SP <-     SP; } SP <-      C  1 ; k++;//   ; } ....      V .... U <-  V; S <-    U  V; U <- suff(U); //      while (S  ) { C <-   S; if ( ,   C ==  S) {      ; } else if ( ,   C >  S){      ;   ; } else { // ,   C <  S     ;   S  ,    ; } }

लेकिन आखिरी सवाल रह गया। इस एल्गोरिथ्म O (N) का स्पर्शोन्मुख व्यवहार क्यों है? इस तथ्य के बावजूद कि ये अनुकूलन हमें सभी प्रत्यय के साथ काम करने की अनुमति देते हैं 2N गुना से अधिक नहीं (प्रत्येक प्रत्यय हम या तो प्रक्रिया करते हैं और आगे जाते हैं, या इस प्रत्यय पर रहते हैं और अगले चरित्र को देखते हैं; इनमें से प्रत्येक मामला N से अधिक नहीं है), हमारे पास अभी भी बदलाव हैं प्रत्यय लिंक द्वारा, जिसके लिए यह बिल्कुल स्पष्ट नहीं है कि क्लिक की कुल संख्या O (N) होगी।

असममित प्रमाण

क्योंकि यदि प्रत्यक्ष लिंक संक्रमण O (1) के लिए काम करता है, और उनमें से कोई भी N से अधिक नहीं हैं, तो यह केवल किनारों पर नीचे जाने पर विचार करने के लिए पर्याप्त है। ऐसा करने के लिए, किनारे के साथ विस्थापन की लंबाई पर विचार करें जिसके साथ हम पूर्वज पर चढ़ गए थे। L के बराबर होने दें। फिर, किनारों के नीचे से प्रत्येक मार्ग के साथ, यह लंबाई कम से कम 1. कम हो जाती है और यह केवल मूल प्रक्रिया में बढ़ जाती है जब प्रतीक C के साथ किनारे से गुजरते हुए, और एक बार में 1 से अधिक नहीं। और ऐसे मार्ग एन। विस्थापन का अंतिम मूल्य सीमा [0, एन] में है, एक्सटेंशन एन की संख्या, फिर संकुचन की कुल संख्या 2N से अधिक नहीं हो सकती है। इसका अर्थ है कि प्रत्यय लिंक O (N) का अनुसरण करते समय नीचे की ओर बढ़ने वाली कुल संख्या। परिणामस्वरूप, प्रत्येक प्रकार की कार्रवाई की संख्या O (N) है, और इसलिए सभी क्रियाओं की कुल संख्या O (N) है। अस्मितापूर्ण व्यवहार सिद्ध होता है।

प्रत्यय वृक्षों का उपयोग करना

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

दो या दो से अधिक लाइनों का सबसे बड़ा सामान्य प्रतिस्थापन।

समस्या की स्थिति सरल है: स्ट्रिंग्स का एक सेट दिया गया है (हम मामले पर विचार करेंगे जब उनमें से दो हैं), और रैखिक समय में उनके सबसे बड़े सामान्य प्रतिस्थापन को खोजने के लिए आवश्यक है। ऐसा करने के लिए, आपको इन सबस्ट्रिंग के सामान्यीकृत प्रत्यय पेड़ बनाने की आवश्यकता है। इस पेड़ का प्रत्येक पत्ता कुछ पंक्ति डेटा सेट का एक प्रत्यय है। फिर, यदि हम प्रत्येक कांटा के लिए संकेत देते हैं, तो इस रेखा के सेट पर रेखाओं के प्रत्ययों की शुरुआत होती है, फिर सबसे बड़ा विकल्प खोजने के लिए, बस सभी शीर्ष रेखाओं से गुजरें और यदि शीर्ष में सभी पंक्तियों का एक सेट होता है, तो उसकी लंबाई और पहले से पाए गए उत्तर की लंबाई।

पहले कार्य में पत्तियों की संख्या की गणना और दूसरे में पंक्तियों के सेट को गतिशील प्रोग्रामिंग को संदर्भित किया जाता है और इस विषय में पारंगत नहीं है। मैं केवल संक्षेप में कह सकता हूं कि इसके लिए पहले से ज्ञात परिणामों के आधार पर, नीचे से पेड़ के साथ चलना और गणना करना आवश्यक है।

पुनश्च। अगर इच्छा रखने वाले हैं, तो मैं अहो-कोरसिक एल्गोरिथ्म पर एक लेख लिख सकता हूं।

पीएसएस। अगर अचानक कुछ अस्पष्ट क्षण बने रहें, तो लिखें, मैं और स्पष्ट रूप से समझाऊंगा।

एक प्रत्यय का पेड़ बनाना: उककोन एल्गोरिथ्म