ट्राई

This article is about a tree data structure. For the French commune, see Trie-sur-Baïse.

Trie
Type	tree
Invented	1960
Invented by	Edward Fredkin, Axel Thue, and René de la Briandais
Time complexity in big O notation
Algorithm Average Worst case Space O(n) O(n) Search O(n) O(n) Insert O(n) O(n) Delete O(n) O(n)

चित्र 1: कुंजियों के लिए ट्राई A, to, tea, ted, ten, i, in, और inn। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ मनमाना पूर्णांक मान सम्बद्ध होता है।

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

बाइनरी सर्च ट्री के विपरीत ट्राई में नोड्स अपनी संबंधित कुंजी को संग्रहीत नहीं करते हैं। इसके स्थान पर ट्राई में एक नोड की स्थिति उस कुंजी को परिभाषित करती है जिसके साथ वह संबद्ध है। यह प्रत्येक कुंजी के मान को डेटा संरचना में वितरित करता है और इसका अर्थ है कि आवश्यक नहीं कि प्रत्येक नोड का एक संबद्ध मान हो।

नोड के सभी छोटे भागों में उस मूल नोड से जुड़े स्ट्रिंग का सामान्य उपसर्ग होता है और रूट रिक्त स्ट्रिंग से सम्बद्ध होता है। इसके उपसर्ग द्वारा पहुंच योग्य डेटा को संग्रहीत करने का यह कार्य मूलांक ट्री को नियोजित करके मेमोरी-अनुकूलित उपाय से पूरा किया जा सकता है।

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

इतिहास, व्युत्पत्ति, और उच्चारण

स्ट्रिंग्स के सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार सन 1912 में एक्सल थ्यू द्वारा संक्षेप में वर्णित किया गया था।ट्राइज़ का वर्णन पहली बार सन1959 में रेने डे ला ब्रिंडैस द्वारा कंप्यूटर संदर्भ में किया गया था।

इस विचार का वर्णन सन 1960 में एडवर्ड फ्रेडकिन द्वारा स्वतंत्र रूप से किया गया था जिन्होंने ट्राई शब्द का उच्चारण करते हुए इसे गढ़ा /ˈtriː/ (ट्री के रूप में), पुनर्प्राप्ति के मध्य अक्षर के पश्चात।जबकि अन्य लेखक इसका उच्चारण करते हैं /ˈtraɪ/ (जैसा ट्राई करें) इसे मौखिक रूप से ट्री से पृथक करने के प्रयास में।

अवलोकन

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

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

संचालन

चित्र 2: ट्राई स्ट्रिंग सेट का प्रतिनिधित्व: see, sells और she।

विभिन्न परिचालनों (स्ट्रिंग कुंजी का सम्मिलन, विलोपन और लुकअप) का समर्थन करने का प्रयास करता है। ${\text{nodes}}$ प्रयत्नों से बना है जिसमें ऐसे लिंक सम्मिलित हैं जो या तो अन्य चाइल्ड प्रत्यय चाइल्ड नोड्स के संदर्भ हैं या ${\text{nil}}$। रूट को छोड़कर, प्रत्येक नोड को केवल अन्य नोड द्वारा इंगित किया जाता है जिसे पैरेंट कहा जाता है। प्रत्येक नोड में ${\text{R}}$ लिंक सम्मिलित है जहाँ ${\text{R}}$ लागू वर्णमाला (औपचारिक भाषाओं) की प्रमुखता है जबकि कोशिशों की पर्याप्त संख्या ${\text{nil}}$ लिंक है। अधिकतर स्थितियों में ${\text{Children}}$ का आकार (अहस्ताक्षरित) ASCII की स्थितियों में सरणी अक्षरों को सांकेतिक अक्षरों में परिवर्तन की बिटलेंथ - 256 है। ${\text{nil}}$ h> भीतर लिंक ${\text{Children}}$ में ${\text{Node}}$ निम्नलिखित विशेषताओं पर जोर देता है:

