ट्राई: Difference between revisions

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

Revision as of 23:07, 19 July 2023

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

कंप्यूटर विज्ञान में ट्राई जिसे डिजिटल ट्री या प्रिफिक्स ट्री भी कहा जाता है^[1] जो एक प्रकार का k-ary सर्च ट्री है। ट्री (डेटा संरचना) डेटा संरचना का उपयोग सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये कुंजियाँ ( ${\text{key}}$ ) अधिकतर स्ट्रिंग (कंप्यूटर विज्ञान) होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि विशिष्ट अक्षरों (कंप्यूटिंग) द्वारा परिभाषित होते हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनः प्राप्त करने, उसे परिवर्तित करने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए डेप्थ-फर्स्ट सर्च को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है।

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

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

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

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

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

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

अवलोकन

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

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

संचालन

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

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

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

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

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

खोजना

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

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

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}}$ वर्णमाला (औपचारिक भाषाएँ) से मेल खाती है।^[16]^: 754 दूसरी ओर बाइनरी सर्च ट्री $O(m\log n)$ लें सबसे खराब स्थिति में, चूँकि सर्च ट्री की ऊँचाई पर निर्भर करती है ( $\log n$ ) बीएसटी का (संतुलित ट्री की स्थिति में), जहां ${\text{n}}$ और ${\text{m}}$ , ${\text{key}}$ की संख्या और ${\text{key}}$ की लंबाई है।^[12]^: 358

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

प्रविष्टि

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

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 के साथ।^[14]^: 745 ${\text{x.Value}}$ इनपुट ${\text{value}}$ को सौंपा जाता है; यदि ${\text{x.Value}}$ इंसर्शन के समय ${\text{nil}}$ नहीं था एवं दी गई स्ट्रिंग कुंजी से सम्बद्ध मान वर्तमान कुंजी से प्रतिस्थापित हो जाता है।

विलोपन

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

रूटेड ट्राई ( ${\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}}$ का सूचकांक आगे बढ़ता है।

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

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

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

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

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

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

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

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

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

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

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

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

कंप्रेस्ड ट्राइ

रेडिक्स ट्री जिसे कंप्रेस्ड ट्राई के रूप में भी जाना जाता है ट्राई का एक अंतरिक्ष-अनुकूलित संस्करण है जिसमें केवल चाइल्ड वाले नोड्स अपने पेरेंट के साथ विलय हो जाते हैं; एकल चाइल्ड के साथ नोड्स की शाखाओं को हटाने से अंतरिक्ष और समय मेट्रिक्स दोनों में उन्नत परिणाम मिलते हैं।^[20]^[21]^: 452 यह तब सबसे अच्छा काम करता है जब ट्राई स्थिर रहता है और संग्रहीत कुंजियों का सेट उनके प्रतिनिधित्व स्थान के भीतर बहुत विरल होता है।^[22]^: 3–16

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

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

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

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

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

अनुप्रयोग

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

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

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

पूर्ण-टेक्स्ट सर्च

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

वेब सर्च इंजन

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

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

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

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

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

यह भी देखें

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

संदर्भ

