सफिक्स ट्री

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

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

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

इतिहास

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

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

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

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

परिभाषा

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

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

ऐसे पेड़ का अस्तित्व सभी स्ट्रिंग्स के लिए नहीं होता है, इसलिए $S$ को स्ट्रिंग में देखा जाने वाला कोई टर्मिनल सिम्बल (आमतौर पर $ से दर्शाया जाता है) के साथ पैड किया जाता है। इससे यह सुनिश्चित होता है कि कोई सफिक्स किसी अन्य सफिक्स का प्रारंभ नहीं है, और $n$ के $n$ सफिक्स के लिए प्रत्येक के लिए $S$ पत्ती के नोड होंगे। सभी आंतरिक गैर-रूट नोड्स ब्रांचिंग होने के कारण, अधिकतम n - 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)$ बार में सबस्ट्रिंग के रूप में पहली घटना ज्ञात कीजिए।
  • $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