javascript - tutorial - जावास्क्रिप्ट डाउनलोड




सादे अंग्रेजी में Ukkonen प्रत्यय पेड़ एल्गोरिदम (4)

निम्नांकित रूप से यह दिखाकर Ukkonen एल्गोरिदम का वर्णन करने का प्रयास है कि स्ट्रिंग सरल होने पर यह क्या करता है (यानी कोई दोहराया गया वर्ण नहीं है), और उसके बाद इसे पूर्ण एल्गोरिदम में विस्तारित किया जाता है।

सबसे पहले, कुछ प्रारंभिक बयान।

  1. हम जो निर्माण कर रहे हैं, मूल रूप से एक खोज trie की तरह है। तो वहां एक रूट नोड है, किनारों से बाहर निकलने वाले किनारे नए नोड्स की ओर अग्रसर होते हैं, और आगे के किनारों से बाहर निकलते हैं, और आगे

  2. लेकिन : एक खोज trie के विपरीत, किनारे लेबल एकल अक्षर नहीं हैं। इसके बजाए, प्रत्येक किनारे को पूर्णांक की एक जोड़ी [from,to] का उपयोग करके लेबल किया जाता है। ये पाठ में पॉइंटर्स हैं। इस अर्थ में, प्रत्येक किनारे में मनमानी लंबाई का एक स्ट्रिंग लेबल होता है, लेकिन केवल ओ (1) स्पेस (दो पॉइंटर्स) लेता है।

मूल सिद्धांत

मैं सबसे पहले यह देखना चाहता हूं कि एक विशेष रूप से सरल स्ट्रिंग के प्रत्यय पेड़ को कैसे बनाया जाए, एक स्ट्रिंग जिसमें दोहराए गए वर्ण नहीं हैं:

abc

एल्गोरिदम बाएं से दाएं, चरणों में काम करता हैस्ट्रिंग के प्रत्येक चरित्र के लिए एक कदम है । प्रत्येक चरण में एक से अधिक व्यक्तिगत संचालन शामिल हो सकते हैं, लेकिन हम देखेंगे (अंत में अंतिम अवलोकन देखें) कि संचालन की कुल संख्या ओ (एन) है।