1. वर्ण और स्ट्रिंग कुंजियाँ अंतर्निहित रूप से ट्राई डेटा संरचना प्रतिनिधित्व में संग्रहीत होती हैं और इसमें स्ट्रिंग-समाप्ति को इंगित करने वाला वर्ण प्रहरी मान सम्मिलित होता है।
2. प्रत्येक नोड में सेट की मजबूत कुंजियों के उपसर्ग का संभावित लिंक होता है।

ट्राई में नोड्स का बुनियादी समग्र डेटा प्रकार इस प्रकार है; ${\text{Node}}$ वैकल्पिक रूप से सम्मिलित हो सकता है ${\text{Value}}$ जो स्ट्रिंग या टर्मिनल नोड के अंतिम अक्षर में संग्रहीत प्रत्येक कुंजी से सम्बद्ध हुआ है।

structure Node Children Node[Alphabet-Size] Is-Terminal Boolean Value Data-Type end structure

खोजना

ट्राइ में ${\text{Value}}$ की खोज स्ट्रिंग कुंजी में वर्णों द्वारा निर्देशित की जाती है क्योंकि ट्राइ में प्रत्येक नोड में दिए गए स्ट्रिंग में प्रत्येक संभावित वर्ण के लिए संबंधित लिंक होता है। इस प्रकार ट्राइ के भीतर स्ट्रिंग का अनुसरण करने से दी गई ${\text{Value}}$ स्ट्रिंग कुंजी के लिए संबंधित परिणाम प्राप्त होता है। ${\text{nil}}$ खोज निष्पादन के भीतर लिंक कुंजी की अस्तित्वहीनता को इंगित करता है।

निम्नलिखित स्यूडोकोड किसी दी गई स्ट्रिंग कुंजी (${\text{key}}$) के लिए जड़ित ट्राइ (${\text{x}}$) में खोज प्रक्रिया को लागू करता है

Trie-Find(x, key) for 0 ≤ i < key.length do if x.Children[key[i]] = nil then return false end if x := x.Children[key[i]] repeat return x.Value

उपरोक्त छद्म कोड में ${\text{x}}$ और ${\text{key}}$ क्रमशः ट्राई के रूट नोड और स्ट्रिंग कुंजी के सूचक से मेल खाते हैं। मानक ट्राई में $O({\text{dm}})$ खोज अभियान चलता है तथा ${\text{m}}$ स्ट्रिंग पैरामीटर ${\text{key}}$ आकार का है और ${\text{d}}$ वर्णमाला (औपचारिक भाषाएँ) से मेल खाती है। दूसरी ओर बाइनरी खोज ट्री $O(m\log n)$ लें सबसे खराब स्थिति में, चूँकि खोज ट्री की ऊँचाई पर निर्भर करती है ($\log n$) बीएसटी का (संतुलित पेड़ों के मामले में), जहां ${\text{n}}$ और ${\text{m}}$ चाबियों की संख्या और चाबियों की लंबाई।

यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं तो बीएसटी की तुलना में ट्राई कम स्थान घेरता है क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं। ट्री के टर्मिनल नोड में ${\text{Value}}$ एक गैर-शून्य होता है और यदि संबंधित मान ट्राई में पाया जाता है तो यह खोज हिट है और यदि ऐसा नहीं है तो खोज मिस हो जाती है।

प्रविष्टि

ट्राई में सम्मिलन को कैरेक्टर एन्कोडिंग, कैरेक्टर मैप और कोड पेजों को इंडेक्स के रूप में उपयोग करके निर्देशित किया जाता है। ${\text{Children}}$ स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने तक सरणी। ट्राई में प्रत्येक नोड मूलांक छँटाई रूटीन की कॉल से मेल खाता है क्योंकि ट्राई संरचना टॉप-डाउन रेडिक्स सॉर्ट के पैटर्न के निष्पादन को दर्शाती है।

1 Trie-Insert(x, key, value) 2 for 0 ≤ i < key.length do 3 if x.Children[key[i]] = nil then 4 x.Children[key[i]] := Node() 5 end if 6 x := x.Children[key[i]] 7 repeat 8 x.Value := value 9 x.Is-Terminal := True

