ट्राई: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{about|a tree data structure|the French commune|Trie-sur-Baïse}}
{{about|ट्री डेटा संरचना|the French commune|Trie-sur-Baïse}}


{{Infobox data structure
{{Infobox data structure
Line 22: Line 22:
नोड के सभी छोटे भागों में उस मूल नोड से जुड़े स्ट्रिंग का सामान्य [[उपसर्ग|प्रिफिक्स]] होता है और रूट [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] से सम्बद्ध होता है। इसके प्रिफिक्स द्वारा पहुंच योग्य डेटा को संग्रहीत करने का यह कार्य [[ मूलांक वृक्ष |रेडिक्स ट्री]] को नियोजित करके मेमोरी-अनुकूलित उपाय से पूरा किया जा सकता है।
नोड के सभी छोटे भागों में उस मूल नोड से जुड़े स्ट्रिंग का सामान्य [[उपसर्ग|प्रिफिक्स]] होता है और रूट [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] से सम्बद्ध होता है। इसके प्रिफिक्स द्वारा पहुंच योग्य डेटा को संग्रहीत करने का यह कार्य [[ मूलांक वृक्ष |रेडिक्स ट्री]] को नियोजित करके मेमोरी-अनुकूलित उपाय से पूरा किया जा सकता है।


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


==इतिहास, व्युत्पत्ति, और उच्चारण==
==इतिहास, व्युत्पत्ति, और उच्चारण==
Line 40: Line 40:
# प्रत्येक नोड में सेट की मजबूत कुंजियों के प्रिफिक्स का संभावित लिंक होता है।
# प्रत्येक नोड में सेट की मजबूत कुंजियों के प्रिफिक्स का संभावित लिंक होता है।


ट्राई में नोड्स का बुनियादी [[समग्र डेटा प्रकार]] इस प्रकार है; <math>\text{Node}</math> वैकल्पिक रूप से सम्मिलित हो सकता है तथा <math>\text{Value}</math> जो स्ट्रिंग या टर्मिनल नोड के अंतिम अक्षर में संग्रहीत प्रत्येक कुंजी से सम्बद्ध हुआ है।
ट्राई में नोड्स का बुनियादी [[समग्र डेटा प्रकार]] इस प्रकार है; <math>\text{Node}</math> वैकल्पिक रूप से सम्मिलित हो सकता है तथा <math>\text{Value}</math> जो स्ट्रिंग या टर्मिनल नोड के अंतिम अक्षर में संग्रहीत प्रत्येक कुंजी से सम्बद्ध होता है।
{|
{|
|- style="vertical-align:top"
|- style="vertical-align:top"
Line 68: Line 68:
     '''return''' x.Value
     '''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>, <math>\text{key}</math> की संख्या और <math>\text{key}</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>, <math>\text{key}</math> की संख्या और <math>\text{key}</math> की लंबाई है।{{r|reema18|p=358}}


यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं तो BST की तुलना में ट्राई कम स्थान घेरता है क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।{{r|reema18|p=358}} ट्री के टर्मिनल नोड में <math>\text{Value}</math> गैर-शून्य होता है और यदि संबंधित मान ट्राई में पाया जाता है तो यह सर्च हिट है और यदि ऐसा नहीं है तो सर्च मिस हो जाती है।{{r|robert11|p=733}}
यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं तो BST की तुलना में ट्राई कम स्थान घेरता है क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।{{r|reema18|p=358}} ट्री के टर्मिनल नोड में <math>\text{Value}</math> गैर-शून्य होता है और यदि संबंधित मान ट्राई में पाया जाता है तो यह सर्च हिट है और यदि ऐसा नहीं है तो सर्च मिस हो जाता है।{{r|robert11|p=733}}


=== प्रविष्टि ===
=== प्रविष्टि ===
Line 90: Line 90:


=== विलोपन ===
=== विलोपन ===
ट्राई से <math>\text{key}</math>-वैल्यू पेअर को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत पर चिह्नित करना सम्मिलित है। <math>\text{nil}</math> तदनुसार.{{r|robert11|p=740}}
ट्राई से <math>\text{key}</math>-वैल्यू पेअर को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत एवं <math>\text{nil}</math> पर चिह्नित करना सम्मिलित है।{{r|robert11|p=740}}


रूटेड ट्राई (<math>\text{x}</math>) से स्ट्रिंग कुंजी (<math>\text{key}</math>) को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है,
रूटेड ट्राई (<math>\text{x}</math>) से स्ट्रिंग कुंजी (<math>\text{key}</math>) को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है,
Line 112: Line 112:
  15      '''return''' x
  15      '''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>


==कार्यान्वयन रणनीतियाँ==
==कार्यान्वयन रणनीतियाँ==
Line 158: Line 158:
पेट्रीसिया ट्री कंप्रेस्ड बाइनरी ट्राइ का विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के [[बाइनरी कोड]] का उपयोग करता है।<ref>{{cite web|url=https://xlinux.nist.gov/dads/HTML/patriciatree.html|publisher=[[National Institute of Standards and Technology]]|archive-date=14 February 2022|archive-url=https://web.archive.org/web/20220214182428/https://xlinux.nist.gov/dads/HTML/patriciatree.html|url-status=live|access-date=17 April 2022|title=Patricia tree}}</ref><ref name="gonnet91">{{cite book|title=Handbook of algorithms and data structures: in Pascal and C|edition=2|date=January 1991|isbn=978-0-201-41607-7|publisher=[[Addison-Wesley]]|location=[[Boston]], [[United States]]|first1=G. H.|last1=Gonnet|first2=R. Baeza|last2=Yates|url=https://dl.acm.org/doi/book/10.5555/103324}}</ref>{{rp|p=140}} पेट्रीसिया ट्री के प्रत्येक नोड में निर्देशिका होती है जिसे स्किप नंबर के रूप में जाना जाता है जो ट्रैवर्सल के समय रिक्त सब ट्री से बचने के लिए नोड के ब्रांचिंग इंडेक्स को संग्रहीत करता है।{{r|gonnet91|p=140-141}} कुंजियों के विरल वितरण के कारण बड़ी संख्या में लीफ-नोड्स के कारण ट्राई के सरल कार्यान्वयन में अत्यधिक भंडारण की खपत होती है; ऐसे स्थितियों के लिए पेट्रीसिया के ट्री कारगर हो सकते हैं।{{r|gonnet91|p=142}}{{r|maxime09|p=3}}
पेट्रीसिया ट्री कंप्रेस्ड बाइनरी ट्राइ का विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के [[बाइनरी कोड]] का उपयोग करता है।<ref>{{cite web|url=https://xlinux.nist.gov/dads/HTML/patriciatree.html|publisher=[[National Institute of Standards and Technology]]|archive-date=14 February 2022|archive-url=https://web.archive.org/web/20220214182428/https://xlinux.nist.gov/dads/HTML/patriciatree.html|url-status=live|access-date=17 April 2022|title=Patricia tree}}</ref><ref name="gonnet91">{{cite book|title=Handbook of algorithms and data structures: in Pascal and C|edition=2|date=January 1991|isbn=978-0-201-41607-7|publisher=[[Addison-Wesley]]|location=[[Boston]], [[United States]]|first1=G. H.|last1=Gonnet|first2=R. Baeza|last2=Yates|url=https://dl.acm.org/doi/book/10.5555/103324}}</ref>{{rp|p=140}} पेट्रीसिया ट्री के प्रत्येक नोड में निर्देशिका होती है जिसे स्किप नंबर के रूप में जाना जाता है जो ट्रैवर्सल के समय रिक्त सब ट्री से बचने के लिए नोड के ब्रांचिंग इंडेक्स को संग्रहीत करता है।{{r|gonnet91|p=140-141}} कुंजियों के विरल वितरण के कारण बड़ी संख्या में लीफ-नोड्स के कारण ट्राई के सरल कार्यान्वयन में अत्यधिक भंडारण की खपत होती है; ऐसे स्थितियों के लिए पेट्रीसिया के ट्री कारगर हो सकते हैं।{{r|gonnet91|p=142}}{{r|maxime09|p=3}}


स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व <math>\{in, integer, interval, string, structure\}</math> चित्र 4 में दिखाया गया है और नोड्स से सटे प्रत्येक सूचकांक मान स्किप संख्या का प्रतिनिधित्व करता है - बिट का सूचकांक जिसके साथ शाखा तय की जानी है।<ref name="maxime09">{{cite book|title=डेटाबेस सिस्टम का विश्वकोश|first1=Maxime|last1=Crochemore|first2=Thierry|last2=Lecroq|url=https://link.springer.com/referencework/10.1007/978-0-387-39940-9|doi=10.1007/978-0-387-39940-9|isbn=978-0-387-49616-0|publisher=[[Springer Publishing]]|location=[[Boston]], [[United States]]|year=2009|chapter=Trie|bibcode=2009eds..book.....L |via=[[HAL (open archive)]]}}</ref>{{rp|p=3}} नोड 0 पर स्किप नंबर 1 बाइनरी एन्कोडेड ASCII में स्थिति 1 से मेल खाता है जहां कुंजी सेट <math>X</math> में सबसे बाईं ओर का बिट भिन्न था।{{r|maxime09|p=3-4}} पेट्रीसिया ट्री में नोड्स की खोज, इंसर्शन और डिलीशन के लिए स्किप नंबर महत्वपूर्ण है और प्रत्येक पुनरावृत्ति के समय थोड़ा मास्किंग ऑपरेशन किया जाता है।{{r|gonnet91|p=143}}
स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व <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}}


== अनुप्रयोग ==
== अनुप्रयोग ==
Line 171: Line 171:
विशेष प्रकार की ट्राई जिसे कंप्रेस्ड ट्राई कहा जाता है का उपयोग वेब सर्च इंजनों में [[ वेब अनुक्रमण ]] को संग्रहीत करने के लिए किया जाता है - जो सभी खोजने योग्य शब्दों का एक संग्रह है।<ref name="Xu12">{{cite journal|title=शब्दकोष खोज के लिए एक उन्नत गतिशील हैश TRIE एल्गोरिथ्म|first1=Lai|last1=Yang|first2=Lida|last2=Xu|first3=Zhongzhi|last3=Shi|doi=10.1080/17517575.2012.665483|date=23 March 2012|pages=419–432|volume=6|issue=4|journal=Enterprise Information Systems|bibcode=2012EntIS...6..419Y |s2cid=37884057 }}</ref> प्रत्येक टर्मिनल नोड कीवर्ड से मेल खाने वाले पेजों के लिए [[यूआरएल]] की सूची से सम्बद्ध होता है - जिसे घटना सूची कहा जाता है। ट्राई को मुख्य मेमोरी में संग्रहीत किया जाता है जबकि घटना को बाहरी स्टोरेज में रखा जाता है एवं अधिकतर बड़े [[कंप्यूटर क्लस्टर]] में या इन-मेमोरी इंडेक्स बाहरी स्थान पर संग्रहीत दस्तावेजों को इंगित करता है।<ref>{{cite journal|first1=Frederik|last1=Transier|first2=Peter|last2=Sanders|volume=29|issue=1|date=December 2010|pages=1–37|doi=10.1145/1877766.1877768|title=इन-मेमोरी टेक्स्ट सर्च इंजन की इंजीनियरिंग बुनियादी एल्गोरिदम|url=https://dl.acm.org/doi/10.1145/1877766.1877768|publisher=[[Association for Computing Machinery]]|journal=ACM Transactions on Information Systems|s2cid=932749 }}</ref>
विशेष प्रकार की ट्राई जिसे कंप्रेस्ड ट्राई कहा जाता है का उपयोग वेब सर्च इंजनों में [[ वेब अनुक्रमण ]] को संग्रहीत करने के लिए किया जाता है - जो सभी खोजने योग्य शब्दों का एक संग्रह है।<ref name="Xu12">{{cite journal|title=शब्दकोष खोज के लिए एक उन्नत गतिशील हैश TRIE एल्गोरिथ्म|first1=Lai|last1=Yang|first2=Lida|last2=Xu|first3=Zhongzhi|last3=Shi|doi=10.1080/17517575.2012.665483|date=23 March 2012|pages=419–432|volume=6|issue=4|journal=Enterprise Information Systems|bibcode=2012EntIS...6..419Y |s2cid=37884057 }}</ref> प्रत्येक टर्मिनल नोड कीवर्ड से मेल खाने वाले पेजों के लिए [[यूआरएल]] की सूची से सम्बद्ध होता है - जिसे घटना सूची कहा जाता है। ट्राई को मुख्य मेमोरी में संग्रहीत किया जाता है जबकि घटना को बाहरी स्टोरेज में रखा जाता है एवं अधिकतर बड़े [[कंप्यूटर क्लस्टर]] में या इन-मेमोरी इंडेक्स बाहरी स्थान पर संग्रहीत दस्तावेजों को इंगित करता है।<ref>{{cite journal|first1=Frederik|last1=Transier|first2=Peter|last2=Sanders|volume=29|issue=1|date=December 2010|pages=1–37|doi=10.1145/1877766.1877768|title=इन-मेमोरी टेक्स्ट सर्च इंजन की इंजीनियरिंग बुनियादी एल्गोरिदम|url=https://dl.acm.org/doi/10.1145/1877766.1877768|publisher=[[Association for Computing Machinery]]|journal=ACM Transactions on Information Systems|s2cid=932749 }}</ref>
=== जैव सूचना विज्ञान ===
=== जैव सूचना विज्ञान ===
ट्राई का उपयोग जैव सूचना विज्ञान में किया जाता है विशेष रूप से [[अनुक्रम संरेखण]] सॉफ़्टवेयर अनुप्रयोगों जैसे कि BLAST (जैव प्रौद्योगिकी)  एल्गोरिदम में जो कंप्रेस्ड ट्राइ में उनकी घटनाओं की स्थिति को संग्रहीत करके किसी पाठ की लंबाई k (जिसे [[k-mer]]s कहा जाता है) के सभी अलग-अलग सबस्ट्रिंग अनुक्रम डेटाबेस{{r|prieto16|p=75}} को अनुक्रमित करता है।
ट्राई का उपयोग जैव सूचना विज्ञान में किया जाता है विशेष रूप से [[अनुक्रम संरेखण]] सॉफ़्टवेयर अनुप्रयोगों जैसे कि BLAST (जैव प्रौद्योगिकी)  एल्गोरिदम में जो कंप्रेस्ड ट्राइ में उनकी घटनाओं की स्थिति को संग्रहीत करके किसी पाठ की लंबाई k (जिसे [[k-mer|k-मर्स]] कहा जाता है) के सभी अलग-अलग सबस्ट्रिंग अनुक्रम डेटाबेस{{r|prieto16|p=75}} को अनुक्रमित करता है।


=== इंटरनेट रूटिंग ===
=== इंटरनेट रूटिंग ===
{{see also|लुलिया एल्गोरिथ्म}}
{{see also|लुलिया एल्गोरिथ्म}}
ट्राई के कंप्रेस्ड वेरिएंट जैसे कि [[अग्रेषण सूचना आधार]] (एफआईबी) के प्रबंधन के लिए डेटाबेस का उपयोग आईपी [[मार्ग]] में [[वाइल्डकार्ड मास्क]] आधारित संचालन को हल करने के लिए प्रिफिक्स-आधारित लुकअप के लिए रूटिंग और [[नेटवर्क ब्रिज]] के भीतर [[सबनेटवर्क]] को संग्रहीत करने में किया जाता है।{{r|prieto16|p=75}}
ट्राई के कंप्रेस्ड वेरिएंट जैसे कि [[अग्रेषण सूचना आधार]] (FIB) के प्रबंधन के लिए डेटाबेस का उपयोग आईपी [[मार्ग|रूटिंग]] में [[वाइल्डकार्ड मास्क]] आधारित संचालन को हल करने के लिए प्रिफिक्स-आधारित लुकअप के लिए रूटिंग और [[नेटवर्क ब्रिज]] के भीतर [[सबनेटवर्क]] को संग्रहीत करने में किया जाता है।{{r|prieto16|p=75}}


== यह भी देखें ==
== यह भी देखें ==
{{div col|colwidth=22em}}
{{div col|colwidth=22em}}
* प्रत्यय वृक्ष
* सफ़िक्स ट्री
* [[हैश ट्राई]]
* [[हैश ट्राई]]
* हैश ऐरे मैप किया गया ट्राई
* हैश ऐरे मैप किया गया ट्राई
* उपसर्ग हैश [[Ctrie]]
* प्रीफिक्स हैश [[Ctrie]]
*सीट्री
*सीट्री
* [[HAT-trie]]
* [[HAT-ट्राई]]
{{div col end}}
{{div col end}}


Revision as of 23:09, 24 July 2023

This article is about ट्री डेटा संरचना. For the French commune, see Trie-sur-Baïse.
Trie
Typetree
Invented1960
Invented byEdward 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। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ मनमाना पूर्णांक मान सम्बद्ध होता है।

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

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

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

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

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

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

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

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