↑ ^1.0 ^1.1 Maabar, Maha (17 November 2014). "डेटा संरचना का प्रयास करें". CVR, University of Glasgow. Archived from the original on 27 January 2021. Retrieved 17 April 2022.
↑ Thue, Axel (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen". Skrifter Udgivne Af Videnskabs-Selskabet I Christiania. 1912 (1): 1–67. Cited by Knuth.
↑ ^3.0 ^3.1 ^3.2 ^3.3 Knuth, Donald (1997). "6.3: Digital Searching". The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 492. ISBN 0-201-89685-0.
↑ de la Briandais, René (1959). परिवर्तनीय लंबाई कुंजियों का उपयोग करके फ़ाइल खोज (PDF). Proc. Western J. Computer Conf. pp. 295–298. doi:10.1145/1457838.1457895. S2CID 10963780. Archived from the original (PDF) on 2020-02-11. Cited by Brass and by Knuth.
↑ ^5.0 ^5.1 ^5.2 ^5.3 Brass, Peter (8 September 2008). उन्नत डेटा संरचनाएँ. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 978-0521880374.
↑ ^6.0 ^6.1 Edward Fredkin (1960). "स्मृति का प्रयास करें". Communications of the ACM. 3 (9): 490–499. doi:10.1145/367390.367400. S2CID 15384533.
↑ ^7.0 ^7.1 Black, Paul E. (2009-11-16). करें.html "प्रयास करें". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. करें.html Archived from the original on 2011-04-29. {{cite web}}: Check |archive-url= value (help); Check |url= value (help)
↑ ^8.0 ^8.1 ^8.2 ^8.3 ^8.4 Franklin Mark Liang (1983). कॉम-पुट-एर द्वारा वर्ड हाई-फेन-ए-टियन (PDF) (Doctor of Philosophy thesis). Stanford University. Archived (PDF) from the original on 2005-11-11. Retrieved 2010-03-28.
↑ "प्रयास करें". School of Arts and Science, Rutgers University. 2022. Archived from the original on 17 April 2022. Retrieved 17 April 2022.
↑ Connelly, Richard H.; Morris, F. Lockwood (1993). "ट्राई डेटा संरचना का सामान्यीकरण". Mathematical Structures in Computer Science. Syracuse University. 5 (3): 381–418. doi:10.1017/S0960129500000803. S2CID 18747244.
↑ ^11.0 ^11.1 Aho, Alfred V.; Corasick, Margaret J. (Jun 1975). "Efficient String Matching: An Aid to Bibliographic Search" (PDF). Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855. S2CID 207735784.
↑ ^12.0 ^12.1 ^12.2 ^12.3 ^12.4 ^12.5 Thareja, Reema (13 October 2018). "Hashing and Collision". सी का उपयोग कर डेटा संरचनाएं (2 ed.). Oxford University Press. ISBN 9780198099307.
↑ Daciuk, Jan (24 June 2003). स्ट्रिंग्स के सेट से न्यूनतम, चक्रीय, नियतात्मक, परिमित-राज्य ऑटोमेटा के लिए निर्माण एल्गोरिदम की तुलना. International Conference on Implementation and Application of Automata. Springer Publishing. pp. 255–261. doi:10.1007/3-540-44977-9_26. ISBN 978-3-540-40391-3.
↑ ^14.0 ^14.1 ^14.2 ^14.3 ^14.4 ^14.5 ^14.6 Sedgewick, Robert; Wayne, Kevin (3 April 2011). एल्गोरिदम (4 ed.). Addison-Wesley, Princeton University. ISBN 978-0321573513.
↑ ^15.0 ^15.1 ^15.2 ^15.3 ^15.4 ^15.5 Gonnet, G. H.; Yates, R. Baeza (January 1991). Handbook of algorithms and data structures: in Pascal and C (2 ed.). Boston, United States: Addison-Wesley. ISBN 978-0-201-41607-7.
↑ Patil, Virsha H. (10 May 2012). C++ का उपयोग कर डेटा संरचनाएँ. Oxford University Press. ISBN 9780198066231.
↑ S. Orley; J. Mathews. "The IEEE 754 Format". Department of Mathematics and Computer Science, Emory University. Archived from the original on 28 March 2022. Retrieved 17 April 2022.
↑ Bellekens, Xavier (2014). "A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems". Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14. Glasgow, Scotland, UK: ACM. pp. 302:302–302:309. arXiv:1704.02272. doi:10.1145/2659651.2659723. ISBN 978-1-4503-3033-6. S2CID 12943246.
↑ ^19.0 ^19.1 Willar, Dan E. (27 January 1983). "अंतरिक्ष O(n) में लॉग-लघुगणकीय सबसे खराब स्थिति वाले श्रेणी प्रश्न संभव हैं". Information Processing Letters. ScienceDirect. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3.
↑ Sartaj Sahni (2004). "Data Structures, Algorithms, & Applications in C++: Tries". University of Florida. Archived from the original on 16 July 2016. Retrieved 17 April 2022. {{cite web}}: |archive-date= / |archive-url= timestamp mismatch (help)
↑ Mehta, Dinesh P.; Sahni, Sartaj (7 March 2018). "Tries". डेटा संरचनाओं और अनुप्रयोगों की पुस्तिका (2 ed.). Chapman & Hall, University of Florida. ISBN 978-1498701853.
↑ Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard E. Watson (1 March 2000). "न्यूनतम एसाइक्लिक परिमित-राज्य ऑटोमेटा का वृद्धिशील निर्माण". Computational Linguistics. MIT Press. 26 (1): 3–16. arXiv:cs/0007009. Bibcode:2000cs........7009D. doi:10.1162/089120100561601.
↑ "Patricia tree". National Institute of Standards and Technology. Archived from the original on 14 February 2022. Retrieved 17 April 2022.
↑ ^24.0 ^24.1 ^24.2 Crochemore, Maxime; Lecroq, Thierry (2009). "Trie". डेटाबेस सिस्टम का विश्वकोश. Boston, United States: Springer Publishing. Bibcode:2009eds..book.....L. doi:10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0 – via HAL (open archive).
↑ ^25.0 ^25.1 ^25.2 Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (March 2016). "व्यावहारिक संपीड़ित स्ट्रिंग शब्दकोश". Information Systems. Elsevier. 56: 73–108. doi:10.1016/j.is.2015.08.008. ISSN 0306-4379.
↑ Kärkkäinen, Juha. "Lecture 2" (PDF). University of Helsinki. एक ट्राइ में नोड्स का प्रीऑर्डर उन स्ट्रिंग्स के लेक्सिकोग्राफ़िकल क्रम के समान है जो वे प्रतिनिधित्व करते हैं, यह मानते हुए कि नोड के बच्चों को किनारे के लेबल द्वारा ऑर्डर किया गया है।
↑ Kallis, Rafael (2018). "The Adaptive Radix Tree (Report #14-708-887)" (PDF). University of Zurich: Department of Informatics, Research Publications.
↑ Ranjan Sinha and Justin Zobel and David Ring (Feb 2006). "प्रतिलिपि का उपयोग करके कैश-कुशल स्ट्रिंग सॉर्टिंग" (PDF). ACM Journal of Experimental Algorithmics. 11: 1–32. doi:10.1145/1187436.1187439. S2CID 3184411.
↑ J. Kärkkäinen and T. Rantala (2008). "Engineering Radix Sort for Strings". In A. Amir and A. Turpin and A. Moffat (ed.). स्ट्रिंग प्रोसेसिंग और सूचना पुनर्प्राप्ति, प्रोक। शिखर. Lecture Notes in Computer Science. Vol. 5280. Springer. pp. 3–14. doi:10.1007/978-3-540-89097-3_3. ISBN 978-3-540-89096-6.
↑ Giancarlo, Raffaele (28 May 1992). "अनुप्रयोगों के साथ वर्गाकार मैट्रिक्स में प्रत्यय वृक्ष का सामान्यीकरण". SIAM Journal on Computing. Society for Industrial and Applied Mathematics. 24 (3): 520–562. doi:10.1137/S0097539792231982. ISSN 0097-5397.
↑ Yang, Lai; Xu, Lida; Shi, Zhongzhi (23 March 2012). "शब्दकोष खोज के लिए एक उन्नत गतिशील हैश TRIE एल्गोरिथ्म". Enterprise Information Systems. 6 (4): 419–432. Bibcode:2012EntIS...6..419Y. doi:10.1080/17517575.2012.665483. S2CID 37884057.
↑ Transier, Frederik; Sanders, Peter (December 2010). "इन-मेमोरी टेक्स्ट सर्च इंजन की इंजीनियरिंग बुनियादी एल्गोरिदम". ACM Transactions on Information Systems. Association for Computing Machinery. 29 (1): 1–37. doi:10.1145/1877766.1877768. S2CID 932749.

बाहरी संबंध

NIST's Dictionary of Algorithms and Data Structures: Trie

[cvr14-1] 1.0 ^1.1 Maabar, Maha (17 November 2014). "डेटा संरचना का प्रयास करें". CVR, University of Glasgow. Archived from the original on 27 January 2021. Retrieved 17 April 2022.

[thue-2] Thue, Axel (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen". Skrifter Udgivne Af Videnskabs-Selskabet I Christiania. 1912 (1): 1–67. Cited by Knuth.

[KnuthVol3-3] 3.0 ^3.1 ^3.2 ^3.3 Knuth, Donald (1997). "6.3: Digital Searching". The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 492. ISBN 0-201-89685-0.

[4] Briandais, René (1959). परिवर्तनीय लंबाई कुंजियों का उपयोग करके फ़ाइल खोज (PDF). Proc. Western J. Computer Conf. pp. 295–298. doi:10.1145/1457838.1457895. S2CID 10963780. Archived from the original (PDF) on 2020-02-11. Cited by Brass and by Knuth.

[brass-5] 5.0 ^5.1 ^5.2 ^5.3 Brass, Peter (8 September 2008). उन्नत डेटा संरचनाएँ. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 978-0521880374.

[triememory-6] 6.0 ^6.1 Edward Fredkin (1960). "स्मृति का प्रयास करें". Communications of the ACM. 3 (9): 490–499. doi:10.1145/367390.367400. S2CID 15384533.

[DADS-7] 7.0 ^7.1 Black, Paul E. (2009-11-16). करें.html "प्रयास करें". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. करें.html Archived from the original on 2011-04-29. {{cite web}}: Check |archive-url= value (help); Check |url= value (help)

[Liang1983-8] 8.0 ^8.1 ^8.2 ^8.3 ^8.4 Franklin Mark Liang (1983). कॉम-पुट-एर द्वारा वर्ड हाई-फेन-ए-टियन (PDF) (Doctor of Philosophy thesis). Stanford University. Archived (PDF) from the original on 2005-11-11. Retrieved 2010-03-28.

[9] "प्रयास करें". School of Arts and Science, Rutgers University. 2022. Archived from the original on 17 April 2022. Retrieved 17 April 2022.

[10] Connelly, Richard H.; Morris, F. Lockwood (1993). "ट्राई डेटा संरचना का सामान्यीकरण". Mathematical Structures in Computer Science. Syracuse University. 5 (3): 381–418. doi:10.1017/S0960129500000803. S2CID 18747244.

[aho75-11] 11.0 ^11.1 Aho, Alfred V.; Corasick, Margaret J. (Jun 1975). "Efficient String Matching: An Aid to Bibliographic Search" (PDF). Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855. S2CID 207735784.

[reema18-12] 12.0 ^12.1 ^12.2 ^12.3 ^12.4 ^12.5 Thareja, Reema (13 October 2018). "Hashing and Collision". सी का उपयोग कर डेटा संरचनाएं (2 ed.). Oxford University Press. ISBN 9780198099307.

[13] Daciuk, Jan (24 June 2003). स्ट्रिंग्स के सेट से न्यूनतम, चक्रीय, नियतात्मक, परिमित-राज्य ऑटोमेटा के लिए निर्माण एल्गोरिदम की तुलना. International Conference on Implementation and Application of Automata. Springer Publishing. pp. 255–261. doi:10.1007/3-540-44977-9_26. ISBN 978-3-540-40391-3.

[robert11-14] 14.0 ^14.1 ^14.2 ^14.3 ^14.4 ^14.5 ^14.6 Sedgewick, Robert; Wayne, Kevin (3 April 2011). एल्गोरिदम (4 ed.). Addison-Wesley, Princeton University. ISBN 978-0321573513.

[gonnet91-15] 15.0 ^15.1 ^15.2 ^15.3 ^15.4 ^15.5 Gonnet, G. H.; Yates, R. Baeza (January 1991). Handbook of algorithms and data structures: in Pascal and C (2 ed.). Boston, United States: Addison-Wesley. ISBN 978-0-201-41607-7.

[patil_12-16] Patil, Virsha H. (10 May 2012). C++ का उपयोग कर डेटा संरचनाएँ. Oxford University Press. ISBN 9780198066231.

[17] S. Orley; J. Mathews. "The IEEE 754 Format". Department of Mathematics and Computer Science, Emory University. Archived from the original on 28 March 2022. Retrieved 17 April 2022.

[18] Bellekens, Xavier (2014). "A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems". Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14. Glasgow, Scotland, UK: ACM. pp. 302:302–302:309. arXiv:1704.02272. doi:10.1145/2659651.2659723. ISBN 978-1-4503-3033-6. S2CID 12943246.

[willar83-19] 19.0 ^19.1 Willar, Dan E. (27 January 1983). "अंतरिक्ष O(n) में लॉग-लघुगणकीय सबसे खराब स्थिति वाले श्रेणी प्रश्न संभव हैं". Information Processing Letters. ScienceDirect. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3.

[20] Sartaj Sahni (2004). "Data Structures, Algorithms, & Applications in C++: Tries". University of Florida. Archived from the original on 16 July 2016. Retrieved 17 April 2022. {{cite web}}: |archive-date= / |archive-url= timestamp mismatch (help)

[21] Mehta, Dinesh P.; Sahni, Sartaj (7 March 2018). "Tries". डेटा संरचनाओं और अनुप्रयोगों की पुस्तिका (2 ed.). Chapman & Hall, University of Florida. ISBN 978-1498701853.

[22] Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard E. Watson (1 March 2000). "न्यूनतम एसाइक्लिक परिमित-राज्य ऑटोमेटा का वृद्धिशील निर्माण". Computational Linguistics. MIT Press. 26 (1): 3–16. arXiv:cs/0007009. Bibcode:2000cs........7009D. doi:10.1162/089120100561601.

[23] "Patricia tree". National Institute of Standards and Technology. Archived from the original on 14 February 2022. Retrieved 17 April 2022.

[maxime09-24] 24.0 ^24.1 ^24.2 Crochemore, Maxime; Lecroq, Thierry (2009). "Trie". डेटाबेस सिस्टम का विश्वकोश. Boston, United States: Springer Publishing. Bibcode:2009eds..book.....L. doi:10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0 – via HAL (open archive).

[prieto16-25] 25.0 ^25.1 ^25.2 Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (March 2016). "व्यावहारिक संपीड़ित स्ट्रिंग शब्दकोश". Information Systems. Elsevier. 56: 73–108. doi:10.1016/j.is.2015.08.008. ISSN 0306-4379.

[26] Kärkkäinen, Juha. "Lecture 2" (PDF). University of Helsinki. एक ट्राइ में नोड्स का प्रीऑर्डर उन स्ट्रिंग्स के लेक्सिकोग्राफ़िकल क्रम के समान है जो वे प्रतिनिधित्व करते हैं, यह मानते हुए कि नोड के बच्चों को किनारे के लेबल द्वारा ऑर्डर किया गया है।

[27] Kallis, Rafael (2018). "The Adaptive Radix Tree (Report #14-708-887)" (PDF). University of Zurich: Department of Informatics, Research Publications.

[cachestringsort-28] Ranjan Sinha and Justin Zobel and David Ring (Feb 2006). "प्रतिलिपि का उपयोग करके कैश-कुशल स्ट्रिंग सॉर्टिंग" (PDF). ACM Journal of Experimental Algorithmics. 11: 1–32. doi:10.1145/1187436.1187439. S2CID 3184411.

[stringradix-29] J. Kärkkäinen and T. Rantala (2008). "Engineering Radix Sort for Strings". In A. Amir and A. Turpin and A. Moffat (ed.). स्ट्रिंग प्रोसेसिंग और सूचना पुनर्प्राप्ति, प्रोक। शिखर. Lecture Notes in Computer Science. Vol. 5280. Springer. pp. 3–14. doi:10.1007/978-3-540-89097-3_3. ISBN 978-3-540-89096-6.

[30] Giancarlo, Raffaele (28 May 1992). "अनुप्रयोगों के साथ वर्गाकार मैट्रिक्स में प्रत्यय वृक्ष का सामान्यीकरण". SIAM Journal on Computing. Society for Industrial and Applied Mathematics. 24 (3): 520–562. doi:10.1137/S0097539792231982. ISSN 0097-5397.

[Xu12-31] Yang, Lai; Xu, Lida; Shi, Zhongzhi (23 March 2012). "शब्दकोष खोज के लिए एक उन्नत गतिशील हैश TRIE एल्गोरिथ्म". Enterprise Information Systems. 6 (4): 419–432. Bibcode:2012EntIS...6..419Y. doi:10.1080/17517575.2012.665483. S2CID 37884057.

[32] Transier, Frederik; Sanders, Peter (December 2010). "इन-मेमोरी टेक्स्ट सर्च इंजन की इंजीनियरिंग बुनियादी एल्गोरिदम". ACM Transactions on Information Systems. Association for Computing Machinery. 29 (1): 1–37. doi:10.1145/1877766.1877768. S2CID 932749.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

@@ Line 1: / Line 1: @@
-{{short description|K-ary search tree data structure}}
 {{about|a tree data structure|the French commune|Trie-sur-Baïse}}
-{{good article}}
 {{Infobox data structure
 | name=Trie
@@ Line 17: / Line 16: @@
 | type=tree
 }}
-[[Image:trie example.svg|thumb|250px|चित्र 1: कुंजियों के लिए ट्राई A, to, tea, ted, ten, i, in, और inn। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ  मनमाना पूर्णांक मान सम्बद्ध होता है।|alt=एक त्रि का चित्रण। रूट नोड का प्रतिनिधित्व करने वाला एकल खाली सर्कल, तीन बच्चों को इंगित करता है। प्रत्येक बच्चे के लिए तीर को अलग-अलग अक्षर से चिह्नित किया गया है। बच्चों के पास स्वयं तीरों और चाइल्ड नोड्स का समान सेट होता है, नोड्स के साथ जो नीले पूर्णांक मान वाले पूर्ण शब्दों के अनुरूप होते हैं।]][[कंप्यूटर विज्ञान]] में '''ट्राई''' जिसे डिजिटल ट्री या उपसर्ग ट्री भी कहा जाता है<ref name="cvr14">{{cite web|url=https://bioinformatics.cvr.ac.uk/trie-data-structure/|publisher=CVR, [[University of Glasgow]]|title=डेटा संरचना का प्रयास करें|first=Maha|last=Maabar|date=17 November 2014|access-date=17 April 2022|archive-date=27 January 2021|url-status=live|archive-url=https://web.archive.org/web/20210127130913/https://bioinformatics.cvr.ac.uk/trie-data-structure/}}</ref> जोकि एक प्रकार का के-एरी [[ खोज वृक्ष |खोज ट्री]] है। ट्री ([[डेटा संरचना]]) डेटा संरचना जिसका उपयोग  सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये कुंजियाँ अधिकतर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि व्यक्तिगत [[ चरित्र (कंप्यूटिंग) |चरित्र (कंप्यूटिंग)]] द्वारा परिभाषित होते हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनर्प्राप्त करने, उसे परिवर्तित करने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए [[गहराई-पहली खोज]] को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है।
+[[Image:trie example.svg|thumb|250px|चित्र 1: कुंजियों के लिए ट्राई A, to, tea, ted, ten, i, in, और inn। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ  मनमाना पूर्णांक मान सम्बद्ध होता है।|alt=एक त्रि का चित्रण। रूट नोड का प्रतिनिधित्व करने वाला एकल खाली सर्कल, तीन बच्चों को इंगित करता है। प्रत्येक बच्चे के लिए तीर को अलग-अलग अक्षर से चिह्नित किया गया है। बच्चों के पास स्वयं तीरों और चाइल्ड नोड्स का समान सेट होता है, नोड्स के साथ जो नीले पूर्णांक मान वाले पूर्ण शब्दों के अनुरूप होते हैं।]][[कंप्यूटर विज्ञान]] में '''ट्राई''' जिसे डिजिटल ट्री या प्रिफिक्स ट्री भी कहा जाता है<ref name="cvr14">{{cite web|url=https://bioinformatics.cvr.ac.uk/trie-data-structure/|publisher=CVR, [[University of Glasgow]]|title=डेटा संरचना का प्रयास करें|first=Maha|last=Maabar|date=17 November 2014|access-date=17 April 2022|archive-date=27 January 2021|url-status=live|archive-url=https://web.archive.org/web/20210127130913/https://bioinformatics.cvr.ac.uk/trie-data-structure/}}</ref> जो एक प्रकार का ''k-ary'' [[ खोज वृक्ष |सर्च ट्री]] है। ट्री ([[डेटा संरचना]]) डेटा संरचना का उपयोग  सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये '''कुंजियाँ (<math>\text{key}</math>)''' अधिकतर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि विशिष्ट [[ चरित्र (कंप्यूटिंग) |अक्षरों (कंप्यूटिंग)]] द्वारा परिभाषित होते हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनः प्राप्त करने, उसे परिवर्तित करने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए [[गहराई-पहली खोज|डेप्थ-फर्स्ट सर्च]] को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है।
 [[बाइनरी सर्च ट्री]] के विपरीत ट्राई में नोड्स अपनी संबंधित कुंजी को संग्रहीत नहीं करते हैं। इसके स्थान पर ट्राई में एक नोड की स्थिति उस कुंजी को परिभाषित करती है जिसके साथ वह संबद्ध है। यह प्रत्येक कुंजी के मान को डेटा संरचना में वितरित करता है और इसका अर्थ है कि आवश्यक नहीं कि प्रत्येक नोड का एक संबद्ध मान हो।
-नोड के सभी छोटे भागों में उस मूल नोड से जुड़े स्ट्रिंग का सामान्य [[उपसर्ग]] होता है और रूट [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] से सम्बद्ध होता है। इसके उपसर्ग द्वारा पहुंच योग्य डेटा को संग्रहीत करने का यह कार्य [[ मूलांक वृक्ष |मूलांक ट्री]] को नियोजित करके मेमोरी-अनुकूलित उपाय से पूरा किया जा सकता है।
+नोड के सभी छोटे भागों में उस मूल नोड से जुड़े स्ट्रिंग का सामान्य [[उपसर्ग|प्रिफिक्स]] होता है और रूट [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] से सम्बद्ध होता है। इसके प्रिफिक्स द्वारा पहुंच योग्य डेटा को संग्रहीत करने का यह कार्य [[ मूलांक वृक्ष |रेडिक्स ट्री]] को नियोजित करके मेमोरी-अनुकूलित उपाय से पूरा किया जा सकता है।
-जबकि कोशिशों को कैरेक्टर स्ट्रिंग्स द्वारा कुंजीबद्ध किया जा सकता है लेकिन ऐसा होना आवश्यक नहीं है। समान एल्गोरिदम को किसी भी अंतर्निहित प्रकार की ऑर्डर की गई सूचियों के लिए अनुकूलित किया जा सकता है उदाहरण के लिए अंकों या आकृतियों का क्रम[[परिवर्तन]]। विशेष रूप से 'बिटवाइज़ ट्राई' को अलग-अलग बिट्स पर कुंजीबद्ध किया जाता है जो निश्चित-लंबाई वाले बाइनरी डेटा का एक टुकड़ा बनाता है जैसे पूर्णांक या [[ स्मृति पता | स्मृति पता]]। ट्राई की कुंजी लुकअप जटिलता कुंजी आकार के समानुपाती रहती है। अनुभवहीन कार्यान्वयन में ट्राइ की विशाल स्थान आवश्यकता से निपटने के लिए संपीड़ित कोशिशों जैसे विशिष्ट ट्राइ कार्यान्वयन का उपयोग किया जाता है।
+जबकि ट्राई को कैरेक्टर स्ट्रिंग्स द्वारा कुंजीबद्ध किया जा सकता है लेकिन ऐसा होना आवश्यक नहीं है। समान एल्गोरिदम को किसी भी अंतर्निहित प्रकार की ऑर्डर की गई सूचियों के लिए अनुकूलित किया जा सकता है उदाहरण के लिए अंकों या आकृतियों का क्रम [[परिवर्तन]]। विशेष रूप से 'बिटवाइज़ ट्राई' को अलग-अलग बिट्स पर कुंजीबद्ध किया जाता है जो निश्चित-लंबाई वाले बाइनरी डेटा का एक टुकड़ा बनाता है जैसे पूर्णांक या [[ स्मृति पता |मेमोरी एड्रेस]]। ट्राई की कुंजी लुकअप जटिलता कुंजी आकार के समानुपाती रहती है। अनुभवहीन कार्यान्वयन में ट्राइ की विशाल स्पेस आवश्यकता से निपटने के लिए कंप्रेस्ड ट्राई जैसे विशिष्ट ट्राइ कार्यान्वयन का उपयोग किया जाता है।
 ==इतिहास, व्युत्पत्ति, और उच्चारण==
 स्ट्रिंग्स के सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार सन 1912 में एक्सल थ्यू द्वारा संक्षेप में वर्णित किया गया था।<ref name=thue>{{cite journal|last=Thue|first=Axel|title=Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen|year=1912|pages=1–67|url=https://archive.org/details/skrifterutgitavv121chri/page/n11/mode/2up|journal=Skrifter Udgivne Af Videnskabs-Selskabet I Christiania|volume=1912|number=1}} Cited by Knuth.</ref><ref name=KnuthVol3/>ट्राइज़ का वर्णन पहली बार सन1959 में रेने डे ला ब्रिंडैस द्वारा कंप्यूटर संदर्भ में किया गया था।<ref>{{cite conference |first=René |last=de la Briandais |year=1959 |title=परिवर्तनीय लंबाई कुंजियों का उपयोग करके फ़ाइल खोज|conference=Proc. Western J. Computer Conf. |pages=295–298 |doi=10.1145/1457838.1457895 |s2cid=10963780 |url=https://pdfs.semanticscholar.org/3ce3/f4cc1c91d03850ed84ef96a08498e018d18f.pdf |archive-url=https://web.archive.org/web/20200211163605/https://pdfs.semanticscholar.org/3ce3/f4cc1c91d03850ed84ef96a08498e018d18f.pdf |url-status=dead |archive-date=2020-02-11 }} Cited by Brass and by Knuth.</ref><ref name=KnuthVol3/><ref name="brass">{{cite book|last=Brass|first=Peter|title=उन्नत डेटा संरचनाएँ|publisher=[[Cambridge University Press]]|date=8 September 2008|isbn= 978-0521880374|location=[[UK]]|doi=10.1017/CBO9780511800191|url=https://www.cambridge.org/core/books/advanced-data-structures/D56E2269D7CEE969A3B8105AD5B9254C}}</ref>{{rp|p=336}}
-इस विचार का वर्णन सन 1960 में [[एडवर्ड फ्रेडकिन]] द्वारा स्वतंत्र रूप से किया गया था<ref name=triememory/> जिन्होंने ट्राई शब्द का उच्चारण करते हुए इसे गढ़ा {{IPAc-en|ˈ|t|r|iː}} (ट्री के रूप में), पुनर्प्राप्ति के मध्य अक्षर के पश्चात।<ref name = DADS>{{cite web|url=https://xlinux.nist.gov/dads/HTML/प्रयास करें.html|title=प्रयास करें|first=Paul E.|last=Black|date=2009-11-16|work=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology]]|archive-url=https://web.archive.org/web/20110429080033/http://xlinux.nist.gov/dads/HTML/प्रयास करें.html|url-status=live|archive-date=2011-04-29}}</ref><ref name="Liang1983"/>जबकि अन्य लेखक इसका उच्चारण करते हैं {{IPAc-en|ˈ|t|r|aɪ}} (जैसा ट्राई करें) इसे मौखिक रूप से ट्री से पृथक करने के प्रयास में।<ref name=DADS/><ref name="Liang1983"/><ref name = KnuthVol3>{{cite book|last=Knuth|first=Donald|author-link=Donald Knuth|title=The Art of Computer Programming Volume 3: Sorting and Searching|edition=2nd|year=1997|publisher=Addison-Wesley|isbn=0-201-89685-0|page=492|chapter=6.3: Digital Searching}}</ref>
+इस विचार का वर्णन सन 1960 में [[एडवर्ड फ्रेडकिन]] द्वारा स्वतंत्र रूप से किया गया था<ref name=triememory/> जिन्होंने ट्राई शब्द का उच्चारण करते हुए इसे गढ़ा {{IPAc-en|ˈ|t|r|iː}} (ट्री के रूप में), पुनः प्राप्ति के मध्य अक्षर के पश्चात।<ref name = DADS>{{cite web|url=https://xlinux.nist.gov/dads/HTML/प्रयास करें.html|title=प्रयास करें|first=Paul E.|last=Black|date=2009-11-16|work=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology]]|archive-url=https://web.archive.org/web/20110429080033/http://xlinux.nist.gov/dads/HTML/प्रयास करें.html|url-status=live|archive-date=2011-04-29}}</ref><ref name="Liang1983"/>जबकि अन्य लेखक इसका उच्चारण {{IPAc-en|ˈ|t|r|aɪ}} (जैसा ट्राई करें) इसे मौखिक रूप से ट्री से पृथक करने के प्रयास में करते हैं।<ref name=DADS/><ref name="Liang1983"/><ref name = KnuthVol3>{{cite book|last=Knuth|first=Donald|author-link=Donald Knuth|title=The Art of Computer Programming Volume 3: Sorting and Searching|edition=2nd|year=1997|publisher=Addison-Wesley|isbn=0-201-89685-0|page=492|chapter=6.3: Digital Searching}}</ref>
 == अवलोकन ==
-'''ट्राई,''' स्ट्रिंग-अनुक्रमित लुक-अप डेटा संरचना का रूप है जिसका उपयोग उन शब्दों की शब्दकोश सूची को संग्रहीत करने के लिए किया जाता है जिन्हें इस उपाय से खोजा जा सकता है जो [[स्वत: पूर्ण]] की कुशल पीढ़ी की अनुमति देता है।<ref>{{cite web|url=https://ds.cs.rutgers.edu/assignment-trie/|title=प्रयास करें|year=2022|publisher=School of Arts and Science, [[Rutgers University]]|archive-url=https://ghostarchive.org/archive/Vagxe|url-status=live|archive-date=17 April 2022|access-date=17 April 2022}}</ref><ref>{{cite journal|publisher=[[Syracuse University]]|url=https://surface.syr.edu/eecs_techreports/162/ |doi=10.1017/S0960129500000803|first1=Richard H.|last1=Connelly|first2=F. Lockwood|last2=Morris|year=1993|title= ट्राई डेटा संरचना का सामान्यीकरण|journal= Mathematical Structures in Computer Science|volume=5 |issue=3 |pages=381–418 |s2cid=18747244 }}</ref>{{rp|p=1}} '''उपसर्ग ट्राई''' क्रमबद्ध ट्री डेटा संरचना है जिसका उपयोग एक परिमित वर्णमाला सेट पर स्ट्रिंग्स के सेट के प्रतिनिधित्व में किया जाता है जो सामान्य उपसर्गों के साथ शब्दों के कुशल भंडारण की अनुमति देता है।<ref name="cvr14" />
+'''ट्राई,''' स्ट्रिंग-अनुक्रमित लुक-अप डेटा संरचना का रूप है जिसका उपयोग उन शब्दों की शब्दकोश सूची को संग्रहीत करने के लिए किया जाता है जिन्हें इस उपाय से खोजा जा सकता है जो [[स्वत: पूर्ण]] की कुशल पीढ़ी की अनुमति देता है।<ref>{{cite web|url=https://ds.cs.rutgers.edu/assignment-trie/|title=प्रयास करें|year=2022|publisher=School of Arts and Science, [[Rutgers University]]|archive-url=https://ghostarchive.org/archive/Vagxe|url-status=live|archive-date=17 April 2022|access-date=17 April 2022}}</ref><ref>{{cite journal|publisher=[[Syracuse University]]|url=https://surface.syr.edu/eecs_techreports/162/ |doi=10.1017/S0960129500000803|first1=Richard H.|last1=Connelly|first2=F. Lockwood|last2=Morris|year=1993|title= ट्राई डेटा संरचना का सामान्यीकरण|journal= Mathematical Structures in Computer Science|volume=5 |issue=3 |pages=381–418 |s2cid=18747244 }}</ref>{{rp|p=1}} '''प्रिफिक्स ट्राई''' क्रमबद्ध ट्री डेटा संरचना है जिसका उपयोग एक परिमित वर्णमाला सेट पर स्ट्रिंग्स के सेट के प्रतिनिधित्व में किया जाता है जो सामान्य प्रिफिक्स के साथ शब्दों के कुशल भंडारण की अनुमति देता है।<ref name="cvr14" />
-ट्राई बाइनरी खोज ट्री की तुलना में [[स्ट्रिंग-खोज एल्गोरिदम]] जैसे पूर्वानुमानित पाठ, [[अनुमानित स्ट्रिंग मिलान]] और [[वर्तनी जांच]] पर प्रभावशाली हो सकते हैं।<ref name="aho75" /><ref name="Liang1983" />{{r|reema18|p=358}} ट्राई को ट्री के आकार के [[नियतात्मक परिमित ऑटोमेटन|नियतात्मक परिमित ऑटोमेशन]] के रूप में देखा जा सकता है।<ref>{{cite conference|conference= International Conference on Implementation and Application of Automata |title=स्ट्रिंग्स के सेट से न्यूनतम, चक्रीय, नियतात्मक, परिमित-राज्य ऑटोमेटा के लिए निर्माण एल्गोरिदम की तुलना|first=Jan|last=Daciuk|date=24 June 2003|doi=10.1007/3-540-44977-9_26|url=https://link.springer.com/chapter/10.1007/3-540-44977-9_26|isbn= 978-3-540-40391-3|publisher=[[Springer Publishing]]|pages=255–261}}</ref>
+ट्राई बाइनरी सर्च ट्री की तुलना में [[स्ट्रिंग-खोज एल्गोरिदम|स्ट्रिंग-सर्च एल्गोरिदम]] जैसे पूर्वानुमानित पाठ, [[अनुमानित स्ट्रिंग मिलान]] और [[वर्तनी जांच]] पर प्रभावशाली हो सकते हैं।<ref name="aho75" /><ref name="Liang1983" />{{r|reema18|p=358}} ट्राई को ट्री के आकार के [[नियतात्मक परिमित ऑटोमेटन|नियतात्मक परिमित ऑटोमेशन]] के रूप में देखा जा सकता है।<ref>{{cite conference|conference= International Conference on Implementation and Application of Automata |title=स्ट्रिंग्स के सेट से न्यूनतम, चक्रीय, नियतात्मक, परिमित-राज्य ऑटोमेटा के लिए निर्माण एल्गोरिदम की तुलना|first=Jan|last=Daciuk|date=24 June 2003|doi=10.1007/3-540-44977-9_26|url=https://link.springer.com/chapter/10.1007/3-540-44977-9_26|isbn= 978-3-540-40391-3|publisher=[[Springer Publishing]]|pages=255–261}}</ref>
 ==संचालन ==
-[[File:Trie representation.png|thumb|right|400px|चित्र 2: ट्राई स्ट्रिंग सेट का प्रतिनिधित्व: see, sells और she।]]विभिन्न परिचालनों (स्ट्रिंग कुंजी का सम्मिलन, विलोपन और लुकअप) का समर्थन करने का प्रयास करता है। <math>\text{nodes}</math> प्रयत्नों से बना है  जिसमें ऐसे लिंक सम्मिलित हैं जो या तो अन्य चाइल्ड प्रत्यय चाइल्ड नोड्स के संदर्भ हैं या <math>\text{nil}</math>।  रूट को छोड़कर, प्रत्येक नोड को केवल अन्य नोड द्वारा इंगित किया जाता है जिसे पैरेंट कहा जाता है। प्रत्येक नोड में <math>\text{R}</math> लिंक सम्मिलित है जहाँ <math>\text{R}</math> लागू वर्णमाला (औपचारिक भाषाओं) की [[प्रमुखता]] है जबकि कोशिशों की पर्याप्त संख्या <math>\text{nil}</math> लिंक है। अधिकतर स्थितियों में <math>\text{Children}</math> का आकार (अहस्ताक्षरित) [[ASCII]] की स्थितियों में सरणी [[अक्षरों को सांकेतिक अक्षरों में बदलना|अक्षरों को सांकेतिक अक्षरों में परिवर्तन]] की बिटलेंथ - 256 है।<ref name="robert11">{{cite book|title=एल्गोरिदम|edition=4|first1=Robert|last1=Sedgewick|first2=Kevin|last2=Wayne|author1-link= Robert_Sedgewick_(computer_scientist) |publisher=[[Addison-Wesley]], [[Princeton University]]|date=3 April 2011|isbn= 978-0321573513 |url=https://algs4.cs.princeton.edu/home/}}</ref>{{rp|p=732}} <math>\text{nil}</math> h> भीतर लिंक <math>\text{Children}</math> में <math>\text{Node}</math> निम्नलिखित विशेषताओं पर जोर देता है:{{r|robert11|p=734}}{{r|brass|p=336}}
+[[File:Trie representation.png|thumb|right|400px|चित्र 2: ट्राई स्ट्रिंग सेट का प्रतिनिधित्व: see, sells और she।]]'''ट्राई''', विभिन्न परिचालनों (स्ट्रिंग कुंजी का इंसर्शन, डिलीशन और लुकअप) का समर्थन करता है। <math>\text{nodes}</math> द्वारा ट्राई का निर्माण होता है जिसमें ऐसे लिंक सम्मिलित हैं जो या तो अन्य चाइल्ड सफिक्स चाइल्ड नोड्स के संदर्भ हैं या <math>\text{nil}</math>।  रूट को छोड़कर, प्रत्येक नोड को केवल अन्य नोड द्वारा इंगित किया जाता है जिसे पैरेंट कहा जाता है। प्रत्येक नोड में <math>\text{R}</math> लिंक सम्मिलित है जहाँ <math>\text{R}</math> लागू वर्णमाला (औपचारिक भाषाओं) की [[प्रमुखता]] है जबकि ट्राई की पर्याप्त संख्या <math>\text{nil}</math> लिंक है। अधिकतर स्थितियों में <math>\text{Children}</math> का आकार (अहस्ताक्षरित) [[ASCII]] की स्थितियों में सरणी [[अक्षरों को सांकेतिक अक्षरों में बदलना|अक्षरों का सांकेतिक अक्षरों में परिवर्तन]] की बिटलेंथ - 256 है।<ref name="robert11">{{cite book|title=एल्गोरिदम|edition=4|first1=Robert|last1=Sedgewick|first2=Kevin|last2=Wayne|author1-link= Robert_Sedgewick_(computer_scientist) |publisher=[[Addison-Wesley]], [[Princeton University]]|date=3 April 2011|isbn= 978-0321573513 |url=https://algs4.cs.princeton.edu/home/}}</ref>{{rp|p=732}} <math>\text{nil}</math> h> भीतर लिंक <math>\text{Children}</math> में <math>\text{Node}</math> निम्नलिखित विशेषताओं पर जोर देता है:{{r|robert11|p=734}}{{r|brass|p=336}}
 # वर्ण और स्ट्रिंग कुंजियाँ अंतर्निहित रूप से ट्राई डेटा संरचना प्रतिनिधित्व में संग्रहीत होती हैं और इसमें स्ट्रिंग-समाप्ति को इंगित करने वाला वर्ण प्रहरी मान सम्मिलित होता है।
-# प्रत्येक नोड में सेट की मजबूत कुंजियों के उपसर्ग का संभावित लिंक होता है।
+# प्रत्येक नोड में सेट की मजबूत कुंजियों के प्रिफिक्स का संभावित लिंक होता है।
-ट्राई में नोड्स का बुनियादी [[समग्र डेटा प्रकार]] इस प्रकार है; <math>\text{Node}</math> वैकल्पिक रूप से सम्मिलित हो सकता है <math>\text{Value}</math> जो स्ट्रिंग या टर्मिनल नोड के अंतिम अक्षर में संग्रहीत प्रत्येक कुंजी से सम्बद्ध हुआ है।
+ट्राई में नोड्स का बुनियादी [[समग्र डेटा प्रकार]] इस प्रकार है; <math>\text{Node}</math> वैकल्पिक रूप से सम्मिलित हो सकता है तथा <math>\text{Value}</math> जो स्ट्रिंग या टर्मिनल नोड के अंतिम अक्षर में संग्रहीत प्रत्येक कुंजी से सम्बद्ध हुआ है।
 {|
 |- style="vertical-align:top"
@@ Line 54: / Line 53: @@
 ===खोजना ===
-ट्राइ में <math>\text{Value}</math> की खोज स्ट्रिंग कुंजी में वर्णों द्वारा निर्देशित की जाती है क्योंकि ट्राइ में प्रत्येक नोड में दिए गए स्ट्रिंग में प्रत्येक संभावित वर्ण के लिए संबंधित लिंक होता है। इस प्रकार ट्राइ के भीतर स्ट्रिंग का अनुसरण करने से दी गई <math>\text{Value}</math> स्ट्रिंग कुंजी के लिए संबंधित परिणाम प्राप्त होता है। <math>\text{nil}</math> खोज निष्पादन के भीतर लिंक कुंजी की अस्तित्वहीनता को इंगित करता है।{{r| robert11|p=732-733}}
+ट्राइ में <math>\text{Value}</math> की सर्च स्ट्रिंग कुंजी में वर्णों द्वारा निर्देशित की जाती है क्योंकि ट्राइ में प्रत्येक नोड में दिए गए स्ट्रिंग में प्रत्येक संभावित वर्ण के लिए संबंधित लिंक होता है। इस प्रकार ट्राइ के भीतर स्ट्रिंग का अनुसरण करने से दी गई <math>\text{Value}</math> स्ट्रिंग कुंजी के लिए संबंधित परिणाम प्राप्त होता है। <math>\text{nil}</math> सर्च निष्पादन के भीतर लिंक कुंजी की अस्तित्वहीनता को इंगित करता है।{{r| robert11|p=732-733}}
-निम्नलिखित स्यूडोकोड किसी दी गई स्ट्रिंग कुंजी (<math>\text{key}</math>) के लिए जड़ित ट्राइ (<math>\text{x}</math>) में खोज प्रक्रिया को लागू करता है{{r|gonnet91|p=135}}
+निम्नलिखित स्यूडोकोड किसी दी गई स्ट्रिंग कुंजी (<math>\text{key}</math>) के लिए जड़ित ट्राइ (<math>\text{x}</math>) में सर्च प्रक्रिया को लागू करता है{{r|gonnet91|p=135}}
 {|
 |- style="vertical-align:top"
@@ Line 69: / Line 68: @@
       '''return''' x.Value
 |}
-उपरोक्त छद्म कोड में <math>\text{x}</math> और <math>\text{key}</math> क्रमशः ट्राई के रूट नोड और स्ट्रिंग कुंजी के सूचक से मेल खाते हैं। मानक ट्राई में <math>O(\text{dm})</math> खोज अभियान चलता है तथा <math>\text{m}</math> स्ट्रिंग पैरामीटर <math>\text{key}</math> आकार का है और <math>\text{d}</math> वर्णमाला (औपचारिक भाषाएँ) से मेल खाती है।<ref name="patil_12">{{cite book|first=Virsha H.|last=Patil|date=10 May 2012|isbn= 9780198066231|publisher=[[Oxford University Press]]|url=https://global.oup.com/academic/product/data-structures-using-c-9780198066231?cc=ca&lang=en&|title=C++ का उपयोग कर डेटा संरचनाएँ}}</ref>{{rp|p=754}} दूसरी ओर [[बाइनरी खोज वृक्ष|बाइनरी खोज ट्री]]  <math>O(m \log n)</math> लें सबसे खराब स्थिति में, चूँकि खोज ट्री की ऊँचाई पर निर्भर करती है (<math>\log n</math>) बीएसटी का (संतुलित पेड़ों के मामले में), जहां <math>\text{n}</math> और <math>\text{m}</math> चाबियों की संख्या और चाबियों की लंबाई।{{r|reema18|p=358}}
+उपरोक्त छद्म कोड में <math>\text{x}</math> और <math>\text{key}</math> क्रमशः ट्राई के रूट नोड और स्ट्रिंग कुंजी के सूचक से मेल खाते हैं। मानक ट्राई में <math>O(\text{dm})</math> सर्च अभियान चलता है तथा <math>\text{m}</math> स्ट्रिंग पैरामीटर <math>\text{key}</math> आकार का है और <math>\text{d}</math> वर्णमाला (औपचारिक भाषाएँ) से मेल खाती है।<ref name="patil_12">{{cite book|first=Virsha H.|last=Patil|date=10 May 2012|isbn= 9780198066231|publisher=[[Oxford University Press]]|url=https://global.oup.com/academic/product/data-structures-using-c-9780198066231?cc=ca&lang=en&|title=C++ का उपयोग कर डेटा संरचनाएँ}}</ref>{{rp|p=754}} दूसरी ओर [[बाइनरी खोज वृक्ष|बाइनरी सर्च ट्री]]  <math>O(m \log n)</math> लें सबसे खराब स्थिति में, चूँकि सर्च ट्री की ऊँचाई पर निर्भर करती है (<math>\log n</math>) बीएसटी का (संतुलित ट्री की स्थिति में), जहां <math>\text{n}</math> और <math>\text{m}</math>, <math>\text{key}</math> की संख्या और <math>\text{key}</math> की लंबाई है।{{r|reema18|p=358}}
-यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं तो बीएसटी की तुलना में ट्राई कम स्थान घेरता है क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।{{r|reema18|p=358}} ट्री के टर्मिनल नोड में <math>\text{Value}</math> एक गैर-शून्य होता है और यदि संबंधित मान ट्राई में पाया जाता है तो यह खोज हिट है और यदि ऐसा नहीं है तो खोज मिस हो जाती है।{{r|robert11|p=733}}
+यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं तो BST की तुलना में ट्राई कम स्थान घेरता है क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।{{r|reema18|p=358}} ट्री के टर्मिनल नोड में <math>\text{Value}</math> गैर-शून्य होता है और यदि संबंधित मान ट्राई में पाया जाता है तो यह सर्च हिट है और यदि ऐसा नहीं है तो सर्च मिस हो जाती है।{{r|robert11|p=733}}
 === प्रविष्टि ===
-ट्राई में सम्मिलन को कैरेक्टर एन्कोडिंग, कैरेक्टर मैप और कोड पेजों को इंडेक्स के रूप में उपयोग करके निर्देशित किया जाता है। <math>\text{Children}</math> स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने तक सरणी।{{r|robert11|p=733-734}} ट्राई में प्रत्येक नोड [[ मूलांक छँटाई |मूलांक छँटाई]] रूटीन की कॉल से मेल खाता है क्योंकि ट्राई संरचना टॉप-डाउन रेडिक्स सॉर्ट के पैटर्न के निष्पादन को दर्शाती है।{{r| gonnet91|p=135}}
+ट्राई में इंसर्शन को कैरेक्टर एन्कोडिंग, कैरेक्टर मैप और कोड पेजों को इंडेक्स के रूप में उपयोग करके निर्देशित किया जाता है। <math>\text{Children}</math> स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने तक सरणी।{{r|robert11|p=733-734}} ट्राई में प्रत्येक नोड [[ मूलांक छँटाई |रेडिक्स सॉर्ट]] रूटीन की कॉल से मेल खाता है क्योंकि ट्राई संरचना टॉप-डाउन रेडिक्स सॉर्ट के पैटर्न के निष्पादन को दर्शाती है।{{r| gonnet91|p=135}}
 {|
 |- style="vertical-align:top"
@@ Line 88: / Line 87: @@
         x.Is-Terminal := True
 |}
-यदि <math>\text{nil}</math> स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने से पहले लिंक का सामना करना पड़ता है एवं नया <math>\text{Node}</math> बनाया गया है जैसे पंक्ति 3-5 के साथ।{{r|robert11|p=745}} <math>\text{x.Value}</math> इनपुट <math>\text{value}</math> को सौंपा जाता है; यदि <math>\text{x.Value}</math> सम्मिलन के समय <math>\text{nil}</math> नहीं था एवं दी गई स्ट्रिंग कुंजी से सम्बद्ध मान वर्तमान कुंजी से प्रतिस्थापित हो जाता है।
+यदि <math>\text{nil}</math> स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने से पहले लिंक का सामना करना पड़ता है एवं नया <math>\text{Node}</math> बनाया गया है जैसे पंक्ति 3-5 के साथ।{{r|robert11|p=745}} <math>\text{x.Value}</math> इनपुट <math>\text{value}</math> को सौंपा जाता है; यदि <math>\text{x.Value}</math> इंसर्शन के समय <math>\text{nil}</math> नहीं था एवं दी गई स्ट्रिंग कुंजी से सम्बद्ध मान वर्तमान कुंजी से प्रतिस्थापित हो जाता है।
 === विलोपन ===
-ट्राई से कुंजी-मूल्य जोड़ी को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत पर चिह्नित करना सम्मिलित है। <math>\text{nil}</math> तदनुसार.{{r|robert11|p=740}}
+ट्राई से <math>\text{key}</math>-वैल्यू पेअर को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत पर चिह्नित करना सम्मिलित है। <math>\text{nil}</math> तदनुसार.{{r|robert11|p=740}}
-जड़ित ट्राई (<math>\text{x}</math>) से स्ट्रिंग कुंजी (<math>\text{key}</math>) को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है,
+रूटेड ट्राई (<math>\text{x}</math>) से स्ट्रिंग कुंजी (<math>\text{key}</math>) को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है,
 {|
 |- style="vertical-align:top"
@@ Line 119: / Line 118: @@
 === [[हैश तालिका]]ओं के लिए प्रतिस्थापन ===
 ट्राई का उपयोग हैश टेबल को परिवर्तित करने के लिए किया जा सकता है जिसके निम्नलिखित लाभ हैं:{{r|reema18|p=358}}
-* <math>m</math> आकार की संबद्ध कुंजी के साथ एक नोड की खोज करना <math>O(m)</math> की जटिलता है जबकि अपूर्ण हैश फ़ंक्शन में कई टकराने वाली कुंजियाँ हो सकती हैं और ऐसी तालिका की सबसे खराब स्थिति वाली लुकअप गति <math>O(N)</math> होगी जहाँ <math>N</math> तालिका के भीतर नोड्स की कुल संख्या को दर्शाता है।
+* <math>m</math> आकार की संबद्ध कुंजी के साथ एक नोड की सर्च करना <math>O(m)</math> की जटिलता है जबकि अपूर्ण हैश फ़ंक्शन में कई टकराने वाली कुंजियाँ हो सकती हैं और ऐसी तालिका की सबसे खराब स्थिति वाली लुकअप गति <math>O(N)</math> होगी जहाँ <math>N</math> तालिका के भीतर नोड्स की कुल संख्या को दर्शाता है।
 * हैश टेबल के विपरीत ट्राइज़ को ऑपरेशन के लिए हैश फ़ंक्शन की आवश्यकता नहीं होती है; ट्राई में विभिन्न कुंजियों की कोई [[हैश टक्कर]] भी नहीं होती है।
 * ट्राई में बकेट जो हैश टेबल बकेट के समान होते हैं जो कुंजी टकराव को संग्रहीत करते हैं एवं केवल तभी आवश्यक होते हैं जब कुंजी एक से अधिक मान से जुड़ी होती है।
@@ Line 127: / Line 126: @@
 ==कार्यान्वयन रणनीतियाँ==
-[[File:Pointer implementation of a trie.svg|thumb|चित्र 3: बाएं-चाइल्ड के दाएं-सिबलिंग बाइनरी ट्री के रूप में कार्यान्वित ट्राइ: ऊर्ध्वाधर तीर {{mono|child}} सूचक हैं, धराशायी क्षैतिज तीर  {{mono|next}} सूचक हैं। इस ट्राई में संग्रहित स्ट्रिंग्स {{mono|{baby, bad, bank, box, dad, dance}}} का सेट है। सूचियों को शब्दकोषीय क्रम में ट्रैवर्सल की अनुमति देने के लिए क्रमबद्ध किया गया है।]]मेमोरी उपयोग और संचालन की गति के मध्य विभिन्न ट्रेड-ऑफ के अनुरूप ट्राई को कई उपायों द्वारा दर्शाया जा सकता है।{{r| brass|p=341}} किसी ट्राई का प्रतिनिधित्व करने के लिए पॉइंटर्स के वेक्टर का उपयोग करने से बड़े स्थान की खपत होती है; जबकि यदि प्रत्येक नोड वेक्टर के लिए एकल लिंक की गई सूची का उपयोग किया जाता है तो मेमोरी स्पेस को रनिंग टाइम के मूल्य पर कम किया जा सकता है क्योंकि वेक्टर <math>\text{nil}</math> की अधिकांश प्रविष्टियाँ सम्मिलित हैं।{{r| KnuthVol3|p=495}}
+[[File:Pointer implementation of a trie.svg|thumb|चित्र 3: बाएं-चाइल्ड के दाएं-सिबलिंग बाइनरी ट्री के रूप में कार्यान्वित ट्राइ: ऊर्ध्वाधर तीर {{mono|child}} सूचक हैं, धराशायी क्षैतिज तीर {{mono|next}} सूचक हैं। इस ट्राई में संग्रहित स्ट्रिंग्स {{mono|{baby, bad, bank, box, dad, dance}}} का सेट है। सूचियों को शब्दकोषीय क्रम में ट्रैवर्सल की अनुमति देने के लिए क्रमबद्ध किया गया है।]]मेमोरी उपयोग और संचालन की गति के मध्य विभिन्न ट्रेड-ऑफ के अनुरूप ट्राई को कई उपायों द्वारा दर्शाया जा सकता है।{{r| brass|p=341}} किसी ट्राई का प्रतिनिधित्व करने के लिए पॉइंटर्स के वेक्टर का उपयोग करने से बड़े स्थान की खपत होती है; जबकि यदि प्रत्येक नोड वेक्टर के लिए एकल लिंक की गई सूची का उपयोग किया जाता है तो मेमोरी स्पेस को रनिंग टाइम के मूल्य पर कम किया जा सकता है क्योंकि वेक्टर <math>\text{nil}</math> की अधिकांश प्रविष्टियाँ सम्मिलित हैं।{{r| KnuthVol3|p=495}}
 वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को छोटे वर्णमाला पर लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। {{mvar|n}} बाइट्स की एक स्ट्रिंग को वैकल्पिक रूप से {{math|2''n''}} चार-बिट इकाइयों की एक स्ट्रिंग के रूप में माना जा सकता है और प्रति नोड सोलह पॉइंटर्स के साथ ट्राइ में संग्रहीत किया जा सकता है। जबकि सबसे खराब स्थिति में लुकअप को दोगुने नोड्स पर जाने की आवश्यकता होती है जबकि स्थान की आवश्यकताएँ आठ गुना कम हो जाती हैं।{{r| brass|p= 347–352}} अन्य तकनीकों में ASCII वर्णमाला का प्रतिनिधित्व करने वाले 256 बिट्स के बिटमैप के रूप में 256 ASCII पॉइंटर्स के वेक्टर को संग्रहीत करना सम्मिलित है जो व्यक्तिगत नोड्स के आकार को नाटकीय रूप से कम कर देता है।<ref>{{cite book|last1=Bellekens|first1=Xavier|title=Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14|chapter=A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems|date=2014|publisher=ACM|location=Glasgow, Scotland, UK|isbn=978-1-4503-3033-6|pages=302:302–302:309|doi=10.1145/2659651.2659723|arxiv=1704.02272|s2cid=12943246}}</ref>
@@ Line 141: / Line 140: @@
-===संपीड़ित ट्राइ ===
+===कंप्रेस्ड ट्राइ ===
 {{main|Radix tree}}
-रेडिक्स ट्री जिसे संपीड़ित ट्राई के रूप में भी जाना जाता है ट्राई का एक अंतरिक्ष-अनुकूलित संस्करण है जिसमें केवल चाइल्ड वाले नोड्स अपने पेरेंट के साथ विलय हो जाते हैं; एकल चाइल्ड के साथ नोड्स की शाखाओं को हटाने से अंतरिक्ष और समय मेट्रिक्स दोनों में उन्नत परिणाम मिलते हैं।<ref>{{cite web|url=https://www.cise.ufl.edu/~sahni/dsaac/enrich/c16/tries.htm|publisher=[[University of Florida]]|access-date=17 April 2022|archive-url=https://web.archive.org/web/20160703161316/http://www.cise.ufl.edu/~sahni/dsaac/enrich/c16/tries.htm|archive-date=16 July 2016|url-status=live|author=Sartaj Sahni|title=Data Structures, Algorithms, & Applications in C++: Tries|year=2004}}</ref><ref>{{cite book|title=डेटा संरचनाओं और अनुप्रयोगों की पुस्तिका|first1=Dinesh P.|last1=Mehta|first2=Sartaj|last2=Sahni|isbn= 978-1498701853 |publisher=[[Chapman & Hall]], [[University of Florida]]|url=https://www.routledge.com/Handbook-of-Data-Structures-and-Applications/Mehta-Sahni/p/book/9780367572006|edition=2|date=7 March 2018|chapter=Tries}}</ref>{{rp|p=452}} यह तब सबसे अच्छा काम करता है जब ट्राई स्थिर रहता है और संग्रहीत कुंजियों का सेट उनके प्रतिनिधित्व स्थान के भीतर बहुत विरल होता है।<ref>{{cite journal|title=न्यूनतम एसाइक्लिक परिमित-राज्य ऑटोमेटा का वृद्धिशील निर्माण|volume=26|issue=1|date=1 March 2000|author1=Jan Daciuk |author2=Stoyan Mihov |author3=Bruce W. Watson |author4=Richard E. Watson |journal = [[Computational Linguistics (journal)|Computational Linguistics]] |pages=3–16|publisher=[[MIT Press]]|doi=10.1162/089120100561601|arxiv=cs/0007009|bibcode=2000cs........7009D|url=https://direct.mit.edu/coli/article/26/1/3/1628/Incremental-Construction-of-Minimal-Acyclic-Finite|doi-access=free}}</ref>{{rp|p=3–16}}
+रेडिक्स ट्री जिसे कंप्रेस्ड ट्राई के रूप में भी जाना जाता है ट्राई का एक अंतरिक्ष-अनुकूलित संस्करण है जिसमें केवल चाइल्ड वाले नोड्स अपने पेरेंट के साथ विलय हो जाते हैं; एकल चाइल्ड के साथ नोड्स की शाखाओं को हटाने से अंतरिक्ष और समय मेट्रिक्स दोनों में उन्नत परिणाम मिलते हैं।<ref>{{cite web|url=https://www.cise.ufl.edu/~sahni/dsaac/enrich/c16/tries.htm|publisher=[[University of Florida]]|access-date=17 April 2022|archive-url=https://web.archive.org/web/20160703161316/http://www.cise.ufl.edu/~sahni/dsaac/enrich/c16/tries.htm|archive-date=16 July 2016|url-status=live|author=Sartaj Sahni|title=Data Structures, Algorithms, & Applications in C++: Tries|year=2004}}</ref><ref>{{cite book|title=डेटा संरचनाओं और अनुप्रयोगों की पुस्तिका|first1=Dinesh P.|last1=Mehta|first2=Sartaj|last2=Sahni|isbn= 978-1498701853 |publisher=[[Chapman & Hall]], [[University of Florida]]|url=https://www.routledge.com/Handbook-of-Data-Structures-and-Applications/Mehta-Sahni/p/book/9780367572006|edition=2|date=7 March 2018|chapter=Tries}}</ref>{{rp|p=452}} यह तब सबसे अच्छा काम करता है जब ट्राई स्थिर रहता है और संग्रहीत कुंजियों का सेट उनके प्रतिनिधित्व स्थान के भीतर बहुत विरल होता है।<ref>{{cite journal|title=न्यूनतम एसाइक्लिक परिमित-राज्य ऑटोमेटा का वृद्धिशील निर्माण|volume=26|issue=1|date=1 March 2000|author1=Jan Daciuk |author2=Stoyan Mihov |author3=Bruce W. Watson |author4=Richard E. Watson |journal = [[Computational Linguistics (journal)|Computational Linguistics]] |pages=3–16|publisher=[[MIT Press]]|doi=10.1162/089120100561601|arxiv=cs/0007009|bibcode=2000cs........7009D|url=https://direct.mit.edu/coli/article/26/1/3/1628/Incremental-Construction-of-Minimal-Acyclic-Finite|doi-access=free}}</ref>{{rp|p=3–16}}
 एक और दृष्टिकोण ट्राइ को पैक करना है जिसमें स्वचालित [[हाइफ़नेशन एल्गोरिथ्म]] पर लागू एक विरल पैक ट्राइ का स्थान-कुशल कार्यान्वयन होता है जिसमें प्रत्येक नोड के वंशजों को मेमोरी में इंटरलीव किया जा सकता है।<ref name=Liang1983>{{cite thesis|degree=Doctor of Philosophy|title=कॉम-पुट-एर द्वारा वर्ड हाई-फेन-ए-टियन|url=http://www.tug.org/docs/liang/liang-thesis.pdf|author=Franklin Mark Liang|year=1983|publisher=Stanford University|access-date=2010-03-28|archive-url=https://web.archive.org/web/20051111105124/http://www.tug.org/docs/liang/liang-thesis.pdf|url-status=live|archive-date=2005-11-11}}</ref>
@@ Line 157: / Line 156: @@
 }}
-पेट्रीसिया ट्री संपीड़ित बाइनरी ट्राइ का विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के [[बाइनरी कोड]] का उपयोग करता है।<ref>{{cite web|url=https://xlinux.nist.gov/dads/HTML/patriciatree.html|publisher=[[National Institute of Standards and Technology]]|archive-date=14 February 2022|archive-url=https://web.archive.org/web/20220214182428/https://xlinux.nist.gov/dads/HTML/patriciatree.html|url-status=live|access-date=17 April 2022|title=Patricia tree}}</ref><ref name="gonnet91">{{cite book|title=Handbook of algorithms and data structures: in Pascal and C|edition=2|date=January 1991|isbn=978-0-201-41607-7|publisher=[[Addison-Wesley]]|location=[[Boston]], [[United States]]|first1=G. H.|last1=Gonnet|first2=R. Baeza|last2=Yates|url=https://dl.acm.org/doi/book/10.5555/103324}}</ref>{{rp|p=140}} पेट्रीसिया ट्री के प्रत्येक नोड में निर्देशिका होती है जिसे स्किप नंबर के रूप में जाना जाता है जो ट्रैवर्सल के समय रिक्त सब ट्री से बचने के लिए नोड के ब्रांचिंग इंडेक्स को संग्रहीत करता है।{{r|gonnet91|p=140-141}} कुंजियों के विरल वितरण के कारण बड़ी संख्या में लीफ-नोड्स के कारण ट्राई के सरल कार्यान्वयन में अत्यधिक भंडारण की खपत होती है; ऐसे स्थितियों के लिए पेट्रीसिया के ट्री कारगर हो सकते हैं।{{r|gonnet91|p=142}}{{r|maxime09|p=3}}
+पेट्रीसिया ट्री कंप्रेस्ड बाइनरी ट्राइ का विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के [[बाइनरी कोड]] का उपयोग करता है।<ref>{{cite web|url=https://xlinux.nist.gov/dads/HTML/patriciatree.html|publisher=[[National Institute of Standards and Technology]]|archive-date=14 February 2022|archive-url=https://web.archive.org/web/20220214182428/https://xlinux.nist.gov/dads/HTML/patriciatree.html|url-status=live|access-date=17 April 2022|title=Patricia tree}}</ref><ref name="gonnet91">{{cite book|title=Handbook of algorithms and data structures: in Pascal and C|edition=2|date=January 1991|isbn=978-0-201-41607-7|publisher=[[Addison-Wesley]]|location=[[Boston]], [[United States]]|first1=G. H.|last1=Gonnet|first2=R. Baeza|last2=Yates|url=https://dl.acm.org/doi/book/10.5555/103324}}</ref>{{rp|p=140}} पेट्रीसिया ट्री के प्रत्येक नोड में निर्देशिका होती है जिसे स्किप नंबर के रूप में जाना जाता है जो ट्रैवर्सल के समय रिक्त सब ट्री से बचने के लिए नोड के ब्रांचिंग इंडेक्स को संग्रहीत करता है।{{r|gonnet91|p=140-141}} कुंजियों के विरल वितरण के कारण बड़ी संख्या में लीफ-नोड्स के कारण ट्राई के सरल कार्यान्वयन में अत्यधिक भंडारण की खपत होती है; ऐसे स्थितियों के लिए पेट्रीसिया के ट्री कारगर हो सकते हैं।{{r|gonnet91|p=142}}{{r|maxime09|p=3}}
-स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व <math>\{in, integer, interval, string, structure\}</math> चित्र 4 में दिखाया गया है और नोड्स से सटे प्रत्येक सूचकांक मान स्किप संख्या का प्रतिनिधित्व करता है - बिट का सूचकांक जिसके साथ शाखा तय की जानी है।<ref name="maxime09">{{cite book|title=डेटाबेस सिस्टम का विश्वकोश|first1=Maxime|last1=Crochemore|first2=Thierry|last2=Lecroq|url=https://link.springer.com/referencework/10.1007/978-0-387-39940-9|doi=10.1007/978-0-387-39940-9|isbn=978-0-387-49616-0|publisher=[[Springer Publishing]]|location=[[Boston]], [[United States]]|year=2009|chapter=Trie|bibcode=2009eds..book.....L |via=[[HAL (open archive)]]}}</ref>{{rp|p=3}} नोड 0 पर स्किप नंबर 1 बाइनरी एन्कोडेड ASCII में स्थिति 1 से मेल खाता है जहां कुंजी सेट में सबसे बाईं ओर का बिट भिन्न था <math>X</math>.{{r|maxime09|p=3-4}} पेट्रीसिया ट्री में नोड्स की खोज, सम्मिलन और हटाने के लिए स्किप नंबर महत्वपूर्ण है, और प्रत्येक पुनरावृत्ति के दौरान थोड़ा मास्किंग ऑपरेशन किया जाता है।{{r|gonnet91|p=143}}
+स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व <math>\{in, integer, interval, string, structure\}</math> चित्र 4 में दिखाया गया है और नोड्स से सटे प्रत्येक सूचकांक मान स्किप संख्या का प्रतिनिधित्व करता है - बिट का सूचकांक जिसके साथ शाखा तय की जानी है।<ref name="maxime09">{{cite book|title=डेटाबेस सिस्टम का विश्वकोश|first1=Maxime|last1=Crochemore|first2=Thierry|last2=Lecroq|url=https://link.springer.com/referencework/10.1007/978-0-387-39940-9|doi=10.1007/978-0-387-39940-9|isbn=978-0-387-49616-0|publisher=[[Springer Publishing]]|location=[[Boston]], [[United States]]|year=2009|chapter=Trie|bibcode=2009eds..book.....L |via=[[HAL (open archive)]]}}</ref>{{rp|p=3}} नोड 0 पर स्किप नंबर 1 बाइनरी एन्कोडेड ASCII में स्थिति 1 से मेल खाता है जहां कुंजी सेट <math>X</math> में सबसे बाईं ओर का बिट भिन्न था।{{r|maxime09|p=3-4}} पेट्रीसिया ट्री में नोड्स की खोज, इंसर्शन और डिलीशन के लिए स्किप नंबर महत्वपूर्ण है और प्रत्येक पुनरावृत्ति के समय थोड़ा मास्किंग ऑपरेशन किया जाता है।{{r|gonnet91|p=143}}
 == अनुप्रयोग ==
-ट्राई डेटा संरचनाओं का उपयोग सामान्य रूप से पूर्वानुमानित पाठ या स्वत: पूर्ण शब्दकोशों और अनुमानित स्ट्रिंग मिलान में किया जाता है।<ref name="aho75">{{Cite journal|last1=Aho|first1=Alfred V.|last2=Corasick|first2=Margaret J.|date=Jun 1975|title=Efficient String Matching: An Aid to Bibliographic Search|url=https://pdfs.semanticscholar.org/3547/ac839d02f6efe3f6f76a8289738a22528442.pdf|journal=[[Communications of the ACM]]|volume=18|issue=6|pages=333–340|doi=10.1145/360825.360855|s2cid=207735784}}</ref> ट्राई तीव्र खोजों को सक्षम करते हैं जो कम जगह घेरते हैं एवं खासकर जब सेट में बड़ी संख्या में छोटे तार होते हैं तथा इस प्रकार वर्तनी जांच, हाइफ़नेशन अनुप्रयोगों और सबसे लंबे उपसर्ग मिलान एल्गोरिदम में उपयोग किया जाता है।<ref name="Liang1983" /><ref name="reema18">{{cite book|title= सी का उपयोग कर डेटा संरचनाएं|date=13 October 2018|edition=2|first=Reema|last=Thareja|publisher=[[Oxford University Press]]|url=https://global.oup.com/academic/product/data-structures-using-c-9780198099307|isbn= 9780198099307|url-access=subscription|chapter=Hashing and Collision}}</ref>{{rp|p=358}} जबकि यदि [[शब्दकोश]] शब्दों को संग्रहीत करना ही आवश्यक है (अर्थात प्रत्येक शब्द से जुड़े मेटाडेटा को संग्रहीत करने की कोई आवश्यकता नहीं है) एवं न्यूनतम नियतात्मक चक्रीय परिमित राज्य ऑटोमेटन (DAFSA) या रेडिक्स ट्री एक ट्राई की तुलना में कम भंडारण स्थान का उपयोग करेगा। ऐसा इसलिए है क्योंकि DAFSAs और रेडिक्स पेड़ ट्राई से समान शाखाओं को संपीड़ित कर सकते हैं जो संग्रहीत किए जा रहे विभिन्न शब्दों के समान प्रत्ययों (या भागों) से मेल खाते हैं। स्ट्रिंग शब्दकोशों का उपयोग [[प्राकृतिक भाषा प्रसंस्करण]] में भी किया जाता है जैसे कि [[पाठ कोष]] का शब्दकोष खोजना।<ref name="prieto16">{{cite journal|journal=[[Information Systems (journal)|Information Systems]]|first1=Miguel A.|last1=Martinez-Prieto|first2=Nieves|last2=Brisaboa|first3=Rodrigo|last3=Canovas|first4=Francisco|last4=Claude|first5=Gonzalo|last5=Navarro|publisher=[[Elsevier]]|volume=56|doi=10.1016/j.is.2015.08.008|url=https://www.sciencedirect.com/science/article/abs/pii/S0306437915001672|date=March 2016|title=व्यावहारिक संपीड़ित स्ट्रिंग शब्दकोश|pages=73–108|issn= 0306-4379 }}</ref>{{rp|p=73}}
+ट्राई डेटा संरचनाओं का उपयोग सामान्य रूप से पूर्वानुमानित पाठ या स्वत: पूर्ण शब्दकोशों और अनुमानित स्ट्रिंग मिलान में किया जाता है।<ref name="aho75">{{Cite journal|last1=Aho|first1=Alfred V.|last2=Corasick|first2=Margaret J.|date=Jun 1975|title=Efficient String Matching: An Aid to Bibliographic Search|url=https://pdfs.semanticscholar.org/3547/ac839d02f6efe3f6f76a8289738a22528442.pdf|journal=[[Communications of the ACM]]|volume=18|issue=6|pages=333–340|doi=10.1145/360825.360855|s2cid=207735784}}</ref> ट्राई तीव्र खोजों को सक्षम करते हैं जो कम जगह घेरते हैं एवं खासकर जब सेट में बड़ी संख्या में छोटे तार होते हैं तथा इस प्रकार वर्तनी जांच, हाइफ़नेशन अनुप्रयोगों और सबसे लंबे प्रिफिक्स मिलान एल्गोरिदम में उपयोग किया जाता है।<ref name="Liang1983" /><ref name="reema18">{{cite book|title= सी का उपयोग कर डेटा संरचनाएं|date=13 October 2018|edition=2|first=Reema|last=Thareja|publisher=[[Oxford University Press]]|url=https://global.oup.com/academic/product/data-structures-using-c-9780198099307|isbn= 9780198099307|url-access=subscription|chapter=Hashing and Collision}}</ref>{{rp|p=358}} जबकि यदि [[शब्दकोश]] शब्दों को संग्रहीत करना ही आवश्यक है (अर्थात प्रत्येक शब्द से जुड़े मेटाडेटा को संग्रहीत करने की कोई आवश्यकता नहीं है) एवं न्यूनतम DAFSA या रेडिक्स ट्री एक ट्राई की तुलना में कम भंडारण स्थान का उपयोग करेगा। ऐसा इसलिए है क्योंकि DAFSAs और रेडिक्स ट्री ट्राई से समान शाखाओं को कंप्रेस्ड कर सकते हैं जो संग्रहीत किए जा रहे विभिन्न शब्दों के समान प्रत्ययों (या भागों) से मेल खाते हैं। स्ट्रिंग शब्दकोशों का उपयोग [[प्राकृतिक भाषा प्रसंस्करण]] में भी किया जाता है जैसे कि [[पाठ कोष]] का शब्दकोष खोजना।<ref name="prieto16">{{cite journal|journal=[[Information Systems (journal)|Information Systems]]|first1=Miguel A.|last1=Martinez-Prieto|first2=Nieves|last2=Brisaboa|first3=Rodrigo|last3=Canovas|first4=Francisco|last4=Claude|first5=Gonzalo|last5=Navarro|publisher=[[Elsevier]]|volume=56|doi=10.1016/j.is.2015.08.008|url=https://www.sciencedirect.com/science/article/abs/pii/S0306437915001672|date=March 2016|title=व्यावहारिक संपीड़ित स्ट्रिंग शब्दकोश|pages=73–108|issn= 0306-4379 }}</ref>{{rp|p=73}}
 === श्रेणीबद्ध करना ===
-स्ट्रिंग कुंजियों के सेट के [[शब्दकोषीय क्रम]] को दी गई कुंजियों के लिए ट्राई बनाकर और ट्री ट्रैवर्सल  प्री-ऑर्डर कार्यान्वयन में ट्री को पार करके कार्यान्वित किया जा सकता है;<ref>{{cite web |url=https://www.cs.helsinki.fi/u/tpkarkka/opetus/12s/spa/lecture02.pdf |title=Lecture 2 |first=Juha |last=Kärkkäinen |quote="एक ट्राइ में नोड्स का प्रीऑर्डर उन स्ट्रिंग्स के लेक्सिकोग्राफ़िकल क्रम के समान है जो वे प्रतिनिधित्व करते हैं, यह मानते हुए कि नोड के बच्चों को किनारे के लेबल द्वारा ऑर्डर किया गया है।"|publisher=[[University of Helsinki]]}}</ref> यह भी मूलांक प्रकार का एक रूप है।<ref>{{Cite web|url=https://www.ifi.uzh.ch/dam/jcr:27d15f69-2a44-40f9-8b41-6d11b5926c67/ReportKallisMScBasis.pdf|title=The Adaptive Radix Tree (Report #14-708-887)|last=Kallis|first=Rafael|date=2018|website=University of Zurich: Department of Informatics, Research Publications}}</ref> ट्राई [[बर्स्टसॉर्ट]] के लिए मूलभूत डेटा संरचनाएं भी हैं जो 2007 तक सबसे तीव्र स्ट्रिंग सॉर्टिंग एल्गोरिदम होने <ref name="cachestringsort">{{cite journal | url=https://people.eng.unimelb.edu.au/jzobel/fulltext/acmjea06.pdf | doi=10.1145/1187436.1187439 | author=Ranjan Sinha and Justin Zobel and David Ring | title=प्रतिलिपि का उपयोग करके कैश-कुशल स्ट्रिंग सॉर्टिंग| journal=ACM Journal of Experimental Algorithmics | volume=11 | pages=1&ndash;32 | date=Feb 2006 | s2cid=3184411 }}</ref> एवं सीपीयू [[कैश (कंप्यूटिंग)|कैच (कंप्यूटिंग)]] के कुशल उपयोग के लिए उल्लेखनीय है।<ref name="stringradix">{{cite book | doi=10.1007/978-3-540-89097-3_3 | author=J. Kärkkäinen and T. Rantala | chapter=Engineering Radix Sort for Strings | editor=A. Amir and A. Turpin and A. Moffat | title=स्ट्रिंग प्रोसेसिंग और सूचना पुनर्प्राप्ति, प्रोक। शिखर| publisher=Springer | series=Lecture Notes in Computer Science | volume=5280 | pages=3–14 | year=2008 | isbn=978-3-540-89096-6 }}</ref>
+स्ट्रिंग कुंजियों के सेट के [[शब्दकोषीय क्रम|लेक्सिकोग्राफ़िक क्रम]] को दी गई कुंजियों के लिए ट्राई बनाकर और ट्री ट्रैवर्सल  प्री-ऑर्डर कार्यान्वयन में ट्री को पार करके कार्यान्वित किया जा सकता है;<ref>{{cite web |url=https://www.cs.helsinki.fi/u/tpkarkka/opetus/12s/spa/lecture02.pdf |title=Lecture 2 |first=Juha |last=Kärkkäinen |quote="एक ट्राइ में नोड्स का प्रीऑर्डर उन स्ट्रिंग्स के लेक्सिकोग्राफ़िकल क्रम के समान है जो वे प्रतिनिधित्व करते हैं, यह मानते हुए कि नोड के बच्चों को किनारे के लेबल द्वारा ऑर्डर किया गया है।"|publisher=[[University of Helsinki]]}}</ref> यह भी मूलांक प्रकार का एक रूप है।<ref>{{Cite web|url=https://www.ifi.uzh.ch/dam/jcr:27d15f69-2a44-40f9-8b41-6d11b5926c67/ReportKallisMScBasis.pdf|title=The Adaptive Radix Tree (Report #14-708-887)|last=Kallis|first=Rafael|date=2018|website=University of Zurich: Department of Informatics, Research Publications}}</ref> ट्राई [[बर्स्टसॉर्ट]] के लिए मूलभूत डेटा संरचनाएं भी हैं जो 2007 तक सबसे तीव्र स्ट्रिंग सॉर्टिंग एल्गोरिदम होने <ref name="cachestringsort">{{cite journal | url=https://people.eng.unimelb.edu.au/jzobel/fulltext/acmjea06.pdf | doi=10.1145/1187436.1187439 | author=Ranjan Sinha and Justin Zobel and David Ring | title=प्रतिलिपि का उपयोग करके कैश-कुशल स्ट्रिंग सॉर्टिंग| journal=ACM Journal of Experimental Algorithmics | volume=11 | pages=1&ndash;32 | date=Feb 2006 | s2cid=3184411 }}</ref> एवं सीपीयू [[कैश (कंप्यूटिंग)|कैच (कंप्यूटिंग)]] के कुशल उपयोग के लिए उल्लेखनीय है।<ref name="stringradix">{{cite book | doi=10.1007/978-3-540-89097-3_3 | author=J. Kärkkäinen and T. Rantala | chapter=Engineering Radix Sort for Strings | editor=A. Amir and A. Turpin and A. Moffat | title=स्ट्रिंग प्रोसेसिंग और सूचना पुनर्प्राप्ति, प्रोक। शिखर| publisher=Springer | series=Lecture Notes in Computer Science | volume=5280 | pages=3–14 | year=2008 | isbn=978-3-540-89096-6 }}</ref>
-=== पूर्ण-पाठ खोज ===
+=== पूर्ण-टेक्स्ट सर्च ===
-विशेष प्रकार की ट्राई जिसे [[[[प्रत्यय]] वृक्ष]] कहा जाता है का उपयोग तीव्रता से पूर्ण-पाठ खोज करने के लिए किसी पाठ में सभी प्रत्ययों को अनुक्रमित करने के लिए किया जा सकता है।<ref>{{cite journal|journal=[[SIAM Journal on Computing]]|doi=10.1137/S0097539792231982|volume=24|issue=3|url=https://epubs.siam.org/doi/abs/10.1137/S0097539792231982|title=अनुप्रयोगों के साथ वर्गाकार मैट्रिक्स में प्रत्यय वृक्ष का सामान्यीकरण|pages=520–562|issn= 0097-5397 |publisher=[[Society for Industrial and Applied Mathematics]]|date=28 May 1992|last1=Giancarlo|first1=Raffaele}}</ref>
+विशेष प्रकार की ट्राई जिसे [[[[प्रत्यय|प्रीफिक्स]] ट्री]] कहा जाता है का उपयोग तीव्रता से पूर्ण-टेक्स्ट सर्च करने के लिए किसी टेक्स्ट में सभी प्रीफिक्स को अनुक्रमित करने के लिए किया जा सकता है।<ref>{{cite journal|journal=[[SIAM Journal on Computing]]|doi=10.1137/S0097539792231982|volume=24|issue=3|url=https://epubs.siam.org/doi/abs/10.1137/S0097539792231982|title=अनुप्रयोगों के साथ वर्गाकार मैट्रिक्स में प्रत्यय वृक्ष का सामान्यीकरण|pages=520–562|issn= 0097-5397 |publisher=[[Society for Industrial and Applied Mathematics]]|date=28 May 1992|last1=Giancarlo|first1=Raffaele}}</ref>
-=== [[वेब खोज इंजन]] ===
+=== [[वेब खोज इंजन|वेब सर्च इंजन]] ===
-विशेष प्रकार की ट्राई जिसे कंप्रेस्ड ट्राई कहा जाता है का उपयोग वेब खोज इंजनों में [[ वेब अनुक्रमण ]] को संग्रहीत करने के लिए किया जाता है - जो सभी खोजने योग्य शब्दों का एक संग्रह है।<ref name="Xu12">{{cite journal|title=शब्दकोष खोज के लिए एक उन्नत गतिशील हैश TRIE एल्गोरिथ्म|first1=Lai|last1=Yang|first2=Lida|last2=Xu|first3=Zhongzhi|last3=Shi|doi=10.1080/17517575.2012.665483|date=23 March 2012|pages=419–432|volume=6|issue=4|journal=Enterprise Information Systems|bibcode=2012EntIS...6..419Y |s2cid=37884057 }}</ref> प्रत्येक टर्मिनल नोड कीवर्ड से मेल खाने वाले पेजों के लिए [[यूआरएल]] की सूची से सम्बद्ध होता है - जिसे घटना सूची कहा जाता है। ट्राई को मुख्य मेमोरी में संग्रहीत किया जाता है जबकि घटना को बाहरी स्टोरेज में रखा जाता है एवं अधिकतर बड़े [[कंप्यूटर क्लस्टर]] में या इन-मेमोरी इंडेक्स बाहरी स्थान पर संग्रहीत दस्तावेजों को इंगित करता है।<ref>{{cite journal|first1=Frederik|last1=Transier|first2=Peter|last2=Sanders|volume=29|issue=1|date=December 2010|pages=1–37|doi=10.1145/1877766.1877768|title=इन-मेमोरी टेक्स्ट सर्च इंजन की इंजीनियरिंग बुनियादी एल्गोरिदम|url=https://dl.acm.org/doi/10.1145/1877766.1877768|publisher=[[Association for Computing Machinery]]|journal=ACM Transactions on Information Systems|s2cid=932749 }}</ref>
+विशेष प्रकार की ट्राई जिसे कंप्रेस्ड ट्राई कहा जाता है का उपयोग वेब सर्च इंजनों में [[ वेब अनुक्रमण ]] को संग्रहीत करने के लिए किया जाता है - जो सभी खोजने योग्य शब्दों का एक संग्रह है।<ref name="Xu12">{{cite journal|title=शब्दकोष खोज के लिए एक उन्नत गतिशील हैश TRIE एल्गोरिथ्म|first1=Lai|last1=Yang|first2=Lida|last2=Xu|first3=Zhongzhi|last3=Shi|doi=10.1080/17517575.2012.665483|date=23 March 2012|pages=419–432|volume=6|issue=4|journal=Enterprise Information Systems|bibcode=2012EntIS...6..419Y |s2cid=37884057 }}</ref> प्रत्येक टर्मिनल नोड कीवर्ड से मेल खाने वाले पेजों के लिए [[यूआरएल]] की सूची से सम्बद्ध होता है - जिसे घटना सूची कहा जाता है। ट्राई को मुख्य मेमोरी में संग्रहीत किया जाता है जबकि घटना को बाहरी स्टोरेज में रखा जाता है एवं अधिकतर बड़े [[कंप्यूटर क्लस्टर]] में या इन-मेमोरी इंडेक्स बाहरी स्थान पर संग्रहीत दस्तावेजों को इंगित करता है।<ref>{{cite journal|first1=Frederik|last1=Transier|first2=Peter|last2=Sanders|volume=29|issue=1|date=December 2010|pages=1–37|doi=10.1145/1877766.1877768|title=इन-मेमोरी टेक्स्ट सर्च इंजन की इंजीनियरिंग बुनियादी एल्गोरिदम|url=https://dl.acm.org/doi/10.1145/1877766.1877768|publisher=[[Association for Computing Machinery]]|journal=ACM Transactions on Information Systems|s2cid=932749 }}</ref>
 === जैव सूचना विज्ञान ===
-ट्राई का उपयोग जैव सूचना विज्ञान में किया जाता है विशेष रूप से [[अनुक्रम संरेखण]] सॉफ़्टवेयर अनुप्रयोगों जैसे कि BLAST (जैव प्रौद्योगिकी)  एल्गोरिदम में जो संपीड़ित ट्राइ में उनकी घटनाओं की स्थिति को संग्रहीत करके किसी पाठ की लंबाई k (जिसे [[k-mer]]s कहा जाता है) के सभी अलग-अलग सबस्ट्रिंग अनुक्रम डेटाबेस{{r|prieto16|p=75}} को अनुक्रमित करता है।
+ट्राई का उपयोग जैव सूचना विज्ञान में किया जाता है विशेष रूप से [[अनुक्रम संरेखण]] सॉफ़्टवेयर अनुप्रयोगों जैसे कि BLAST (जैव प्रौद्योगिकी)  एल्गोरिदम में जो कंप्रेस्ड ट्राइ में उनकी घटनाओं की स्थिति को संग्रहीत करके किसी पाठ की लंबाई k (जिसे [[k-mer]]s कहा जाता है) के सभी अलग-अलग सबस्ट्रिंग अनुक्रम डेटाबेस{{r|prieto16|p=75}} को अनुक्रमित करता है।
 === इंटरनेट रूटिंग ===
 {{see also|Luleå algorithm}}
-ट्राई के संपीड़ित वेरिएंट जैसे कि [[अग्रेषण सूचना आधार]] (एफआईबी) के प्रबंधन के लिए डेटाबेस का उपयोग आईपी [[मार्ग]] में [[वाइल्डकार्ड मास्क]] आधारित संचालन को हल करने के लिए उपसर्ग-आधारित लुकअप के लिए रूटिंग और [[नेटवर्क ब्रिज]] के भीतर [[सबनेटवर्क]] को संग्रहीत करने में किया जाता है।{{r|prieto16|p=75}}
+ट्राई के कंप्रेस्ड वेरिएंट जैसे कि [[अग्रेषण सूचना आधार]] (एफआईबी) के प्रबंधन के लिए डेटाबेस का उपयोग आईपी [[मार्ग]] में [[वाइल्डकार्ड मास्क]] आधारित संचालन को हल करने के लिए प्रिफिक्स-आधारित लुकअप के लिए रूटिंग और [[नेटवर्क ब्रिज]] के भीतर [[सबनेटवर्क]] को संग्रहीत करने में किया जाता है।{{r|prieto16|p=75}}
 == यह भी देखें ==

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt Pattern Matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting

Anonymous

Search

ट्राई: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:07, 19 July 2023

Contents

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

अवलोकन

संचालन

खोजना

प्रविष्टि

विलोपन

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

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

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

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

कंप्रेस्ड ट्राइ

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

अनुप्रयोग

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

पूर्ण-टेक्स्ट सर्च

वेब सर्च इंजन

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ट्राई: Difference between revisions

Revision as of 23:07, 19 July 2023

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

अवलोकन

संचालन

खोजना

प्रविष्टि

विलोपन

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

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

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

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

कंप्रेस्ड ट्राइ

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

अनुप्रयोग

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

पूर्ण-टेक्स्ट सर्च

वेब सर्च इंजन

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories