ट्राई: 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 15:39, 16 July 2023

चित्र 1: कुंजियों के लिए एक प्रयास ए, टू, टी, टेड, टेन, आई, इन, और इन। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ एक मनमाना पूर्णांक मान सम्बद्ध होता है।

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

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

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

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

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

स्ट्रिंग्स के सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार सन 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: स्ट्रिंग सेट का प्रतिनिधित्व करने का प्रयास करें: समुद्र, बेचता है, और वह।

विभिन्न परिचालनों (स्ट्रिंग कुंजी का सम्मिलन, विलोपन और लुकअप) का समर्थन करने का प्रयास करता है। प्रयत्नों से बना है ${\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}}$ चाबियों की संख्या और चाबियों की लंबाई।^[12]^: 358

यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग शामिल हैं, तो बीएसटी की तुलना में ट्राई कम जगह घेरता है, क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।^[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{nil}}$ तदनुसार.^[14]^: 740

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

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]

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

Fig. 4: Patricia tree representation of string keys: in, integer, interval, string, and structure.

पेट्रीसिया पेड़ संपीड़ित बाइनरी ट्राइ का एक विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के बाइनरी कोड का उपयोग करता है।^[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 17: / Line 17: @@
 | type=tree
 }}
-[[Image:trie example.svg|thumb|250px|चित्र 1: कुंजियों के लिए एक प्रयास ए, टू, टी, टेड, टेन, आई, इन, और इन। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ एक मनमाना पूर्णांक मान जुड़ा होता है।|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: कुंजियों के लिए एक प्रयास ए, टू, टी, टेड, टेन, आई, इन, और इन। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ एक मनमाना पूर्णांक मान सम्बद्ध होता है।|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> जोकि एक प्रकार का के-एरी [[ खोज वृक्ष |खोज ट्री]] है। ट्री ([[डेटा संरचना]]) डेटा संरचना जिसका उपयोग  सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये कुंजियाँ अधिकतर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि व्यक्तिगत [[ चरित्र (कंप्यूटिंग) |चरित्र (कंप्यूटिंग)]] द्वारा परिभाषित होते हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनर्प्राप्त करने, उसे बदलने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए [[गहराई-पहली खोज]] को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है।
-[[बाइनरी सर्च ट्री]] के विपरीत, ट्राई में नोड्स अपनी संबंधित कुंजी को संग्रहीत नहीं करते हैं। इसके बजाय, ट्राई में एक नोड की स्थिति उस कुंजी को परिभाषित करती है जिसके साथ वह संबद्ध है। यह प्रत्येक कुंजी के मान को डेटा संरचना में वितरित करता है, और इसका मतलब है कि जरूरी नहीं कि प्रत्येक नोड का एक संबद्ध मान हो।
+[[बाइनरी सर्च ट्री]] के विपरीत ट्राई में नोड्स अपनी संबंधित कुंजी को संग्रहीत नहीं करते हैं। इसके स्थान पर ट्राई में एक नोड की स्थिति उस कुंजी को परिभाषित करती है जिसके साथ वह संबद्ध है। यह प्रत्येक कुंजी के मान को डेटा संरचना में वितरित करता है और इसका अर्थ है कि आवश्यक नहीं कि प्रत्येक नोड का एक संबद्ध मान हो।
-एक नोड के सभी बच्चों में उस मूल नोड से जुड़े स्ट्रिंग का एक सामान्य [[उपसर्ग]] होता है, और रूट [[खाली स्ट्रिंग]] से जुड़ा होता है। इसके उपसर्ग द्वारा पहुंच योग्य डेटा को संग्रहीत करने का यह कार्य [[ मूलांक वृक्ष ]] को नियोजित करके मेमोरी-अनुकूलित तरीके से पूरा किया जा सकता है।
+नोड के सभी छोटे भागों में उस मूल नोड से जुड़े स्ट्रिंग का सामान्य [[उपसर्ग]] होता है और रूट [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] से सम्बद्ध होता है। इसके उपसर्ग द्वारा पहुंच योग्य डेटा को संग्रहीत करने का यह कार्य [[ मूलांक वृक्ष |मूलांक ट्री]] को नियोजित करके मेमोरी-अनुकूलित उपाय से पूरा किया जा सकता है।
-हालाँकि कोशिशों को कैरेक्टर स्ट्रिंग्स द्वारा कुंजीबद्ध किया जा सकता है, लेकिन ऐसा होना ज़रूरी नहीं है। समान एल्गोरिदम को किसी भी अंतर्निहित प्रकार की ऑर्डर की गई सूचियों के लिए अनुकूलित किया जा सकता है, उदाहरण के लिए अंकों या आकृतियों का क्रम[[परिवर्तन]]। विशेष रूप से, एक 'बिटवाइज़ ट्राई' को अलग-अलग बिट्स पर कुंजीबद्ध किया जाता है, जो निश्चित-लंबाई वाले बाइनरी डेटा का एक टुकड़ा बनाता है, जैसे पूर्णांक या [[ स्मृति पता ]]। ट्राई की कुंजी लुकअप जटिलता कुंजी आकार के समानुपाती रहती है। अनुभवहीन कार्यान्वयन में ट्राइ की विशाल स्थान आवश्यकता से निपटने के लिए संपीड़ित कोशिशों जैसे विशिष्ट ट्राइ कार्यान्वयन का उपयोग किया जाता है।
+जबकि कोशिशों को कैरेक्टर स्ट्रिंग्स द्वारा कुंजीबद्ध किया जा सकता है लेकिन ऐसा होना आवश्यक नहीं है। समान एल्गोरिदम को किसी भी अंतर्निहित प्रकार की ऑर्डर की गई सूचियों के लिए अनुकूलित किया जा सकता है उदाहरण के लिए अंकों या आकृतियों का क्रम[[परिवर्तन]]। विशेष रूप से 'बिटवाइज़ ट्राई' को अलग-अलग बिट्स पर कुंजीबद्ध किया जाता है जो निश्चित-लंबाई वाले बाइनरी डेटा का एक टुकड़ा बनाता है जैसे पूर्णांक या [[ स्मृति पता | स्मृति पता]]। ट्राई की कुंजी लुकअप जटिलता कुंजी आकार के समानुपाती रहती है। अनुभवहीन कार्यान्वयन में ट्राइ की विशाल स्थान आवश्यकता से निपटने के लिए संपीड़ित कोशिशों जैसे विशिष्ट ट्राइ कार्यान्वयन का उपयोग किया जाता है।
 ==इतिहास, व्युत्पत्ति, और उच्चारण==
-स्ट्रिंग्स के एक सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार 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}}
+स्ट्रिंग्स के सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार सन 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 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>{{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>
 ==संचालन ==
-[[File:Trie representation.png|thumb|right|400px|चित्र 2: स्ट्रिंग सेट का प्रतिनिधित्व करने का प्रयास करें: समुद्र, बेचता है, और वह।]]विभिन्न परिचालनों का समर्थन करने का प्रयास करता है: एक स्ट्रिंग कुंजी का सम्मिलन, विलोपन और लुकअप। प्रयत्नों से बना है <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: स्ट्रिंग सेट का प्रतिनिधित्व करने का प्रयास करें: समुद्र, बेचता है, और वह।]]विभिन्न परिचालनों (स्ट्रिंग कुंजी का सम्मिलन, विलोपन और लुकअप) का समर्थन करने का प्रयास करता है। प्रयत्नों से बना है <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 89: / Line 88: @@
         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> सम्मिलन के समय, दी गई स्ट्रिंग कुंजी से सम्बद्ध मान वर्तमान कुंजी से प्रतिस्थापित हो जाता है।
 === विलोपन ===
