ट्राई

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)

File:Trie example.svg

चित्र 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]

संचालन

File:Trie representation.png

चित्र 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]

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

File:Pointer implementation of a trie.svg

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Anonymous

Search