सफिक्स ट्री

पाठ के लिए सफिक्स ट्री BANANA. प्रत्येक सबस्ट्रिंग को विशेष वर्ण के साथ समाप्त किया जाता है $. जड़ से पत्तियों तक के छह रास्ते (बक्से के रूप में दिखाए गए) छह सफिक्स के अनुरूप हैं A$, NA$, ANA$, NANA$, ANANA$ और BANANA$. पत्तों की संख्याएँ संबंधित सफिक्स की आरंभिक स्थिति बताती हैं। निर्माण के दौरान धराशायी खींचे गए सफिक्स लिंक का उपयोग किया जाता है।

कंप्यूटर विज्ञान में, एक सफिक्स ट्री (पीएटी ट्री या पहले के रूप में पोजीशन ट्री के रूप में भी जाना जाता है) दिए गए पाठ के सभी सफिक्स को उनकी कुंजी और पाठ में उनकी स्थानों को उनके मान के रूप में संग्रहीत करने वाला एक सकसिंक्ट ट्राई होता है। ससफिक्स ट्री कई महत्वपूर्ण स्ट्रिंग ऑपरेशनों के विशेष रूप से तेज़ कार्यान्वयन की अनुमति देते हैं।

इस प्रकार के एक ट्री का निर्माण $S$ स्ट्रिंग के लिए $S$ की लंबाई में समय और स्थान लीनियर होता है। एक बार निर्मित होने के बाद, कई ऑपरेशन तेजी से किए जा सकते हैं, उदाहरण के लिए $S$ में एक सबस्ट्रिंग के स्थान को ज्ञात करना, यदि एक निश्चित संख्या की गलतियों की अनुमति हो, एक नियमित व्यंजक (रेगुलर एक्सप्रेशन) पैटर्न के लिए मिलान करना इत्यादि। सफेक्स ट्रीज़ ने दीर्घतम सामान्य सबस्ट्रिंग समस्या के लिए पहले से ही लीनियर समय के समाधानों में से एक प्रदान किया। ये गति वृद्धि का लाभ है: एक स्ट्रिंग के सफिक्स ट्री को संग्रहीत करने के लिए सामान्यतः स्ट्रिंग की तुलना में बहुत अधिक स्थान की आवश्यकता होती है।

इतिहास

यह अवधारणा पहली बार वेनर (1973) द्वारा प्रस्तुत की गई थी। सफिक्स $S[i..n]$ के बजाय, वेनर ने अपने ट्राई में प्रत्येक स्थान के लिए प्रीफिक्स आइडेंटिफायर संग्रहित की, अर्थात्, $i$ से प्रारंभ होने और $S$ में केवल एक बार होने वाली सबसे छोटी स्ट्रिंग होती है। उनका एल्गोरिदम डी$S[k+1..n]$ के लिए असम्पीडित (अनकप्रेस्सेड) ट्राई को लेता है और इसे $S[k..n]$ के लिए एक ट्राई में बढ़ाता है। इस विधि से, ट्राईवियल ट्राई से $S[n..n]$ के लिए ट्राई को $S[1..n]$ के लिए एल्गोरिदम डी को $n-1$ लगातार कॉल करके बनाया जा सकता है; हालांकि, कुल मान्य समय $O(n^{2})$ होता है। वेनर का एल्गोरिदम बी कई सहायक डेटा संरचनाओं को बनाए रखने के लिए उपयोग करता है, जिससे निर्मित ट्राई के साइज़ में संगठन का चलन औसत करार दिया जा सकता है। यह अंतिम रूप से $O(n^{2})$ नोड हो सकता है, जैसे $S=a^{n}b^{n}a^{n}b^{n}\$.$ के लिए। वेनर का एल्गोरिदम सी अंततः संपीडित ट्राई का उपयोग करता है, जिससे साइज़ और संचालन का चलन लीनियर समग्र संचय साइज़ और समय होता है। डोनाल्ड नुथ ने इसे बाद में "वर्ष 1973 का एल्गोरिदम" के रूप में वर्णनित किया। पाठग्रंथ एएचओ, होपक्रॉफ्ट & उल्मन (1974, Sect.9.5) ने वेनर के परिणामों को सरल और और सुंदर रूप में पुनर्जीवित किया, पोजीशन ट्री के शब्द का परिचय कराया।