@@ Line 114: / Line 113: @@
        '''return''' x
 |}
-प्रक्रियाएँ जाँचने से शुरू होती हैं <math>\text{key}</math>; <math>\text{nil}</math> टर्मिनल नोड या स्ट्रिंग कुंजी के अंत के आगमन को दर्शाता है। यदि टर्मिनल और यदि इसमें कोई संतान नहीं है, तो नोड को ट्राइ से हटा दिया जाता है (पंक्ति 14 वर्ण सूचकांक को निर्दिष्ट करता है) <math>\text{nil}</math>). हालाँकि, नोड के टर्मिनल के बिना स्ट्रिंग कुंजी का अंत इंगित करता है कि कुंजी मौजूद नहीं है, इस प्रकार प्रक्रिया ट्राई को संशोधित नहीं करती है। प्रत्यावर्तन वृद्धि करके आगे बढ़ता है <math>\text{key}</math>का सूचकांक.
+प्रक्रियाएँ जाँचने से शुरू होती हैं <math>\text{key}</math>; <math>\text{nil}</math> टर्मिनल नोड या स्ट्रिंग कुंजी के अंत के आगमन को दर्शाता है। यदि टर्मिनल और यदि इसमें कोई संतान नहीं है, तो नोड को ट्राइ से हटा दिया जाता है (पंक्ति 14 वर्ण सूचकांक को निर्दिष्ट करता है) <math>\text{nil}</math>). जबकि, नोड के टर्मिनल के बिना स्ट्रिंग कुंजी का अंत इंगित करता है कि कुंजी मौजूद नहीं है, इस प्रकार प्रक्रिया ट्राई को संशोधित नहीं करती है। प्रत्यावर्तन वृद्धि करके आगे बढ़ता है <math>\text{key}</math>का सूचकांक.
 == अन्य डेटा संरचनाओं को बदलना ==
@@ Line 125: / Line 124: @@
 * ट्राई के भीतर स्ट्रिंग कुंजियों को पूर्व निर्धारित वर्णमाला क्रम का उपयोग करके क्रमबद्ध किया जा सकता है।