यदि ${\text{nil}}$ स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने से पहले लिंक का सामना करना पड़ता है एवं नया ${\text{Node}}$ बनाया गया है जैसे पंक्ति 3-5 के साथ। ${\text{x.Value}}$ इनपुट ${\text{value}}$ को सौंपा जाता है; यदि ${\text{x.Value}}$ सम्मिलन के समय ${\text{nil}}$ नहीं था एवं दी गई स्ट्रिंग कुंजी से सम्बद्ध मान वर्तमान कुंजी से प्रतिस्थापित हो जाता है।

विलोपन

ट्राई से कुंजी-मूल्य जोड़ी को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत पर चिह्नित करना सम्मिलित है। ${\text{nil}}$ तदनुसार.

जड़ित ट्राई (${\text{x}}$) से स्ट्रिंग कुंजी (${\text{key}}$) को हटाने के लिए रिकर्सन (कंप्यूटर विज्ञान) प्रक्रिया निम्नलिखित है,

1 Trie-Delete(x, key) 2 if key = nil then 3 if x.Is-Terminal = True then 4 x.Is-Terminal := False 5 x.Value := nil 6 end if 7 for 0 ≤ i < x.Children.length 8 if x.Children[i] != nil 9 return x 10 end if 11 repeat 12 return nil 13 end if 14 x.Children[key[0]] := Trie-Delete(x.Children[key[0]], key[1:]) 15 return x

${\text{key}}$ प्रक्रियाएँ जाँचने से प्रारम्भ होती हैं; ${\text{nil}}$ टर्मिनल नोड या स्ट्रिंग कुंजी के अंत के आगमन को दर्शाता है। यदि टर्मिनल और यदि इसमें कोई चाइल्ड नहीं है तो नोड को ट्राइ से हटा दिया जाता है (पंक्ति 14 वर्ण सूचकांक को निर्दिष्ट करता है) ${\text{nil}}$) जबकि नोड के टर्मिनल के बिना स्ट्रिंग कुंजी का अंत इंगित करता है कि कुंजी उपस्थित नहीं है इस प्रकार प्रक्रिया ट्राई को संशोधित नहीं करती है। प्रत्यावर्तन वृद्धि करके ${\text{key}}$ का सूचकांक आगे बढ़ता है।

अन्य डेटा संरचनाओं को परिवर्तित करना

हैश तालिकाओं के लिए प्रतिस्थापन

ट्राई का उपयोग हैश टेबल को परिवर्तित करने के लिए किया जा सकता है जिसके निम्नलिखित लाभ हैं:

• $m$ आकार की संबद्ध कुंजी के साथ एक नोड की खोज करना $O(m)$ की जटिलता है जबकि अपूर्ण हैश फ़ंक्शन में कई टकराने वाली कुंजियाँ हो सकती हैं और ऐसी तालिका की सबसे खराब स्थिति वाली लुकअप गति $O(N)$ होगी जहाँ $N$ तालिका के भीतर नोड्स की कुल संख्या को दर्शाता है।
• हैश टेबल के विपरीत ट्राइज़ को ऑपरेशन के लिए हैश फ़ंक्शन की आवश्यकता नहीं होती है; ट्राई में विभिन्न कुंजियों की कोई हैश टक्कर भी नहीं होती है।
• ट्राई में बकेट जो हैश टेबल बकेट के समान होते हैं जो कुंजी टकराव को संग्रहीत करते हैं एवं केवल तभी आवश्यक होते हैं जब कुंजी एक से अधिक मान से जुड़ी होती है।
• ट्राई के भीतर स्ट्रिंग कुंजियों को पूर्व निर्धारित वर्णमाला क्रम का उपयोग करके क्रमबद्ध किया जा सकता है।