मैकक्रेइट (1976) $S$ के सभी सफिक्स की एक (संपीड़ित (कंप्रेस्ड)) ट्राई बनाने वाले पहले व्यक्ति थे। हालाँकि $i$ से शुरू होने वाला सफिक्स सामान्यतः प्रीफिक्स आइडेंटिफायर से अधिक लंबा होता है, संपीड़ित ट्राई में उनका पथ प्रतिनिधित्व साइज़ में भिन्न नहीं होता है। दूसरी ओर, मैकक्रेइट वेनर की अधिकांश सहायक डेटा संरचनाओं से दूर रह सकता है; केवल सफिक्स लिंक बचे हैं।

यूकोनेन (1995) ने निर्माण को और भी सरल बनाया। उन्होंने सफिक्स ट्री का पहला ऑनलाइन निर्माण प्रदान किया, जिसे अब यूकोनेन का एल्गोरिदम के रूप में जाना जाता है, जिसका चलन समय उस समय के सबसे तेज़ एल्गोरिदमों के साथ मेल खाता था। ये एल्गोरिदम सभी स्थिर-साइज वर्णमाला के लिए लीनियर-समय के होते हैं, और सामान्यतः $O(n\log n)$ का अत्यंत चलन समय होता है।

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

परिभाषा

लंबाई $n$ की स्ट्रिंग $S$ के लिए सफिक्स ट्री को एक ट्री के रूप में परिभाषित किया गया है:

• ट्री में यथार्थ n लीव्स होती हैं, जिन्हें $1$ से $n$ तक क्रमांकित किया जाता है।
• रूट को छोड़कर, हर आंतरिक नोड में कम से कम दो चिल्ड्रन होते हैं।
• प्रत्येक किनारे को $S$ की एक गैर-रिक्त सबस्ट्रिंग के साथ लेबल किया गया है।
• किसी नोड से शुरू होने वाले किसी भी दो किनारों में समान वर्ण से शुरू होने वाले स्ट्रिंग-लेबल नहीं हो सकते हैं।
• रूट से लीव्स $S[i..n]$ तक के पथ पर पाए जाने वाले सभी स्ट्रिंग-लेबलों को संयोजित करके प्राप्त स्ट्रिंग, सफिक्स $i$ का उच्चारण करती है, $i$ के लिए $1$ से $n$ तक।

ऐसे एक ट्री के लिए जो सभी स्ट्रिंग के लिए विद्यमान नहीं होता है, $S$ को स्ट्रिंग में देखे जाने वाले टर्मिनल सिम्बल (सामान्यतः $ के रूप में दर्शाया जाता है) के साथ पैड किया जाता है। इससे सुनिश्चित होता है कि कोई सफिक्स किसी अन्य सफिक्स का प्रत्यय नहीं होगा, और कुल में $n$ लीव्स नोड होंगे, $S$ के $n$ सफिक्स के प्रत्येक के लिए एक होंगे। मूल से भिन्न आंतरिक नोड सभी ब्रांचिंग होने के कारण, अधिकतम n - 1 ऐसे नोड हो सकते हैं, और कुल n + (n - 1) + 1 = 2n नोड होंगे (n पत्तियाँ, n - 1 आंतरिक गैर-मूल नोड, 1 मूल)।

