मैं एक तेजी से suffix-array निर्माण एल्गोरिदम खोज रहा हूं। मैं एसिम्प्टोटिक जटिलता की तुलना में कार्यान्वयन और कच्ची गति में आसानी से अधिक रुचि रखता हूं (मुझे पता है कि एक प्रत्यय सरणी ओ (एन) समय में एक प्रत्यय पेड़ के माध्यम से बनाई जा सकती है, लेकिन इसमें बहुत अधिक जगह होती है; जाहिर है कि अन्य एल्गोरिदम हैं बुरी सबसे बुरी स्थिति बड़ी-जटिलता, लेकिन अभ्यास में काफी तेजी से चलती है)। मुझे एल्गोरिदम नहीं लगता है जो एक उप-उत्पाद के रूप में एक एलसीपी सरणी उत्पन्न करता है, क्योंकि मुझे अपने उद्देश्यों के लिए वैसे भी एक की आवश्यकता है।वर्तमान अत्याधुनिक प्रत्यय सरणी निर्माण एल्गोरिदम क्या है?
मुझे taxonomy of various suffix array construction algorithms मिला, लेकिन यह पुराना है। मैंने SA-IS, qsufsort, और BPR के बारे में सुना है, लेकिन मुझे वास्तव में नहीं पता कि वे एक दूसरे से तुलना कैसे करते हैं, न ही यदि बेहतर एल्गोरिदम भी हैं। इस बात पर विचार करते हुए कि प्रत्यय-सरणी फ़ील्ड कितनी गर्म है, मुझे उम्मीद है कि कुछ अन्य एल्गोरिदम ने प्रकाशित होने के बाद से उन्हें हटा दिया है। मुझे लगता है कि "विभाजित" नामक एक तेज एल्गोरिदम का वर्णन करने वाले पेपर में आना याद है, लेकिन मुझे अब मेरे जीवन के लिए यह नहीं मिल रहा है।
तो, कला की वर्तमान स्थिति क्या है? आदर्श रूप से, मुझे वर्तमान सर्वोत्तम एल्गोरिदम की एक छोटी सूची चाहिए (लिंक के साथ, यदि संभव हो) और उनकी सापेक्ष ताकत और कमजोरियों का त्वरित अवलोकन।
चीयर्स :-) इसके लिए धन्यवाद, यह सबसे प्रबुद्ध है। मुझे नहीं लगता कि आपको पता होना चाहिए कि "विभाजित" एसएसीए क्या है? (मुझे यह नहीं पता कि मैंने इसे कहाँ देखा है, और खोज निष्पक्ष साबित हो रही हैं) – Cameron
आह, मुझे अंत में "विभाजन" मिला: इसका उल्लेख [इस पेपर] में है (http://goanna.cs.rmit.edu.au/~ sjp/awoca2006.pdf), MS4Sort एल्गोरिदम के लिए उपनाम के रूप में खंड 4 – Cameron