जबकि हैश तालिका की तुलना में ट्राई कम कुशल होते हैं जब डेटा को सीधे कंप्यूटर डेटा स्टोरेज जैसे कि हार्ड डिस्क ड्राइव पर एक्सेस किया जाता है जिसमें मुख्य मेमोरी की तुलना में अधिक रैंडम एक्सेस समय होता है। जब कुंजी मान को सरलता से स्ट्रिंग के रूप में प्रस्तुत नहीं किया जा सकता है तो कोशिशें भी हानिकारक होती हैं जैसे कि फ़्लोटिंग पॉइंट संख्याएँ जहाँ एकाधिक प्रतिनिधित्व संभव हैं (उदाहरण के लिए 1, 1.0, +1.0, 1.00, आदि के बराबर है) जबकि इसे दो के पूरक प्रारूप की तुलना में IEEE 754 में बाइनरी संख्या के रूप में स्पष्ट रूप से दर्शाया जा सकता है।

कार्यान्वयन रणनीतियाँ

चित्र 3: बाएं-चाइल्ड के दाएं-सिबलिंग बाइनरी ट्री के रूप में कार्यान्वित ट्राइ: ऊर्ध्वाधर तीर child सूचक हैं, धराशायी क्षैतिज तीर next सूचक हैं। इस ट्राई में संग्रहित स्ट्रिंग्स {baby, bad, bank, box, dad, dance} का सेट है। सूचियों को शब्दकोषीय क्रम में ट्रैवर्सल की अनुमति देने के लिए क्रमबद्ध किया गया है।

मेमोरी उपयोग और संचालन की गति के मध्य विभिन्न ट्रेड-ऑफ के अनुरूप ट्राई को कई उपायों द्वारा दर्शाया जा सकता है। किसी ट्राई का प्रतिनिधित्व करने के लिए पॉइंटर्स के वेक्टर का उपयोग करने से बड़े स्थान की खपत होती है; जबकि यदि प्रत्येक नोड वेक्टर के लिए एकल लिंक की गई सूची का उपयोग किया जाता है तो मेमोरी स्पेस को रनिंग टाइम के मूल्य पर कम किया जा सकता है क्योंकि वेक्टर ${\text{nil}}$ की अधिकांश प्रविष्टियाँ सम्मिलित हैं।

वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को छोटे वर्णमाला पर लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। n बाइट्स की एक स्ट्रिंग को वैकल्पिक रूप से 2n चार-बिट इकाइयों की एक स्ट्रिंग के रूप में माना जा सकता है और प्रति नोड सोलह पॉइंटर्स के साथ ट्राइ में संग्रहीत किया जा सकता है। जबकि सबसे खराब स्थिति में लुकअप को दोगुने नोड्स पर जाने की आवश्यकता होती है जबकि स्थान की आवश्यकताएँ आठ गुना कम हो जाती हैं। अन्य तकनीकों में ASCII वर्णमाला का प्रतिनिधित्व करने वाले 256 बिट्स के बिटमैप के रूप में 256 ASCII पॉइंटर्स के वेक्टर को संग्रहीत करना सम्मिलित है जो व्यक्तिगत नोड्स के आकार को नाटकीय रूप से कम कर देता है।

बिटवाइज़ ट्राई

See also: x-तीव्र ट्राई and बिटमैप के साथ बिटवाइज़ ट्राई

सरल पॉइंटर वेक्टर कार्यान्वयन में ट्राइ नोड्स के लिए विशाल स्थान की आवश्यकता को संबोधित करने के लिए बिटवाइज़ ट्राईों का उपयोग किया जाता है। स्ट्रिंग कुंजी सेट में प्रत्येक वर्ण को अलग-अलग बिट्स के माध्यम से दर्शाया जाता है जिसका उपयोग स्ट्रिंग कुंजी पर ट्राई को पार करने के लिए किया जाता है। इस प्रकार के ट्राई के कार्यान्वयन निश्चित-लंबाई कुंजी इनपुट में पहला सेट खोजने के लिए SIMD CPU निर्देशों का उपयोग करते हैं (उदाहरण के लिए जीएनयू कंपाइलर संग्रह) __builtin_clz() आंतरिक कार्य)। तदनुसार, सेट बिट का उपयोग 32- या 64-प्रविष्टि आधारित बिटवाइज़ ट्री में पहले आइटम या चाइल्ड नोड को अनुक्रमित करने के लिए किया जाता है। इसके पश्चात कुंजी में प्रत्येक आगामी बिट का परीक्षण करके खोज आगे बढ़ती है।

