ट्राई

This article is about ट्री डेटा संरचना. For the French commune, see Trie-sur-Baïse.

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

File:Trie example.svg

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

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

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

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

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

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

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

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

अवलोकन

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

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

संचालन

Error creating thumbnail:

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

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

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

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

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

खोजना

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

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

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

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

प्रविष्टि

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

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

विलोपन

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

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

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

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

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

• $m$