स्ट्रिंग अनुक्रमणिका संरचनाएँ

स्ट्रिंग अनुक्रमणिका संरचनाएँ एक टेक्स्ट को खोज योग्य रूप में पूर्व-संसाधित करती हैं — जैसे ट्राई, सफिक्स ट्री, या सफिक्स ऐरे — ताकि बाद में कई पैटर्न क्वेरी, और दोहराव तथा सामान्य सबस्ट्रिंग के बारे में प्रश्नों का तुरंत उत्तर दिया जा सके।

Definition

एक स्ट्रिंग अनुक्रमणिका संरचना एक टेक्स्ट (या स्ट्रिंग के सेट) से निर्मित एक डेटा संरचना है जो टेक्स्ट के बारे में कुशल क्वेरी का समर्थन करती है — जैसे कि कोई पैटर्न कब और कहाँ होता है, सबसे लंबी दोहराई गई सबस्ट्रिंग, या दो टेक्स्ट की सबसे लंबी सामान्य सबस्ट्रिंग — आमतौर पर टेक्स्ट के प्रीफिक्स या सफिक्स का प्रतिनिधित्व करके।

Scope

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

Core questions

• एक ट्राई प्रीफिक्स-आधारित खोज के लिए स्ट्रिंग के एक सेट को कैसे व्यवस्थित करता है?
• एक सफिक्स ट्री सभी सफिक्स का प्रतिनिधित्व कैसे करता है ताकि पैटर्न क्वेरी में पैटर्न की लंबाई के अनुपात में समय लगे?
• सफिक्स ऐरे कम मेमोरी के साथ समान शक्ति कैसे प्राप्त करते हैं?
• कौन से निर्माण एल्गोरिदम इन संरचनाओं को कुशलता से बनाते हैं, आदर्श रूप से लीनियर समय में?
• ये इंडेक्स किन टेक्स्ट समस्याओं (दोहराव, सामान्य सबस्ट्रिंग) को सुरुचिपूर्ण ढंग से हल करते हैं?

Key concepts

• ट्राई (प्रीफिक्स ट्री)
• सफिक्स ट्री
• सफिक्स ऐरे
• लॉन्गेस्ट-कॉमन-प्रीफिक्स ऐरे
• ऑन-लाइन निर्माण
• सबसे लंबी दोहराई गई सबस्ट्रिंग
• सबसे लंबी सामान्य सबस्ट्रिंग
• स्पेस-टाइम ट्रेड-ऑफ

Key theories

सफिक्स ट्री और लीनियर-टाइम निर्माण

एक सफिक्स ट्री एक टेक्स्ट के प्रत्येक सफिक्स का संक्षिप्त रूप से प्रतिनिधित्व करता है, जिससे पैटर्न को उसकी लंबाई के अनुपात में समय में खोजा जा सकता है; उकोनेन का एल्गोरिदम इसे टेक्स्ट की लंबाई के लीनियर समय में ऑन-लाइन बनाता है।

स्पेस-कुशल इंडेक्स के रूप में सफिक्स ऐरे

एक सफिक्स ऐरे एक साधारण पूर्णांक ऐरे में सभी सफिक्स के सॉर्ट किए गए क्रम को संग्रहीत करता है; लॉन्गेस्ट-कॉमन-प्रीफिक्स ऐरे के साथ मिलकर यह सफिक्स ट्री की तुलना में बहुत कम मेमोरी का उपयोग करके तेजी से पैटर्न खोज का समर्थन करता है।

Clinical relevance

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

History

पीटर वेनर ने 1973 में सफिक्स ट्री पेश किए, जिसमें मैकक्रेइट (1976) और उकोनेन (1995) द्वारा सरल लीनियर-टाइम निर्माण किए गए। मैनबर और मायर्स ने 1990 में सफिक्स ऐरे को एक अधिक स्पेस-कुशल विकल्प के रूप में पेश किया, और बाद में संपीड़ित और एफएम-इंडेक्स पर किए गए काम ने इन विचारों को बहुत बड़े टेक्स्ट और जीनोम तक विस्तारित किया।

Key figures

• Peter Weiner
• Edward McCreight
• Esko Ukkonen
• Udi Manber
• Gene Myers
• Dan Gusfield

Seminal works

• ukkonen1995
• manber1993
• gusfield1997

Frequently asked questions

मुझे सफिक्स ट्री के बजाय सफिक्स ऐरे का उपयोग कब करना चाहिए?

सफिक्स ऐरे सफिक्स ट्री की तुलना में काफी कम मेमोरी का उपयोग करते हैं और उनमें अच्छा कैश व्यवहार होता है, जिससे वे जीनोम जैसे बड़े टेक्स्ट के लिए बेहतर होते हैं। सफिक्स ट्री अधिक संरचना को सीधे उजागर करते हैं और कुछ एल्गोरिदम को वैचारिक रूप से सरल बना सकते हैं, लेकिन उच्च स्पेस लागत पर; सफिक्स ऐरे और एक लॉन्गेस्ट-कॉमन-प्रीफिक्स ऐरे उस शक्ति का अधिकांश हिस्सा पुनः प्राप्त करते हैं।

एक ट्राई किस लिए अच्छा है?

एक ट्राई साझा प्रीफिक्स द्वारा स्ट्रिंग के एक सेट को संग्रहीत करता है, जिससे तेजी से प्रीफिक्स खोज, ऑटोकंप्लीशन और ऑर्डर किया गया ट्रैवर्सल मिलता है। यह शब्दकोशों, ऑटोकंप्लीट सुझावों और लॉन्गेस्ट-प्रीफिक्स मिलान के लिए अच्छी तरह से अनुकूल है जैसे आईपी रूटिंग में, जहाँ कुंजियाँ सामान्य शुरुआत साझा करती हैं।