सफिक्स ट्री

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

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

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

इतिहास

इस अवधारणा को सबसे पहले पेश किया गया था Weiner (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 के एल्गोरिदम के रूप में। पाठ्यपुस्तक Aho, Hopcroft & Ullman (1974, Sect.9.5) वेनर के परिणामों को एक सरलीकृत और अधिक सुंदर रूप में पुन: प्रस्तुत किया गया, जिसमें पोजीशन ट्री शब्द का परिचय दिया गया।

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

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

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

परिभाषा

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

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

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

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

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

कार्यक्षमता

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

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

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

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

• प्रत्ययों के बीच सबसे लंबा सामान्य उपसर्ग खोजें $S_{i}[p..n_{i}]$ और $S_{j}[q..n_{j}]$ में $\Theta (1)$.
• अधिकतम k बेमेल के साथ लंबाई m का एक पैटर्न P खोजें $O(kn+z)$ समय, जहां z हिट्स की संख्या है।
• सब ढूँढ़ो $z$ अधिकतम विलोमपद $\Theta (n)$, या $\Theta (gn)$ यदि लंबाई का अंतराल हो तो समय $g$ अनुमति है, या $\Theta (kn)$ अगर $k$ बेमेल की अनुमति है.
• सब ढूँढ़ो $z$ अग्रानुक्रम दोहराता है $O(n\log n+z)$, और k-बेमेल अग्रानुक्रम दोहराता है $O(kn\log(n/k)+z)$.
• कम से कम सबसे लंबी सामान्य सबस्ट्रिंग समस्या ढूंढें $k$ में तार $D$ के लिए $k=2,\dots ,K$ में $\Theta (n)$ समय।
• रैखिक समय में किसी दिए गए स्ट्रिंग का सबसे लंबा पैलिंड्रोमिक सबस्ट्रिंग (स्ट्रिंग के सामान्यीकृत प्रत्यय ट्री और उसके रिवर्स का उपयोग करके) ढूंढें।

अनुप्रयोग

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

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

प्रत्यय वृक्षों का उपयोग अक्सर जैव सूचना विज्ञान अनुप्रयोगों में किया जाता है, डीएनए या प्रोटीन अनुक्रमों में पैटर्न की खोज की जाती है (जिन्हें वर्णों की लंबी श्रृंखला के रूप में देखा जा सकता है)। बेमेल के साथ कुशलतापूर्वक खोज करने की क्षमता उनकी सबसे बड़ी ताकत मानी जा सकती है। प्रत्यय वृक्षों का उपयोग डेटा संपीड़न में भी किया जाता है; उनका उपयोग बार-बार डेटा खोजने के लिए किया जा सकता है, और बरोज़-व्हीलर ट्रांसफ़ॉर्म के सॉर्टिंग चरण के लिए भी किया जा सकता है। 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-बिट वर्णों के भीतर निर्मित एलसीपी सरणी मानों सहित सरणी के लिए।) यह कारक गुणों पर निर्भर करता है और 4-बाइट चौड़े वर्णों के उपयोग के साथ 2 तक पहुंच सकता है। (कुछ UNIX-जैसी प्रणालियों में कोई प्रतीक शामिल करने की आवश्यकता है, wchar_t देखें) 32-बिट सिस्टम पर। शोधकर्ताओं ने छोटी अनुक्रमणिका संरचनाओं को ढूंढना जारी रखा है।

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

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

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

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

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

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

ये सभी विधियाँ उस मामले के लिए कुशलतापूर्वक प्रत्यय वृक्षों का निर्माण कर सकती हैं जब पेड़ मुख्य मेमोरी में फ़िट नहीं होता, लेकिन इनपुट करता है. सबसे नवीनतम विधि, बी²ST,संभालने के लिए तराजू ऐसे इनपुट जो मुख्य मेमोरी में फिट नहीं होते। ईआरए एक हालिया समानांतर प्रत्यय वृक्ष निर्माण विधि है जो काफी तेज़ है। ईआरए 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