यह प्रक्रिया सीपीयू रजिस्टर स्वतंत्रता के कारण कैच-स्थानीय और समानांतर प्रोग्रामिंग मॉडल भी है और इस प्रकार क्रम से बाहर निष्पादन सीपीयू पर प्रदर्शन करती है।

संपीड़ित ट्राइ

Main article: Radix tree

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

एक और दृष्टिकोण ट्राइ को पैक करना है जिसमें स्वचालित हाइफ़नेशन एल्गोरिथ्म पर लागू एक विरल पैक ट्राइ का स्थान-कुशल कार्यान्वयन होता है जिसमें प्रत्येक नोड के वंशजों को मेमोरी में इंटरलीव किया जा सकता है।

पेट्रीसिया ट्री

चित्र. 4: पेट्रीसिया ट्री स्ट्रिंग कुंजियों का प्रतिनिधित्व: इन, पूर्णांक, अंतराल, स्ट्रिंग और संरचना।

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

स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व $\{in,integer,interval,string,structure\}$ चित्र 4 में दिखाया गया है और नोड्स से सटे प्रत्येक सूचकांक मान स्किप संख्या का प्रतिनिधित्व करता है - बिट का सूचकांक जिसके साथ शाखा तय की जानी है। नोड 0 पर स्किप नंबर 1 बाइनरी एन्कोडेड ASCII में स्थिति 1 से मेल खाता है जहां कुंजी सेट में सबसे बाईं ओर का बिट भिन्न था $X$. पेट्रीसिया ट्री में नोड्स की खोज, सम्मिलन और हटाने के लिए स्किप नंबर महत्वपूर्ण है, और प्रत्येक पुनरावृत्ति के दौरान थोड़ा मास्किंग ऑपरेशन किया जाता है।

अनुप्रयोग

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

श्रेणीबद्ध करना

स्ट्रिंग कुंजियों के सेट के शब्दकोषीय क्रम को दी गई कुंजियों के लिए ट्राई बनाकर और ट्री ट्रैवर्सल प्री-ऑर्डर कार्यान्वयन में ट्री को पार करके कार्यान्वित किया जा सकता है; यह भी मूलांक प्रकार का एक रूप है। ट्राई बर्स्टसॉर्ट के लिए मूलभूत डेटा संरचनाएं भी हैं जो 2007 तक सबसे तीव्र स्ट्रिंग सॉर्टिंग एल्गोरिदम होने एवं सीपीयू कैच (कंप्यूटिंग) के कुशल उपयोग के लिए उल्लेखनीय है।

पूर्ण-पाठ खोज

विशेष प्रकार की ट्राई जिसे [[प्रत्यय वृक्ष]] कहा जाता है का उपयोग तीव्रता से पूर्ण-पाठ खोज करने के लिए किसी पाठ में सभी प्रत्ययों को अनुक्रमित करने के लिए किया जा सकता है।

वेब खोज इंजन

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

जैव सूचना विज्ञान

ट्राई का उपयोग जैव सूचना विज्ञान में किया जाता है विशेष रूप से अनुक्रम संरेखण सॉफ़्टवेयर अनुप्रयोगों जैसे कि BLAST (जैव प्रौद्योगिकी) एल्गोरिदम में जो संपीड़ित ट्राइ में उनकी घटनाओं की स्थिति को संग्रहीत करके किसी पाठ की लंबाई k (जिसे k-mers कहा जाता है) के सभी अलग-अलग सबस्ट्रिंग अनुक्रम डेटाबेस को अनुक्रमित करता है।

इंटरनेट रूटिंग

See also: Luleå algorithm

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

यह भी देखें

• प्रत्यय वृक्ष
• हैश ट्राई
• हैश ऐरे मैप किया गया ट्राई
• उपसर्ग हैश Ctrie
• सीट्री
• HAT-trie

बाहरी संबंध

• NIST's Dictionary of Algorithms and Data Structures: Trie