सफिक्स लिंक पुरातर लीनियर समय के निर्माण एल्गोरिदमों के लिए एक मुख्य सुविधा हैं, हालांकि अधिकांश नवीनतम एल्गोरिदम, जो फराक एल्गोरिदम पर आधारित हैं, सफिक्स लिंक के बिना काम करते हैं। पूर्ण सफिक्स ट्री में, सभी आंतरिक गैर-रूट नोड्स के पास एक सफिक्स लिंक होता है जो दूसरे आंतरिक नोड की ओर जाता है। यदि रूट से एक नोड तक का पथ $\chi \alpha$ स्ट्रिंग को बनाता है, जहां $\chi$ एकल अक्षर है और $\alpha$ एक स्ट्रिंग है (संभवतः रिक्त), तो इसके पास सफिक्स लिंक होता है जो $\alpha$ को प्रतिनिधित्व करने वाले आंतरिक नोड की ओर जाता है। ऊपर दिए गए आकृति में ANAके नोड से NA के नोड के लिए सफिक्स लिंक देखें। सफिक्स लिंक भी ट्री पर चल रहे कुछ एल्गोरिदमों में उपयोग किए जाते हैं।

सामान्यीकृत सफिक्स ट्री एक सफिक्स ट्री होता है जो एकल स्ट्रिंग के बजाय स्ट्रिंग के एक सेट के लिए बनाया गया है। यह तारों के इस सेट से सभी सफिक्स का प्रतिनिधित्व करता है। प्रत्येक स्ट्रिंग को एक अलग समाप्ति चिह्न द्वारा समाप्त किया जाना चाहिए।

कार्यक्षमता

लंबाई $n$ की स्ट्रिंग $S$ के लिए एक सफिक्स ट्री $\Theta (n)$ समय में बनाया जा सकता है, यदि अक्षर बहुपद श्रेणी में पूर्णांकों के वर्णमाला से आते हैं (विशेष रूप से, यह स्थिर साइज़ के अक्षरों के लिए सच है)। बड़े वर्णमालाओं के लिए, चलन समय का मुख्य भाग पहले अक्षरों को सॉर्ट करके उन्हें साइज़ $O(n)$ के रेंज में लाने का होता है; सामान्यतः, इसके लिए $O(n\log n)$ समय लगता है। नीचे दी गई लागत इस धारणा के अंतर्गत दी गई है कि वर्णमाला स्थिर है।

मान लें कि लंबाई $n$ की स्ट्रिंग $S$ के लिए सफिक्स ट्री बनाया गया है, या कुल लंबाई $n=n_{1}+n_{2}+\cdots +n_{K}$ की स्ट्रिंग $D=\{S_{1},S_{2},\dots ,S_{K}\}$ के सेट के लिए सामान्यीकृत सफिक्स ट्री बनाया गया है। आप यह कर सकते हैं:

• स्ट्रिंग के लिए खोजें:
  • $m$ लंबाई की एक स्ट्रिंग $P$ को $O(m)$ समय में उपस्थिति जांचें।
  • कुल लंबाई $m$ के पैटर्न $P_{1},\dots ,P_{q}$ की $O(m)$ बार में सबस्ट्रिंग के रूप में पहली घटना ज्ञात कीजिए।
  • (Work done)
  • $O(m+z)$ समय में सबस्ट्रिंग के रूप में कुल लंबाई $m$ के पैटर्न $P_{1},\dots ,P_{q}$ की सभी $z$ घटनाएँ ज्ञात करें।
  • $n$ में अपेक्षित सबलाइनियर टाइम में एक नियमित अभिव्यक्ति पी खोजें।
  • पैटर्न $P$ के प्रत्येक सफिक्स के लिए, $\Theta (m)$ समय में $P[i\dots m]$ के प्रीफिक्स और $D$ में एक सबस्ट्रिंग के बीच सबसे लंबे मिलान की लंबाई ज्ञात करें। इसे $P$ के मिलान आँकड़े कहा जाता है।