-हालाँकि, हैश टेबल की तुलना में प्रयास कम कुशल होते हैं जब डेटा को सीधे कंप्यूटर डेटा स्टोरेज#सेकेंडरी स्टोरेज जैसे कि हार्ड डिस्क ड्राइव पर एक्सेस किया जाता है, जिसमें मुख्य मेमोरी की तुलना में अधिक [[रैंडम एक्सेस]] समय होता है।<ref name="triememory">{{cite journal | author=Edward Fredkin| author-link=Edward Fredkin| title=स्मृति का प्रयास करें| journal=Communications of the ACM| year=1960| volume=3| issue=9| pages=490–499| doi=10.1145/367390.367400 | s2cid=15384533}}</ref> जब कुंजी मान को आसानी से स्ट्रिंग के रूप में प्रस्तुत नहीं किया जा सकता है, तो कोशिशें भी नुकसानदायक होती हैं, जैसे कि फ़्लोटिंग पॉइंट संख्याएँ जहाँ एकाधिक प्रतिनिधित्व संभव हैं (उदाहरण के लिए 1, 1.0, +1.0, 1.00, आदि के बराबर है),{{r|reema18|p=359}} हालाँकि इसे दो के पूरक प्रारूप की तुलना में [[IEEE 754]] में एक [[बाइनरी संख्या]] के रूप में स्पष्ट रूप से दर्शाया जा सकता है।<ref>{{cite web|publisher=Department of Mathematics and Computer Science, [[Emory University]]|title=The IEEE 754 Format|url=http://mathcenter.oxford.emory.edu/site/cs170/ieee754/|access-date=17 April 2022|author1=S. Orley|author2=J. Mathews|url-status=live|archive-date=28 March 2022|archive-url=https://web.archive.org/web/20220328093853/http://mathcenter.oxford.emory.edu/site/cs170/ieee754/}}</ref>
+जबकि, हैश टेबल की तुलना में प्रयास कम कुशल होते हैं जब डेटा को सीधे कंप्यूटर डेटा स्टोरेज#सेकेंडरी स्टोरेज जैसे कि हार्ड डिस्क ड्राइव पर एक्सेस किया जाता है, जिसमें मुख्य मेमोरी की तुलना में अधिक [[रैंडम एक्सेस]] समय होता है।<ref name="triememory">{{cite journal | author=Edward Fredkin| author-link=Edward Fredkin| title=स्मृति का प्रयास करें| journal=Communications of the ACM| year=1960| volume=3| issue=9| pages=490–499| doi=10.1145/367390.367400 | s2cid=15384533}}</ref> जब कुंजी मान को आसानी से स्ट्रिंग के रूप में प्रस्तुत नहीं किया जा सकता है, तो कोशिशें भी नुकसानदायक होती हैं, जैसे कि फ़्लोटिंग पॉइंट संख्याएँ जहाँ एकाधिक प्रतिनिधित्व संभव हैं (उदाहरण के लिए 1, 1.0, +1.0, 1.00, आदि के बराबर है),{{r|reema18|p=359}} जबकि इसे दो के पूरक प्रारूप की तुलना में [[IEEE 754]] में एक [[बाइनरी संख्या]] के रूप में स्पष्ट रूप से दर्शाया जा सकता है।<ref>{{cite web|publisher=Department of Mathematics and Computer Science, [[Emory University]]|title=The IEEE 754 Format|url=http://mathcenter.oxford.emory.edu/site/cs170/ieee754/|access-date=17 April 2022|author1=S. Orley|author2=J. Mathews|url-status=live|archive-date=28 March 2022|archive-url=https://web.archive.org/web/20220328093853/http://mathcenter.oxford.emory.edu/site/cs170/ieee754/}}</ref>
 ==कार्यान्वयन रणनीतियाँ==
-[[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>
+वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को एक छोटे वर्णमाला पर एक लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। {{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 156: / Line 155: @@
 | width = 400
 }}
-पेट्रीसिया पेड़ संपीड़ित बाइनरी ट्राइ का एक विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के [[बाइनरी कोड]] का उपयोग करता है।<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}}
 == अनुप्रयोग ==
-त्रि डेटा संरचनाओं का उपयोग आमतौर पर पूर्वानुमानित पाठ या स्वत: पूर्ण शब्दकोशों और अनुमानित स्ट्रिंग मिलान में किया जाता है।<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}}
 === छँटाई ===
@@ Line 172: / Line 171: @@
 === [[वेब खोज इंजन]] ===
-एक विशेष प्रकार की ट्राई, जिसे कंप्रेस्ड ट्राई कहा जाता है, का उपयोग वेब खोज इंजनों में [[ वेब अनुक्रमण ]] को संग्रहीत करने के लिए किया जाता है - जो सभी खोजने योग्य शब्दों का एक संग्रह है।<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>

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 15:39, 16 July 2023

Contents

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

अवलोकन

संचालन

खोज रहा हूँ

निवेशन

विलोपन

अन्य डेटा संरचनाओं को बदलना

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

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

बिटवाइज़ प्रयास करता है

संपीड़ित प्रयास

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

अनुप्रयोग

छँटाई

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

वेब खोज इंजन

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ट्राई: Difference between revisions

Revision as of 15:39, 16 July 2023

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

अवलोकन

संचालन

खोज रहा हूँ

निवेशन

विलोपन

अन्य डेटा संरचनाओं को बदलना

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

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

बिटवाइज़ प्रयास करता है

संपीड़ित प्रयास

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

अनुप्रयोग

छँटाई

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

वेब खोज इंजन

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories