प्रत्यय पेड़ बनाम प्रत्यय पेड़

Question

मैं बस जानना चाहता हूं, जब एक प्रत्यय पेड़ एक उन्नत प्रत्यय सरणी से बेहतर होता है।

Replacing suffix trees with enhanced suffix arrays पढ़ने के बाद मुझे अब प्रत्यय पेड़ों का उपयोग करने का कोई कारण नहीं दिख रहा है। कुछ विधियां जटिल हो सकती हैं, लेकिन आप प्रत्यय सरणी के साथ सब कुछ कर सकते हैं, आप प्रत्यय पेड़ के साथ क्या कर सकते हैं और आपको एक ही समय की जटिलता की आवश्यकता है लेकिन कम स्मृति।

ए survey ने यह भी दिखाया कि प्रत्यय सरणी तेज हैं, क्योंकि वे कैश मित्र हैं, और अधिक कैश मिस नहीं पैदा करते हैं, फिर प्रत्यय पेड़ (इसलिए कैश सरणी के उपयोग को बेहतर तरीके से भविष्यवाणी कर सकता है, फिर रिकर्सिव पर वृक्ष संरचना)।

तो, क्या किसी को प्रत्यय सरणी पर प्रत्यय वृक्ष चुनने का कोई कारण पता है?

संपादित ठीक है, आप जानते हैं कि अधिक मुझे बताओ, अब तक इसकी:

• Suffixarrays न ऑन लाइन निर्माण
• कुछ एल्गोरिदम मिलान पैटर्न Suffixtrees
पर तेजी से
• (जोड़ा चलाने की अनुमति देने के) ऑनलाइन निर्माण के कारण, आप इसे एचडी पर सहेज सकते हैं और एक मौजूदा प्रत्यय को बढ़ा सकते हैं। यदि आप एक एसएसडी का उपयोग करते हैं, तो यह भी तेजी से शांत होना चाहिए।

Answer 1

एसओ में इस विषय पर कुछ interesting thoughts हैं। आप लाइन पर उपलब्ध more technical material भी पा सकते हैं। another paper है जो इन संरचनाओं को लागू करने का एक और प्रभावी तरीका होने का दावा करते हुए आपके मुद्दों के साथ आपकी मदद कर सकता है।

मैं इस मुद्दे में एक विशेषज्ञ नहीं हूं, लेकिन ऐसा लगता है कि प्रत्यय सरणी कुछ हद तक धीमी हो सकती है, भले ही वे अधिक स्थान कुशल हों। फिर भी, उनमें से दोनों के बारे में अधिक विस्तृत होने के लिए मुझे व्यावहारिक अनुभव की कमी है।

Answer 2

एक और उदाहरण को दिखाने के लिए एक प्रत्यय पेड़ बेहतर है:

आप आसानी से एक प्रत्यय सरणी का निर्माण कर सकते हैं यदि आप एक प्रत्यय पेड़ पहले से ही है।

लेकिन प्रत्यय सरणी से प्रत्यय वृक्ष बनाने के लिए यह बहुत जटिल है।