• स्ट्रिंग्स के गुण खोजें:
  • $\Theta (n_{i}+n_{j})$ बार में स्ट्रिंग $S_{i}$ और $S_{j}$ की सबसे लंबी सामान्य उपस्ट्रिंग्स खोजें।
  • $\Theta (n+z)$ समय में सभी अधिकतम जोड़े, अधिकतम दोहराव या सुपरमैक्सिमल दोहराव खोजें।
  • $\Theta (n)$ बार में लेम्पेल-ज़िव अपघटन का पता लगाएं।
  • $\Theta (n)$ बार में सबसे लंबे समय तक दोहराया जाने वाला सबस्ट्रिंग खोजें।
  • $\Theta (n)$ बार में न्यूनतम लंबाई की सबसे अधिक बार आने वाली सबस्ट्रिंग खोजें।
  • $\Sigma$ में से सबसे छोटी स्ट्रिंग खोजें जो $D$ में नहीं आती हैं, $O(n+z)$ समय में, यदि ऐसी $z$ स्ट्रिंग हैं।
  • $\Theta (n)$ बार में केवल एक बार आने वाली सबसे छोटी उपस्ट्रिंग ज्ञात कीजिए।
  • प्रत्येक $i$ के लिए, $\Theta (n)$ समय में $D$ में से $S_{i}$ की सबसे छोटी उपस्ट्रिंग खोजें जो कहीं और न हों।

सफिक्स ट्री को $\Theta (n)$ समय में नोड्स के बीच निरंतर समय न्यूनतम सामान्य पूर्वज पुनर्प्राप्ति के लिए तैयार किया जा सकता है। तब कोई भी यह कर सकता है:

$S_{j}[q..n_{j}]$ में सफिक्स $\Theta (1)$ और $S_{i}[p..n_{i}]$ के बीच सबसे लंबा सामान्य प्रीफिक्स खोजें।

$O(kn+z)$ बार में अधिकतम k बेमेल के साथ m लंबाई का एक पैटर्न P खोजें, जहां z हिट की संख्या है।

यदि लंबाई $g$ के अंतराल की अनुमति है, या $\Theta (kn)$ यदि $k$ बेमेल की विलोमपद अनुमति है, तो $\Theta (n)$, या $\Theta (gn)$ बार में सभी $z$ अधिकतम पैलिन्ड्रोम खोजें।

$O(n\log n+z)$ में सभी $z$ अग्रानुक्रम दोहराव खोजें, और के-बेमेल अग्रानुक्रम $O(kn\log(n/k)+z)$ में दोहराएँ।

$\Theta (n)$ समय में $k=2,\dots ,K$ के लिए $D$ में कम से कम $k$ स्ट्रिंग्स के लिए सबसे लंबी आम सबस्ट्रिंग्स खोजें।

रैखिक समय में किसी दिए गए स्ट्रिंग का सबसे लंबा पैलिंड्रोमिक सबस्ट्रिंग (स्ट्रिंग के सामान्यीकृत सफिक्स ट्री और उसके रिवर्स का उपयोग करके) खोजें।

अनुप्रयोग

सफिक्स ट्री का उपयोग पाठ-संपादन, मुक्त-पाठ खोज, कम्प्यूटेशनल बायोलॉजी और अन्य अनुप्रयोग क्षेत्रों में होने वाली बड़ी संख्या में स्ट्रिंग समस्याओं को हल करने के लिए किया जा सकता है। प्राथमिक अनुप्रयोगों में शामिल हैं:

• स्ट्रिंग खोज, ओ(एम) जटिलता में, जहां एम उप-स्ट्रिंग की लंबाई है (लेकिन स्ट्रिंग के लिए सफिक्स ट्री बनाने के लिए प्रारंभिक ओ(एन) समय की आवश्यकता होती है)
• सबसे लंबे समय तक दोहराई जाने वाली सबस्ट्रिंग ढूँढना
• सबसे लंबी उभयनिष्ठ उपस्ट्रिंग ढूँढना
• एक स्ट्रिंग में सबसे लंबा पैलिन्ड्रोम ढूँढना

सफिक्स ट्री का उपयोग अक्सर जैव सूचना विज्ञान अनुप्रयोगों में किया जाता है, जो डीएनए या प्रोटीन अनुक्रमों में पैटर्न की खोज करते हैं (जिन्हें वर्णों की लंबी श्रृंखला के रूप में देखा जा सकता है)। बेमेल के साथ कुशलता से खोज करने की क्षमता को उनकी सबसे बड़ी ताकत माना जा सकता है। सफिक्स ट्री का उपयोग डेटा संपीड़न में भी किया जाता है; उनका उपयोग बार-बार डेटा ढूंढने के लिए किया जा सकता है, और बरोज़-व्हीलर ट्रांसफॉर्म के सॉर्टिंग चरण के लिए भी किया जा सकता है। LZW संपीड़न योजनाओं के प्रकार सफिक्स ट्री (LZSS) का उपयोग करते हैं। सफिक्स ट्री का उपयोग सफिक्स ट्री क्लस्टरिंग में भी किया जाता है, कुछ खोज इंजनों में उपयोग किया जाने वाला डेटा क्लस्टरिंग एल्गोरिदम।

कार्यान्वयन

यदि प्रत्येक नोड और किनारे को $\Theta (1)$ स्पेस में दर्शाया जा सकता है, तो पूरे ट्री को $\Theta (n)$ स्पेस में दर्शाया जा सकता है। ट्री के सभी किनारों पर सभी स्ट्रिंग्स की कुल लंबाई $O(n^{2})$ है, लेकिन प्रत्येक किनारे को S के एक सबस्ट्रिंग की स्थिति और लंबाई के रूप में संग्रहीत किया जा सकता है, जिससे कुल $\Theta (n)$ कंप्यूटर शब्दों का स्थान उपयोग होता है। सफिक्स ट्री का सबसे खराब स्थिति वाला स्थान उपयोग एक फाइबोनैचि शब्द के साथ देखा जाता है, जो पूरे $2n$ नोड्स देता है।

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

• किसी दिए गए चरित्र पर बच्चे को ढूंढने की लागत.
• एक बच्चे को सम्मिलित करने की लागत.
• किसी नोड के सभी बच्चों को सूचीबद्ध करने की लागत (नीचे तालिका में बच्चों की संख्या से विभाजित)।

मान लीजिए कि σ वर्णमाला का साइज़ है। तो आपके पास निम्नलिखित लागतें होंगी:

${\begin{array}{r|lll}&{\text{Lookup}}&{\text{Insertion}}&{\text{Traversal}}\\\hline {\text{Sibling lists / unsorted arrays}}&O(\sigma )&\Theta (1)&\Theta (1)\\{\text{Bitwise sibling trees}}&O(\log \sigma )&\Theta (1)&\Theta (1)\\{\text{Hash maps}}&\Theta (1)&\Theta (1)&O(\sigma )\\{\text{Balanced search tree}}&O(\log \sigma )&O(\log \sigma )&O(1)\\{\text{Sorted arrays}}&O(\log \sigma )&O(\sigma )&O(1)\\{\text{Hash maps + sibling lists}}&O(1)&O(1)&O(1)\end{array}}$

सम्मिलन लागत का परिशोधन किया गया है, और हैशिंग की लागत सही हैशिंग के लिए दी गई है।

प्रत्येक किनारे और नोड में बड़ी मात्रा में जानकारी सफिक्स ट्री को बहुत महंगा बनाती है, जो अच्छे कार्यान्वयन में स्रोत पाठ की मेमोरी साइज़ का लगभग 10 से 20 गुना अधिक खपत करती है। सफिक्स ऐरे इस आवश्यकता को 8 का कारक तक कम करता है (32-बिट एड्रेस स्पेस और 8-बिट वर्णों के साथ निर्मित एलसीपी मानों को शामिल करने वाले ऐरे के लिए।) यह कारक गुणवत्ताओं पर निर्भर करता है और 32-बिट सिस्टमों पर 4-बाइट चौड़े वर्णों का उपयोग करने के साथ 2 तक पहुंच सकता है (कुछ UNIX-जैसे सिस्टम में किसी भी प्रतीक को समाहित करने के लिए आवश्यक होते हैं, wchar_t देखें)। शोधकर्ताओं ने छोटे इंडेक्स संरचनाओं की खोज जारी रखी है।

समानांतर निर्माण

