प्रत्यय पेड़ और कोशिशें। अंतर क्या है?

Question

मैं लगभग Tries पढ़ रहा हूं जिसे आमतौर पर उपसर्ग पेड़ और Suffix Trees के नाम से जाना जाता है।
हालांकि मुझे Trie के लिए कोड मिला है, मुझे Suffix Tree के लिए कोई उदाहरण नहीं मिल रहा है। मुझे यह भी महसूस हो रहा है कि Trie बनाने वाला कोड Suffix Tree के लिए एक जैसा अंतर है, जो कि पहले मामले में हम उपसर्गों को संग्रहित करते हैं लेकिन बाद के प्रत्यय में।
क्या यह सच है? क्या कोई मुझे अपने सिर में इसे साफ़ करने में मदद कर सकता है? एक उदाहरण कोड बहुत मदद मिलेगी!

Answer 1

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

banana 
anana 
nana 
ana 
na 
a 

एक बार है कि आप किसी भी एन-ग्राम के लिए खोज और अगर देख सकते हैं किया है यह आपकी अनुक्रमित स्ट्रिंग में मौजूद है। दूसरे शब्दों में, एन-ग्राम खोज आपकी स्ट्रिंग के सभी संभावित प्रत्यय की एक उपसर्ग खोज है।

यह प्रत्यय पेड़ बनाने का सबसे सरल और धीमा तरीका है। यह पता चला है कि इस डेटा संरचना पर कई प्रशंसक भिन्नताएं हैं जो या तो दोनों या दोनों जगहों पर सुधार करती हैं और समय बनाती हैं। मुझे इस डोमेन में एक सिंहावलोकन देने के लिए पर्याप्त जानकारी नहीं है लेकिन आप suffix arrays या इस कक्षा advanced data structures (व्याख्यान 16 और 18) देखकर शुरू कर सकते हैं।

यह answer भी इस डेटा-संरचना के एक संस्करण को समझाते हुए एक अद्भुत काम करता है।

Answer 2

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

लेकिन इस बेवकूफ दृष्टिकोण का उपयोग करके, आकार के एक स्ट्रिंग के लिए इस पेड़ का निर्माण ओ (एन^2) होगा और बहुत सारी मेमोरी लेंगी।

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

Answer 3

अंतर बहुत आसान है। प्रत्यय के पेड़ की तुलना में एक प्रत्यय पेड़ में कम "डमी" नोड्स होते हैं। ये डमी नोड्स एकल वर्ण हैं जो पेड़ पर लुकअप ऑपरेशन को बढ़ाते हैं