तो, हम बाएं से शुरू करते हैं, और पहले रूट नोड (बाईं ओर) से एक पत्ते तक किनारे बनाने और इसे [0,#] रूप में लेबल करके केवल एक वर्ण को सम्मिलित करते हैं, जिसका अर्थ है कि किनारा सबस्ट्रिंग का प्रतिनिधित्व करता है स्थिति 0 से शुरू होता है और वर्तमान अंत में समाप्त होता है । मैं वर्तमान अंत का मतलब # प्रतीक का उपयोग करता हूं, जो स्थिति 1 पर है (ठीक बाद a )।

तो हमारे पास एक प्रारंभिक पेड़ है, जो इस तरह दिखता है:

और इसका क्या अर्थ है यह है:

अब हम 2 स्थिति ( b ठीक बाद) की प्रगति करते हैं। प्रत्येक चरण में हमारा लक्ष्य वर्तमान स्थिति तक सभी प्रत्यय डालना है । हम इसे करते हैं

  • मौजूदा a एज को ab तक विस्तारित करना
  • b लिए एक नया किनारा डालने

हमारे प्रतिनिधित्व में ऐसा लगता है

और इसका क्या अर्थ है:

हम दो चीजों का पालन ​​करते हैं:

  • ab लिए किनारे का प्रतिनिधित्व वही है जैसा कि यह प्रारंभिक पेड़ में होता था: [0,#] । इसका अर्थ स्वचालित रूप से बदल गया है क्योंकि हमने वर्तमान स्थिति # को 1 से 2 तक अपडेट किया है।
  • प्रत्येक किनारे ओ (1) अंतरिक्ष का उपभोग करता है, क्योंकि इसमें पाठ में केवल दो पॉइंटर्स होते हैं, भले ही यह कितने वर्णों का प्रतिनिधित्व करता हो।

इसके बाद हम फिर से स्थिति बढ़ाते हैं और प्रत्येक मौजूदा किनारे पर c जोड़कर पेड़ को अपडेट करते हैं और नए प्रत्यय c लिए एक नया किनारा डालते हैं।

हमारे प्रतिनिधित्व में ऐसा लगता है

और इसका क्या अर्थ है:

हम निरीक्षण करते हैं:

  • पेड़ प्रत्येक चरण के बाद वर्तमान स्थिति तक सही प्रत्यय पेड़ है
  • टेक्स्ट में वर्ण होने के कई कदम हैं
  • प्रत्येक चरण में काम की मात्रा ओ (1) है, क्योंकि सभी मौजूदा किनारों को स्वचालित रूप से # बढ़ाकर अपडेट किया जाता है, और अंतिम वर्ण के लिए एक नया किनारा डालने से ओ (1) समय में किया जा सकता है। इसलिए लंबाई की एक स्ट्रिंग के लिए, केवल ओ (एन) समय आवश्यक है।

पहला विस्तार: सरल पुनरावृत्ति

बेशक यह केवल इतना ही काम करता है क्योंकि हमारी स्ट्रिंग में कोई दोहराव नहीं है। अब हम एक और यथार्थवादी स्ट्रिंग को देखते हैं:

abcabxabcd

यह पिछले उदाहरण के रूप में abc साथ शुरू होता है, फिर ab दोहराया जाता है और x बाद पीछा किया जाता है, और उसके बाद abc दोहराया जाता है।

चरण 1 से 3: पहले 3 चरणों के बाद हमारे पिछले उदाहरण से पेड़ है:

चरण 4: हम # स्थिति 4 पर ले जाते हैं। यह सभी मौजूदा किनारों को इस पर अद्यतन करता है:

और हमें रूट पर वर्तमान चरण, a , के अंतिम प्रत्यय को सम्मिलित करने की आवश्यकता है।

ऐसा करने से पहले, हम दो और चर ( # अलावा) पेश करते हैं, जो निश्चित रूप से वहां रहे हैं लेकिन हमने अब तक उनका उपयोग नहीं किया है:

  • सक्रिय बिंदु , जो एक तिहरा है (active_node,active_edge,active_length)
  • remainder , जो एक पूर्णांक है यह दर्शाता है कि हमें कितने नए प्रत्यय को सम्मिलित करने की आवश्यकता है

इन दोनों का सटीक अर्थ जल्द ही स्पष्ट हो जाएगा, लेकिन अभी के लिए बस कहना है:

  • सरल abc उदाहरण में, सक्रिय बिंदु हमेशा (root,'\0x',0) , यानी active_node रूट नोड था, active_edge को शून्य वर्ण '\0x' रूप में निर्दिष्ट किया गया था, और active_length शून्य था। इसका प्रभाव यह था कि एक नया किनारा जिसे हमने प्रत्येक चरण में डाला था, रूट नोड पर ताजा बनाया गया किनारा के रूप में डाला गया था। हम जल्द ही देखेंगे कि इस जानकारी का प्रतिनिधित्व करने के लिए एक तिहाई क्यों जरूरी है।
  • remainder प्रत्येक चरण की शुरुआत में हमेशा 1 पर सेट किया गया था। इसका अर्थ यह था कि प्रत्येक चरण के अंत में सक्रिय रूप से डालने के लिए हमें प्रत्यय की संख्या 1 थी (हमेशा केवल अंतिम चरित्र)।

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

  • हम रूट नोड पर एक ताजा किनारा [4,#] डालते हैं। इसके बजाए हम बस ध्यान देते हैं कि प्रत्यय पहले से ही हमारे पेड़ में है। यह एक लंबे किनारे के बीच में समाप्त होता है, लेकिन हम इससे परेशान नहीं हैं। हम चीजों को वैसे ही छोड़ देते हैं जैसे वे हैं।
  • हमने सक्रिय बिंदु (root,'a',1) । इसका मतलब है कि सक्रिय बिंदु अब रूट नोड के आउटगोइंग किनारे के बीच में है जो विशेष रूप से उस किनारे पर स्थिति 1 के बाद शुरू होता है। हम देखते हैं कि किनारे को केवल अपने पहले अक्षर a द्वारा निर्दिष्ट किया गया a । यह पर्याप्त है क्योंकि किसी भी विशेष चरित्र से शुरू होने वाला केवल एक किनारा हो सकता है (पुष्टि करें कि पूरे विवरण को पढ़ने के बाद यह सच है)।
  • हम भी remainder वृद्धि करते हैं, इसलिए अगले चरण की शुरुआत में यह 2 होगा।

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

चरण 5: हम वर्तमान स्थिति # से 5 को अपडेट करते हैं। यह स्वचालित रूप से पेड़ को अपडेट करता है:

और क्योंकि remainder 2 है , हमें वर्तमान स्थिति के दो अंतिम प्रत्यय डालने की आवश्यकता है: ab और b । यह मूल रूप से है क्योंकि:

  • पिछले चरण से a प्रत्यय कभी ठीक से डाला नहीं गया है। तो यह बना रहा है , और चूंकि हमने एक कदम प्रगति की है, अब यह अब से अब तक बढ़ी है।
  • और हमें नया अंतिम किनारा b

प्रैक्टिस में इसका मतलब है कि हम सक्रिय बिंदु पर जाते हैं (जो कि अब abcab एज पर है) के पीछे इंगित करता है, और वर्तमान अंतिम चरित्र b डालें। लेकिन: फिर, यह पता चला है कि b भी उसी किनारे पर मौजूद है।

तो, फिर, हम पेड़ नहीं बदलते हैं। हम बस:

  • सक्रिय बिंदु को अद्यतन करें (root,'a',2) (उसी नोड और एज जैसा पहले है, लेकिन अब हम b पीछे इंगित करते हैं)
  • remainder को 3 तक बढ़ाएं क्योंकि हमने अभी भी पिछले चरण से अंतिम किनारे को ठीक से नहीं डाला है, और हम वर्तमान अंतिम किनारे को भी सम्मिलित नहीं करते हैं।

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

हम # वृद्धि करके 6 कदम आगे बढ़ते हैं। पेड़ को स्वचालित रूप से अपडेट किया जाता है:

क्योंकि remainder 3 है , हमें abx , bx और x abx । सक्रिय बिंदु हमें बताता है कि ab कहां समाप्त होता है, इसलिए हमें केवल वहां कूदने और x डालने की आवश्यकता है। वास्तव में, x अभी तक नहीं है, इसलिए हम abcabx किनारे को विभाजित करते हैं और एक आंतरिक नोड डालें:

किनारे का प्रतिनिधित्व अभी भी टेक्स्ट में पॉइंटर्स हैं, इसलिए एक आंतरिक नोड को विभाजित करना और डालना ओ (1) समय में किया जा सकता है।

इसलिए हमने abx और कमी के साथ remainder 2 को निपटाया है। अब हमें अगले शेष प्रत्यय, bx डालने की आवश्यकता है। लेकिन इससे पहले कि हम सक्रिय बिंदु को अद्यतन करने की जरूरत है। इसके लिए नियम, किनारे को विभाजित करने और डालने के बाद, नीचे नियम 1 कहा जाएगा, और जब भी active_node रूट होता है तब यह लागू होता है (हम नीचे अन्य मामलों के लिए नियम 3 सीखेंगे)। नियम 1 है:

रूट से सम्मिलन के बाद,

  • active_node रूट बना रहता है
  • active_edge को नए प्रत्यय के पहले अक्षर पर सेट किया गया है जिसे हमें सम्मिलित करने की आवश्यकता है, यानी b
  • active_length 1 से कम हो जाती है

इसलिए, नया सक्रिय-बिंदु ट्रिपल (root,'b',1) इंगित करता है कि अगला डालने bcabx एज पर किया जाना चाहिए, 1 अक्षर के पीछे, यानी b पीछे। हम ओ (1) समय में सम्मिलन बिंदु की पहचान कर सकते हैं और जांच सकते हैं कि x पहले से मौजूद है या नहीं। यदि यह मौजूद था, तो हम वर्तमान कदम को समाप्त कर देंगे और जिस तरह से यह सब कुछ छोड़ देंगे। लेकिन x मौजूद नहीं है, इसलिए हम किनारे को विभाजित करके इसे सम्मिलित करते हैं:

दोबारा, इसने ओ (1) समय लिया और हम remainder 1 को अपडेट करते हैं और सक्रिय बिंदु (root,'x',0) नियम 1 राज्य के रूप में अद्यतन करते हैं।

लेकिन एक और चीज है जो हमें करने की ज़रूरत है। हम इस नियम 2 को कॉल करेंगे :

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

हमें अभी भी वर्तमान चरण के अंतिम प्रत्यय को सम्मिलित करने की आवश्यकता है, x । चूंकि सक्रिय नोड के active_length घटक 0 पर गिर गए हैं, इसलिए अंतिम डालने सीधे रूट पर किया जाता है। चूंकि x साथ शुरू होने वाले रूट नोड पर कोई आउटगोइंग एज नहीं है, इसलिए हम एक नया किनारा डालते हैं:

जैसा कि हम देख सकते हैं, वर्तमान चरण में सभी शेष आवेषण किए गए थे।

हम # = 7 सेट करके चरण 7 पर आगे बढ़ते हैं, जो स्वचालित रूप से अगले अक्षर को a , सभी पत्तियों के किनारों पर स्वचालित रूप से जोड़ता है। फिर हम सक्रिय बिंदु (रूट) में नया अंतिम वर्ण डालने का प्रयास करते हैं, और पाते हैं कि यह पहले से ही है। इसलिए हम कुछ भी डालने के बिना वर्तमान चरण को समाप्त करते हैं और सक्रिय बिंदु को अपडेट करते हैं (root,'a',1)

चरण 8 , # = 8 में, हम b जोड़ते हैं, और जैसा कि पहले देखा गया है, इसका मतलब केवल हम सक्रिय बिंदु को अद्यतन करते हैं (root,'a',2) और remainder कुछ भी किए बिना remainder वृद्धि, क्योंकि b पहले से मौजूद है। हालांकि, हम देखते हैं (ओ (1) समय में) कि सक्रिय बिंदु अब किनारे के अंत में है। हम इसे फिर से सेट करके इसे प्रतिबिंबित करते हैं (node1,'\0x',0) । यहां, मैं नोड एज का उपयोग करने के लिए नोड 1 का उपयोग करता हूं।

फिर, चरण # = 9 में , हमें 'सी' डालना होगा और इससे हमें अंतिम चाल को समझने में मदद मिलेगी:

दूसरा एक्सटेंशन: प्रत्यय लिंक का उपयोग करना

हमेशा के रूप में, # अद्यतन स्वचालित रूप से पत्ती किनारों पर c जोड़ता है और हम सक्रिय बिंदु पर जाते हैं यह देखने के लिए कि क्या हम 'सी' डाल सकते हैं। यह पता चला है कि 'सी' पहले से ही उस किनारे पर मौजूद है, इसलिए हमने सक्रिय बिंदु (node1,'c',1) , remainder वृद्धि और कुछ और नहीं किया है।

अब चरण # = 10 में , remainder is 4 , और इसलिए हमें सक्रिय बिंदु पर d डालने से पहले abcd (जो 3 चरणों पहले से बनी हुई है) डालने की आवश्यकता है।

सक्रिय बिंदु पर d डालने का प्रयास करने से ओ (1) समय में किनारे का विभाजन होता है:

active_node , जिसमें से विभाजन शुरू किया गया था, ऊपर लाल रंग में चिह्नित है। अंतिम नियम यहां है, नियम 3:

एक active_node से किनारे को विभाजित करने के बाद जो रूट नोड नहीं है, हम उस नोड से बाहर होने वाले प्रत्यय लिंक का पालन करते हैं, यदि कोई है, और active_node को नोड पर रीसेट करें। यदि कोई प्रत्यय लिंक नहीं है, तो हम active_node को रूट पर सेट करते हैं। active_edge और active_length अपरिवर्तित रहते हैं।

तो सक्रिय बिंदु अब (node2,'c',1) , और node2 नीचे लाल रंग में चिह्नित है:

चूंकि abcd का सम्मिलन पूरा हो गया है, इसलिए हम remainder 3 तक घटाते हैं और वर्तमान चरण के अगले शेष प्रत्यय पर विचार करते हैं, bcd । नियम 3 ने सक्रिय बिंदु को केवल सही नोड और किनारे पर सेट किया है ताकि bcd को सक्रिय बिंदु पर अपने अंतिम चरित्र d को डालने से किया जा सके।

ऐसा करने से दूसरा किनारा विभाजित होता है, और नियम 2 के कारण , हमें पहले डाले गए नोड से एक प्रत्यय लिंक बनाना होगा:

हम देखते हैं: प्रत्यय लिंक हमें सक्रिय बिंदु को रीसेट करने में सक्षम करते हैं ताकि हम ओ (1) प्रयास में अगले शेष डालने को सक्षम कर सकें। यह पुष्टि करने के लिए उपरोक्त आलेख को देखें कि वास्तव में लेबल ab पर नोड b (इसके प्रत्यय) पर नोड से जुड़ा हुआ है, और abc पर नोड bc से जुड़ा हुआ है।

वर्तमान चरण अभी तक समाप्त नहीं हुआ है। remainder अब 2 है, और हमें फिर से सक्रिय बिंदु को रीसेट करने के लिए नियम 3 का पालन करना होगा। चूंकि वर्तमान active_node (ऊपर लाल) में कोई प्रत्यय लिंक नहीं है, इसलिए हम रूट पर रीसेट करते हैं। सक्रिय बिंदु अब है (root,'c',1)

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

और चूंकि इसमें एक नया आंतरिक नोड बनाने का समावेश है, हम नियम 2 का पालन करते हैं और पहले बनाए गए आंतरिक नोड से एक नया प्रत्यय लिंक सेट करते हैं:

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

इसके साथ, remainder को 1 पर सेट किया जा सकता है और चूंकि active_node रूट है, इसलिए हम सक्रिय बिंदु को अद्यतन करने के लिए नियम 1 का उपयोग करते हैं (root,'d',0) । इसका मतलब है कि वर्तमान चरण का अंतिम सम्मिलन रूट पर एक d डालना है:

वह अंतिम चरण था और हम कर रहे हैं। अंतिम अवलोकनों की संख्या है, हालांकि:

  • प्रत्येक चरण में हम # आगे बढ़कर 1 स्थान पर जाते हैं। यह स्वचालित रूप से ओ (1) समय में सभी पत्ते नोड्स को अद्यतन करता है।

  • लेकिन यह किसी के साथ सौदा नहीं करता है) पिछले चरणों से शेष किसी भी प्रत्यय, और बी) वर्तमान चरण के एक अंतिम चरित्र के साथ।

  • remainder हमें बताता है कि हमें कितने अतिरिक्त आवेषण करने की आवश्यकता है। ये आवेषण स्ट्रिंग के अंतिम प्रत्यय में एक से एक के अनुरूप होते हैं जो वर्तमान स्थिति # पर समाप्त होता है। हम एक के बाद एक पर विचार करते हैं और डालने के लिए। महत्वपूर्ण: प्रत्येक सम्मिलन ओ (1) समय में किया जाता है क्योंकि सक्रिय बिंदु हमें बताता है कि कहां जाना है, और हमें सक्रिय बिंदु पर केवल एक ही वर्ण जोड़ने की आवश्यकता है। क्यूं कर? क्योंकि अन्य पात्रों को निहित रूप से निहित किया जाता है (अन्यथा सक्रिय बिंदु यह नहीं होगा)।

  • इस तरह के प्रत्येक सम्मिलन के बाद, हम remainder कमी करते हैं और यदि कोई है तो प्रत्यय लिंक का पालन करें। यदि नहीं तो हम रूट (नियम 3) पर जाते हैं। यदि हम पहले से ही रूट पर हैं, तो हम नियम 1 का उपयोग कर सक्रिय बिंदु को संशोधित करते हैं। किसी भी मामले में, केवल ओ (1) समय लगता है।

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

  • क्या होगा यदि एल्गोरिदम remainder के अंत में> 0? यह तब भी होगा जब टेक्स्ट का अंत एक सबस्ट्रिंग होता है जो कहीं पहले हुआ था। उस स्थिति में हमें स्ट्रिंग के अंत में एक अतिरिक्त चरित्र जोड़ना चाहिए जो पहले नहीं हुआ है। साहित्य में, आम तौर पर डॉलर का चिह्न $ उस के प्रतीक के रूप में उपयोग किया जाता है। यह तथ्य इतना मायने क्यों रखता हे? -> यदि बाद में हम प्रत्यय की खोज के लिए पूर्ण प्रत्यय पेड़ का उपयोग करते हैं, तो हमें केवल पत्ते पर समाप्त होने पर ही मैचों को स्वीकार करना होगा। अन्यथा हमें बहुत सारे नकली मैच मिलेंगे, क्योंकि पेड़ में निहित कई तार हैं जो मुख्य स्ट्रिंग के वास्तविक प्रत्यय नहीं हैं। अंत में remainder 0 को मजबूर करना अनिवार्य रूप से यह सुनिश्चित करने का एक तरीका है कि सभी प्रत्यय एक पत्ता नोड पर समाप्त होते हैं। हालांकि, अगर हम सामान्य सबस्ट्रिंग्स को खोजने के लिए पेड़ का उपयोग करना चाहते हैं, न केवल मुख्य स्ट्रिंग के प्रत्यय , यह अंतिम चरण वास्तव में आवश्यक नहीं है, जैसा कि नीचे ओपी की टिप्पणी द्वारा सुझाया गया है।

  • तो पूरे एल्गोरिदम की जटिलता क्या है? यदि पाठ लंबाई में एन वर्ण है, तो स्पष्ट रूप से एन चरण (या एन + 1 अगर हम डॉलर चिह्न जोड़ते हैं) हैं। प्रत्येक चरण में हम या तो कुछ भी नहीं करते हैं (वेरिएबल्स को अपडेट करने के अलावा), या हम remainder आवेषण करते हैं, प्रत्येक ओ (1) समय लेते हैं। चूंकि remainder इंगित करता है कि हमने पिछले चरणों में कितनी बार कुछ नहीं किया है, और अब हम जो भी सम्मिलित करते हैं, उसके लिए कम किया गया है, हम जो कुछ भी करते हैं, वह बिल्कुल एन (या एन + 1) है। इसलिए, कुल जटिलता ओ (एन) है।

  • हालांकि, एक छोटी सी चीज है जिसे मैंने सही ढंग से समझाया नहीं है: ऐसा हो सकता है कि हम एक प्रत्यय लिंक का पालन करें, सक्रिय बिंदु अपडेट करें, और उसके बाद यह पता लगाएं कि इसका active_length घटक नया active_node साथ अच्छी तरह से काम नहीं करता है। उदाहरण के लिए, इस तरह की स्थिति पर विचार करें:

(धराशायी रेखाएं बाकी पेड़ को इंगित करती हैं। बिंदीदार रेखा एक प्रत्यय लिंक है।)

अब सक्रिय बिंदु (red,'d',3) , इसलिए यह defg किनारे पर f पीछे की जगह को defg है। अब मान लें कि हमने आवश्यक अपडेट किए हैं और अब नियम 3 के अनुसार सक्रिय बिंदु को अद्यतन करने के लिए प्रत्यय लिंक का पालन करें। नया सक्रिय बिंदु (green,'d',3) । हालांकि, हरे नोड से बाहर जाने वाला d डीज de , इसलिए इसमें केवल 2 अक्षर हैं। सही सक्रिय बिंदु खोजने के लिए, हमें स्पष्ट रूप से नीले नोड पर उस किनारे का पालन करने और (blue,'f',1) रीसेट करने की आवश्यकता है।

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

नहीं। कारण यह है कि अगर हमें वास्तव में सक्रिय बिंदु को समायोजित करना है (उदाहरण के लिए हरे से नीले रंग के ऊपर), जो हमें एक नए नोड में लाता है जिसमें इसका अपना प्रत्यय लिंक होता है, और active_length कम हो जाएगा। चूंकि हम प्रत्यय लिंक की श्रृंखला का पालन करते हैं, हम शेष आवेषण करते हैं, active_length केवल कम हो सकता है, और जिस तरह से हम सक्रिय कर सकते हैं सक्रिय-बिंदु समायोजन की संख्या किसी भी समय active_length से बड़ी नहीं हो सकती है। चूंकि active_length remainder से बड़ा कभी नहीं हो सकता है, और remainder केवल ओ (एन) न केवल प्रत्येक चरण में है, लेकिन पूरी प्रक्रिया के दौरान remainder तक किए गए वेतन वृद्धि की कुल राशि ओ (एन) भी है, इसकी संख्या सक्रिय बिंदु समायोजन भी ओ (एन) द्वारा बाध्य है।

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

स्टैक ओवरफ़्लो पर इस एल्गोरिदम का एक चरण-दर-चरण स्पष्टीकरण मेरे अलावा कई अन्य लोगों के लिए अमूल्य होगा, मुझे यकीन है।

संदर्भ के लिए, यहां एल्गोरिदम पर Ukkonen का पेपर है: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

मेरी मूल समझ, अब तक:

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

मूल एल्गोरिदम ओ (एन 2 ) प्रतीत होता है, जैसा कि अधिकांश स्पष्टीकरणों में इंगित किया गया है, क्योंकि हमें सभी उपसर्गों के माध्यम से कदम उठाने की आवश्यकता है, फिर हमें प्रत्येक उपसर्ग के लिए प्रत्येक प्रत्यय के माध्यम से कदम उठाने की आवश्यकता है। Ukkonen का एल्गोरिदम स्पष्ट रूप से अद्वितीय है क्योंकि वह प्रत्यय सूचक तकनीक का उपयोग करता है, हालांकि मुझे लगता है कि मुझे समझ में परेशानी हो रही है।

मुझे समझ में भी परेशानी हो रही है:

  • वास्तव में कब और कैसे "सक्रिय बिंदु" असाइन किया जाता है, उपयोग और बदला जाता है
  • एल्गोरिदम के कैनोनाइजेशन पहलू के साथ क्या चल रहा है
  • मैंने जो कार्यान्वयन देखा है, वे बाध्यकारी वेरिएबल्स को "ठीक" करने की आवश्यकता क्यों हैं जिनका उपयोग वे कर रहे हैं

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

https://gist.github.com/2373868

2017-11-04 अपडेट करें

कई सालों बाद मुझे प्रत्यय पेड़ के लिए एक नया उपयोग मिला है, और जावास्क्रिप्ट में एल्गोरिदम लागू किया है। जिस्ट नीचे है। यह बग-मुक्त होना चाहिए। इसे एक जेएस फ़ाइल में डंप करें, npm उसी स्थान से npm install chalk , और फिर कुछ रंगीन आउटपुट देखने के लिए node.js के साथ चलाएं। डिबगिंग कोड के बिना, एक ही गिस्ट में एक अलग संस्करण है।

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6


मेरा अंतर्ज्ञान निम्नानुसार है:

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

शुरुआत में, इसका मतलब है कि प्रत्यय पेड़ में एक रूट रूट नोड होता है जो पूरे स्ट्रिंग का प्रतिनिधित्व करता है (यह केवल एक ही प्रत्यय है जो 0 से शुरू होता है)।

लेन (स्ट्रिंग) पुनरावृत्तियों के बाद आपके पास एक प्रत्यय वृक्ष होता है जिसमें सभी प्रत्यय होते हैं।

लूप के दौरान कुंजी सक्रिय बिंदु है। मेरा अनुमान है कि यह प्रत्यय पेड़ में गहरे बिंदु का प्रतिनिधित्व करता है जो स्ट्रिंग के पहले के वर्णों के उचित प्रत्यय से मेल खाता है। (मुझे लगता है कि उचित मतलब है कि प्रत्यय पूरी स्ट्रिंग नहीं हो सकती है।)

उदाहरण के लिए, मान लीजिए कि आपने अक्षर 'abcabc' देखा है। सक्रिय बिंदु प्रत्यय 'abc' के अनुरूप पेड़ में बिंदु का प्रतिनिधित्व करेगा।

सक्रिय बिंदु (मूल, पहला, अंतिम) द्वारा दर्शाया गया है। इसका मतलब यह है कि आप वर्तमान में पेड़ के बिंदु पर हैं जो आपको नोड मूल से शुरू करके और स्ट्रिंग में वर्णों में खिलाकर [पहले: आखिरी]

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

नोट 1: प्रत्यय पॉइंटर्स प्रत्येक नोड के लिए अगले सबसे छोटे मैच का लिंक देते हैं।

नोट 2: जब आप कोई नया नोड और फ़ॉलबैक जोड़ते हैं तो आप नए नोड के लिए एक नया प्रत्यय सूचक जोड़ते हैं। इस प्रत्यय सूचक के लिए गंतव्य संक्षिप्त सक्रिय बिंदु पर नोड होगा। यह नोड या तो पहले से मौजूद होगा, या इस फ़ॉलबैक लूप के अगले पुनरावृत्ति पर बनाया जाएगा।

नोट 3: कैनोनाइजेशन भाग सक्रिय बिंदु की जांच में समय बचाता है। उदाहरण के लिए, मान लीजिए कि आपने हमेशा मूल = 0 का उपयोग किया है, और बस पहले और आखिरी बार बदल दिया है। सक्रिय बिंदु की जांच करने के लिए आपको हर इंटरमीडिएट नोड्स के साथ हर बार प्रत्यय पेड़ का पालन करना होगा। आखिरी नोड से दूरी रिकॉर्ड करके इस पथ का पालन करने के परिणाम को कैश करना समझ में आता है।

क्या आप "फिक्स" बाउंडिंग वैरिएबल द्वारा क्या मतलब है इसका एक कोड उदाहरण दे सकते हैं?

स्वास्थ्य चेतावनी: मुझे यह एल्गोरिदम भी समझने में विशेष रूप से कठिन पाया गया है, इसलिए कृपया यह समझें कि यह अंतर्ज्ञान सभी महत्वपूर्ण विवरणों में गलत होने की संभावना है ...


@jogojapan द्वारा अच्छी तरह से समझाया गया ट्यूटोरियल के लिए धन्यवाद, मैंने पायथन में एल्गोरिदम लागू किया।

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

  1. Remainder > 0 साथ समाप्त करें Remainder > 0 यह पता चला है कि यह स्थिति पूरे एल्गोरिदम के अंत में नहीं, आने वाले चरण के दौरान भी हो सकती है। जब ऐसा होता है, तो हम शेष, एक्टनोड, एक्टेज, और एक्टलाइंड अपरिवर्तित छोड़ सकते हैं , वर्तमान प्रकट चरण को समाप्त कर सकते हैं, और मूल स्ट्रिंग में अगला चार वर्तमान पथ पर निर्भर करते हुए या तो फोल्डिंग या प्रकट होने के द्वारा एक और चरण शुरू कर सकते हैं या नहीं।

  2. नोड्स पर लीप करें: जब हम एक प्रत्यय लिंक का पालन करते हैं, तो सक्रिय बिंदु अपडेट करें, और उसके बाद यह पता लगाएं कि इसका सक्रिय_लेथ घटक नया सक्रिय_नोड के साथ अच्छी तरह से काम नहीं करता है। हमें विभाजित करने या पत्ते डालने के लिए सही जगह पर आगे बढ़ना होगा। This process might be not that straightforward because during the moving the actlength and actedge keep changing all the way, when you have to move back to the root node , the actedge and actlength could be wrong because of those moves. We need additional variable(s) to keep that information.

The other two problems have somehow been pointed out by @managonov

  1. Split Could Degenerate When trying to split an edge, sometime you'll find the split operation is right on a node. That case we only need add a new leaf to that node, take it as a standard edge split operation, which means the suffix links if there's any, should be maintained correspondingly.

  2. Hidden Suffix Links There is another special case which is incurred by problem 1 and problem 2 . Sometimes we need to hop over several nodes to the right point for split, we might surpass the right point if we move by comparing the remainder string and the path labels. That case the suffix link will be neglected unintentionally, if there should be any. This could be avoided by remembering the right point when moving forward. The suffix link should be maintained if the split node already exists, or even the problem 1 happens during a unfolding step.

Finally, my implementation in Python is as follows:

Tips: It includes a naive tree printing function in the code above, which is very important while debugging . It saved me a lot of time and is convenient for locating special cases.


@jogojapan you brought awesome explanation and visualisation. But as @makagonov mentioned it's missing some rules regarding setting suffix links. It's visible in nice way when going step by step on http://brenden.github.io/ukkonen-animation/ through word 'aabaaabb'. When you go from step 10 to step 11, there is no suffix link from node 5 to node 2 but active point suddenly moves there.

@makagonov since I live in Java world I also tried to follow your implementation to grasp ST building workflow but it was hard to me because of:

  • combining edges with nodes
  • using index pointers instead of references
  • breaks statements;
  • continue statements;

So I ended up with such implementation in Java which I hope reflects all steps in clearer way and will reduce learning time for other Java people:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}




suffix-tree