सफिक्स ट्री निर्माण में तेजी लाने के लिए विभिन्न समानांतर एल्गोरिदम प्रस्तावित किए गए हैं। हाल ही में, $O(n)$ कार्य (अनुक्रमिक समय) और $O(\log ^{2}n)$ स्पैन के साथ सफिक्स ट्री निर्माण के लिए एक व्यावहारिक समानांतर एल्गोरिदम विकसित किया गया है। एल्गोरिथ्म साझा-मेमोरी मल्टीकोर मशीनों पर अच्छी समानांतर स्केलेबिलिटी प्राप्त करता है और 40-कोर मशीन का उपयोग करके 3 मिनट से कम समय में मानव जीनोम - लगभग 3 जीबी - को अनुक्रमित कर सकता है।

बाहरी निर्माण

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

बाहरी मेमोरी में सफिक्स ट्री के निर्माण के सैद्धांतिक परिणाम हैं। Farach-Colton, Ferragina & Muthukrishnan (2000) द्वारा एल्गोरिदम सैद्धांतिक रूप से इष्टतम है, जिसमें सॉर्टिंग के बराबर I/O जटिलता है। हालाँकि, इस एल्गोरिथम की समग्र जटिलता ने अब तक इसके व्यावहारिक कार्यान्वयन को रोका है।

दूसरी ओर, डिस्क-आधारित सफिक्स ट्री के निर्माण के लिए व्यावहारिक कार्य किए गए हैं जो (कुछ) जीबी/घंटे के पैमाने पर हैं। अत्याधुनिक विधियाँ हैं टीडीडी, ट्रेलिस, डिजेएसटी, और बी2एसटी।

टीडीडी और ट्रेलिस पूरे मानव जीनोम तक फैलते हैं, जिसके परिणामस्वरूप दसियों गीगाबाइट साइज़ का एक डिस्क-आधारित सफिक्स ट्री बनता है। हालाँकि, ये विधियाँ 3GB से अधिक अनुक्रमों के संग्रह को कुशलता से संभाल नहीं सकती हैं। DiGeST काफी बेहतर प्रदर्शन करता है और लगभग 6 घंटों में 6GB के क्रम में अनुक्रमों के संग्रह को संभालने में सक्षम है।

ये सभी विधियां उस स्थिति के लिए कुशलतापूर्वक सफिक्स ट्री बना सकती हैं जब ट्री मुख्य मेमोरी में फिट नहीं होता है, लेकिन इनपुट होता है। सबसे नवीनतम विधि, B2ST, उन इनपुट को संभालने के लिए स्केल करती है जो मुख्य मेमोरी में फिट नहीं होते हैं। ईआरए एक हालिया समानांतर सफिक्स ट्री निर्माण विधि है जो काफी तेज़ है। ईआरए 16 जीबी रैम के साथ 8-कोर डेस्कटॉप कंप्यूटर पर 19 मिनट में पूरे मानव जीनोम को अनुक्रमित कर सकता है। 16 नोड्स (4 जीबी रैम प्रति नोड) वाले एक साधारण लिनक्स क्लस्टर पर, ईआरए 9 मिनट से भी कम समय में पूरे मानव जीनोम को अनुक्रमित कर सकता है।

यह भी देखें

• सफिक्स ऑटोमेटन

संदर्भ

• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading/MA: Addison-Wesley, ISBN 0-201-00029-6.
• Apostolico, A.; Iliopoulos, C.; Landau, G. M.; Schieber, B.; Vishkin, U. (1988), "Parallel construction of a suffix tree with applications", Algorithmica, 3 (1–4): 347–365, doi:10.1007/bf01762122, S2CID 5024136.
• Baeza-Yates, Ricardo A.; Gonnet, Gaston H. (1996), "Fast text searching for regular expressions or automaton searching on tries", Journal of the ACM, 43 (6): 915–936, doi:10.1145/235809.235810, S2CID 1420298.
• Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2008), "A new method for indexing genomes using on-disk suffix trees", CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management (PDF), New York, NY, USA: ACM, pp. 649–658.
• Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2009), "Suffix trees for very large genomic sequences", CIKM '09: Proceedings of the 18th ACM Conference on Information and Knowledge Management (PDF), New York, NY, USA: ACM.
• Farach, Martin (1997), "Optimal Suffix Tree Construction with Large Alphabets" (PDF), 38th IEEE Symposium on Foundations of Computer Science (FOCS '97), pp. 137–143.
• Farach, Martin; Muthukrishnan, S. (1996), "Optimal Logarithmic Time Randomized Suffix Tree Construction", International Colloquium on Automata Languages and Programming (PDF).
• Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S. (2000), "On the sorting-complexity of suffix tree construction.", Journal of the ACM, 47 (6): 987–1011, doi:10.1145/355541.355547, S2CID 8164822.
• Giegerich, R.; Kurtz, S. (1997), "From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction" (PDF), Algorithmica, 19 (3): 331–353, doi:10.1007/PL00009177, S2CID 18039097, archived from the original (PDF) on 2016-03-03, retrieved 2012-07-13.
• Gusfield, Dan (1997), Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, ISBN 0-521-58519-8.
• Hariharan, Ramesh (1994), "Optimal Parallel Suffix Tree Construction", ACM Symposium on Theory of Computing (PDF).
• Iliopoulos, Costas; Rytter, Wojciech (2004), "On Parallel Transformations of Suffix Arrays into Suffix Trees", 15th Australasian Workshop on Combinatorial Algorithms, CiteSeerX 10.1.1.62.6715.
• Mansour, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011), "ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings" (PDF), Proceedings of the VLDB Endowment, 5 (1): 49–60, arXiv:1109.6884, Bibcode:2011arXiv1109.6884M, doi:10.14778/2047485.2047490, S2CID 7582116.
• McCreight, Edward M. (1976), "A Space-Economical Suffix Tree Construction Algorithm", Journal of the ACM, 23 (2): 262–272, CiteSeerX 10.1.1.130.8022, doi:10.1145/321941.321946, S2CID 9250303.
• Phoophakdee, Benjarath; Zaki, Mohammed J. (2007), "Genome-scale disk-based suffix tree indexing", SIGMOD '07: Proceedings of the ACM SIGMOD International Conference on Management of Data, New York, NY, USA: ACM, pp. 833–844, CiteSeerX 10.1.1.81.6031.
• Sahinalp, Cenk; Vishkin, Uzi (1994), "Symmetry breaking for suffix tree construction", ACM Symposium on Theory of Computing, doi:10.1145/195058.195164, S2CID 5985171
• Smyth, William (2003), Computing Patterns in Strings, Addison-Wesley.
• Shun, Julian; Blelloch, Guy E. (2014), "A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction", ACM Transactions on Parallel Computing, 1: 1–20, doi:10.1145/2661653, S2CID 1912378.
• Tata, Sandeep; Hankins, Richard A.; Patel, Jignesh M. (2003), "Practical Suffix Tree Construction", VLDB '03: Proceedings of the 30th International Conference on Very Large Data Bases (PDF), Morgan Kaufmann, pp. 36–47.
• Ukkonen, E. (1995), "On-line construction of suffix trees" (PDF), Algorithmica, 14 (3): 249–260, doi:10.1007/BF01206331, S2CID 6027556.
• Weiner, P. (1973), "Linear pattern matching algorithms" (PDF), 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1–11, doi:10.1109/SWAT.1973.13.
• Zamir, Oren; Etzioni, Oren (1998), "Web document clustering: a feasibility demonstration", SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, New York, NY, USA: ACM, pp. 46–54, CiteSeerX 10.1.1.36.4719.

बाहरी संबंध

• Suffix Trees by Sartaj Sahni
• NIST's Dictionary of Algorithms and Data Structures: Suffix Tree
• Universal Data Compression Based on the Burrows-Wheeler Transformation: Theory and Practice, application of suffix trees in the BWT
• Theory and Practice of Succinct Data Structures, C++ implementation of a compressed suffix tree
• Ukkonen's Suffix Tree Implementation in C Part 1 Part 2 Part 3 Part 4 Part 5 Part 6
• Online Demo: Ukkonen's Suffix Tree Visualization