ट्राई

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)

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

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

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

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

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

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

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

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

अवलोकन

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

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

संचालन

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

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

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

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

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

खोजना

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

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

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

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

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

प्रविष्टि

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

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

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

विलोपन

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

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

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

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Anonymous

Search