ट्राई: 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:05, 18 July 2023

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

कंप्यूटर विज्ञान में ट्राई जिसे डिजिटल ट्री या उपसर्ग ट्री भी कहा जाता है^[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: ट्राई स्ट्रिंग सेट का प्रतिनिधित्व: 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}}$ चाबियों की संख्या और चाबियों की लंबाई।^[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{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 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: कुंजियों के लिए ट्राई 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> जोकि एक प्रकार का के-एरी [[ खोज वृक्ष |खोज ट्री]] है। ट्री ([[डेटा संरचना]]) डेटा संरचना जिसका उपयोग  सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये कुंजियाँ अधिकतर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि व्यक्तिगत [[ चरित्र (कंप्यूटिंग) |चरित्र (कंप्यूटिंग)]] द्वारा परिभाषित होते हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनर्प्राप्त करने, उसे परिवर्तित करने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए [[गहराई-पहली खोज]] को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है।
 [[बाइनरी सर्च ट्री]] के विपरीत ट्राई में नोड्स अपनी संबंधित कुंजी को संग्रहीत नहीं करते हैं। इसके स्थान पर ट्राई में एक नोड की स्थिति उस कुंजी को परिभाषित करती है जिसके साथ वह संबद्ध है। यह प्रत्येक कुंजी के मान को डेटा संरचना में वितरित करता है और इसका अर्थ है कि आवश्यक नहीं कि प्रत्येक नोड का एक संबद्ध मान हो।
@@ Line 28: / Line 28: @@
 स्ट्रिंग्स के सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार सन 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>
 == अवलोकन ==
@@ Line 37: / Line 37: @@
 ==संचालन ==
-[[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: ट्राई स्ट्रिंग सेट का प्रतिनिधित्व: 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}}
 # वर्ण और स्ट्रिंग कुंजियाँ अंतर्निहित रूप से ट्राई डेटा संरचना प्रतिनिधित्व में संग्रहीत होती हैं और इसमें स्ट्रिंग-समाप्ति को इंगित करने वाला वर्ण प्रहरी मान सम्मिलित होता है।
 # प्रत्येक नोड में सेट की मजबूत कुंजियों के उपसर्ग का संभावित लिंक होता है।
@@ Line 69: / Line 69: @@
       '''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> चाबियों की संख्या और चाबियों की लंबाई।{{r|reema18|p=358}}
-यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं, तो बीएसटी की तुलना में ट्राई कम जगह घेरता है, क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।{{r|reema18|p=358}} पेड़ के टर्मिनल नोड में एक गैर-शून्य होता है <math>\text{Value}</math>, और यदि संबंधित मान ट्राई में पाया जाता है तो यह एक खोज हिट है, और यदि ऐसा नहीं है तो खोज मिस हो जाती है।{{r|robert11|p=733}}
+यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं तो बीएसटी की तुलना में ट्राई कम स्थान घेरता है क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।{{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 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> नहीं था एवं दी गई स्ट्रिंग कुंजी से सम्बद्ध मान वर्तमान कुंजी से प्रतिस्थापित हो जाता है।
 === विलोपन ===
 ट्राई से कुंजी-मूल्य जोड़ी को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत पर चिह्नित करना सम्मिलित है। <math>\text{nil}</math> तदनुसार.{{r|robert11|p=740}}
-स्ट्रिंग कुंजी को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है (<math>\text{key}</math>) जड़ित त्रि से (<math>\text{x}</math>).
+जड़ित ट्राई (<math>\text{x}</math>) से स्ट्रिंग कुंजी (<math>\text{key}</math>) को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है,
 {|
 |- style="vertical-align:top"
@@ Line 113: / 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> का सूचकांक आगे बढ़ता है।
-== अन्य डेटा संरचनाओं को बदलना ==
+== अन्य डेटा संरचनाओं को परिवर्तित करना ==
 === [[हैश तालिका]]ओं के लिए प्रतिस्थापन ===
-ट्राई का उपयोग हैश टेबल को बदलने के लिए किया जा सकता है, जिसके निम्नलिखित फायदे हैं:{{r|reema18|p=358}}
+ट्राई का उपयोग हैश टेबल को परिवर्तित करने के लिए किया जा सकता है जिसके निम्नलिखित लाभ हैं:{{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> तालिका के भीतर नोड्स की कुल संख्या को दर्शाता है।
-* हैश टेबल के विपरीत, ट्राइज़ को ऑपरेशन के लिए हैश फ़ंक्शन की आवश्यकता नहीं होती है; एक प्रयास में विभिन्न कुंजियों की कोई [[हैश टक्कर]] भी नहीं होती है।
+* हैश टेबल के विपरीत ट्राइज़ को ऑपरेशन के लिए हैश फ़ंक्शन की आवश्यकता नहीं होती है; ट्राई में विभिन्न कुंजियों की कोई [[हैश टक्कर]] भी नहीं होती है।
-* ट्राई में बकेट, जो हैश टेबल बकेट के समान होते हैं जो कुंजी टकराव को संग्रहीत करते हैं, केवल तभी आवश्यक होते हैं जब एक कुंजी एक से अधिक मान से जुड़ी होती है।
+* ट्राई में बकेट जो हैश टेबल बकेट के समान होते हैं जो कुंजी टकराव को संग्रहीत करते हैं एवं केवल तभी आवश्यक होते हैं जब कुंजी एक से अधिक मान से जुड़ी होती है।
 * ट्राई के भीतर स्ट्रिंग कुंजियों को पूर्व निर्धारित वर्णमाला क्रम का उपयोग करके क्रमबद्ध किया जा सकता है।
-जबकि, हैश टेबल की तुलना में प्रयास कम कुशल होते हैं जब डेटा को सीधे कंप्यूटर डेटा स्टोरेज#सेकेंडरी स्टोरेज जैसे कि हार्ड डिस्क ड्राइव पर एक्सेस किया जाता है, जिसमें मुख्य मेमोरी की तुलना में अधिक [[रैंडम एक्सेस]] समय होता है।<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}}
+वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को छोटे वर्णमाला पर लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। {{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>
-==कार्यान्वयन रणनीतियाँ==
+=== बिटवाइज़ ट्राई ===
-[[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}}
+{{see also| x-तीव्र ट्राई|बिटमैप के साथ बिटवाइज़ ट्राई}}
-वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को एक छोटे वर्णमाला पर एक लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। {{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>
+सरल पॉइंटर वेक्टर कार्यान्वयन में ट्राइ नोड्स के लिए विशाल स्थान की आवश्यकता को संबोधित करने के लिए बिटवाइज़ ट्राईों का उपयोग किया जाता है। स्ट्रिंग कुंजी सेट में प्रत्येक वर्ण को अलग-अलग बिट्स के माध्यम से दर्शाया जाता है जिसका उपयोग स्ट्रिंग कुंजी पर ट्राई को पार करने के लिए किया जाता है। इस प्रकार के ट्राई के कार्यान्वयन निश्चित-लंबाई कुंजी इनपुट में पहला सेट खोजने के लिए [[SIMD]] CPU निर्देशों का उपयोग करते हैं (उदाहरण के लिए [[जीएनयू कंपाइलर संग्रह]]) <code>__builtin_clz()</code> [[आंतरिक कार्य]])। तदनुसार, सेट बिट का उपयोग 32- या 64-प्रविष्टि आधारित बिटवाइज़ ट्री में पहले आइटम या चाइल्ड नोड को अनुक्रमित करने के लिए किया जाता है। इसके पश्चात कुंजी में प्रत्येक आगामी बिट का परीक्षण करके खोज आगे बढ़ती है।<ref name="willar83">{{cite journal|title=अंतरिक्ष O(n) में लॉग-लघुगणकीय सबसे खराब स्थिति वाले श्रेणी प्रश्न संभव हैं|publisher=[[ScienceDirect]]|doi=10.1016/0020-0190(83)90075-3|url=https://www.sciencedirect.com/science/article/abs/pii/0020019083900753|volume=17|issue=2|date=27 January 1983|pages=81–84|first=Dan E.|last=Willar|journal=Information Processing Letters}}</ref>
+यह प्रक्रिया [[सीपीयू रजिस्टर]] स्वतंत्रता के कारण  कैच-स्थानीय और [[समानांतर प्रोग्रामिंग मॉडल]] भी है और इस प्रकार क्रम से बाहर निष्पादन सीपीयू पर प्रदर्शन करती है।<ref name="willar83" />
-=== बिटवाइज़ प्रयास करता है ===
-{{see also| x-fast trie| Bitwise trie with bitmap}}
-सरल सरल पॉइंटर वेक्टर कार्यान्वयन में ट्राइ नोड्स के लिए विशाल स्थान की आवश्यकता को संबोधित करने के लिए बिटवाइज़ प्रयासों का उपयोग किया जाता है। स्ट्रिंग कुंजी सेट में प्रत्येक वर्ण को अलग-अलग बिट्स के माध्यम से दर्शाया जाता है, जिसका उपयोग स्ट्रिंग कुंजी पर ट्राई को पार करने के लिए किया जाता है। इस प्रकार के ट्राई के कार्यान्वयन एक निश्चित-लंबाई कुंजी इनपुट में पहला सेट खोजने के लिए [[SIMD]] CPU निर्देशों का उपयोग करते हैं (उदाहरण के लिए [[जीएनयू कंपाइलर संग्रह]]) <code>__builtin_clz()</code> [[आंतरिक कार्य]])। तदनुसार, सेट बिट का उपयोग 32- या 64-प्रविष्टि आधारित बिटवाइज़ ट्री में पहले आइटम, या चाइल्ड नोड को अनुक्रमित करने के लिए किया जाता है। फिर कुंजी में प्रत्येक आगामी बिट का परीक्षण करके खोज आगे बढ़ती है।<ref name="willar83">{{cite journal|title=अंतरिक्ष O(n) में लॉग-लघुगणकीय सबसे खराब स्थिति वाले श्रेणी प्रश्न संभव हैं|publisher=[[ScienceDirect]]|doi=10.1016/0020-0190(83)90075-3|url=https://www.sciencedirect.com/science/article/abs/pii/0020019083900753|volume=17|issue=2|date=27 January 1983|pages=81–84|first=Dan E.|last=Willar|journal=Information Processing Letters}}</ref>
-यह प्रक्रिया [[सीपीयू रजिस्टर]] स्वतंत्रता के कारण संदर्भ की स्थानीयता | कैश-स्थानीय और [[समानांतर प्रोग्रामिंग मॉडल]] भी है, और इस प्रकार आउट-ऑफ-ऑर्डर निष्पादन सीपीयू पर प्रदर्शन करती है।<ref name="willar83" />
-===संपीड़ित प्रयास ===
+===संपीड़ित ट्राइ ===
 {{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>
+एक और दृष्टिकोण ट्राइ को पैक करना है जिसमें स्वचालित [[हाइफ़नेशन एल्गोरिथ्म]] पर लागू एक विरल पैक ट्राइ का स्थान-कुशल कार्यान्वयन होता है जिसमें प्रत्येक नोड के वंशजों को मेमोरी में इंटरलीव किया जा सकता है।<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>
+==== पेट्रीसिया ट्री ====
-==== पेट्रीसिया पेड़ ====
 {{multiple image
 | direction = vertical
 | image1 = Patricia tree.png
 | image2 = Patricia tree ASCII to binary.png
-| footer = Fig. 4: Patricia tree representation of string keys: in, integer, interval, string, and structure.
+| footer = चित्र. 4: पेट्रीसिया ट्री स्ट्रिंग कुंजियों का प्रतिनिधित्व: इन, पूर्णांक, अंतराल, स्ट्रिंग और संरचना।
 | 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}}
-स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व <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>{{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}}
-=== छँटाई ===
-स्ट्रिंग कुंजियों के एक सेट के [[शब्दकोषीय क्रम]] को दी गई कुंजियों के लिए एक ट्राई बनाकर और ट्री ट्रैवर्सल#प्री-ऑर्डर कार्यान्वयन|प्री-ऑर्डर फैशन में ट्री को पार करके कार्यान्वित किया जा सकता है;<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:05, 18 July 2023

Contents

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

अवलोकन

संचालन

खोजना

प्रविष्टि

विलोपन

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

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

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

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

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

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

अनुप्रयोग

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

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

वेब खोज इंजन

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ट्राई: Difference between revisions

Revision as of 23:05, 18 July 2023

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

अवलोकन

संचालन

खोजना

प्रविष्टि

विलोपन

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

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

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

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

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

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

अनुप्रयोग

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

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

वेब खोज इंजन

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories