ट्राई: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{about| | {{about|ट्री डेटा संरचना|the French commune|Trie-sur-Baïse}} | ||
{{Infobox data structure | {{Infobox data structure | ||
| Line 16: | Line 16: | ||
| type=tree | | type=tree | ||
}} | }} | ||
[[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> जो एक प्रकार का ''k-ary'' [[ खोज वृक्ष |सर्च ट्री]] है। ट्री ([[डेटा संरचना]]) डेटा संरचना का उपयोग सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये '''कुंजियाँ (<math>\text{key}</math>)''' अधिकतर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि विशिष्ट [[ चरित्र (कंप्यूटिंग) |अक्षरों (कंप्यूटिंग)]] द्वारा परिभाषित | [[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> जो एक प्रकार का ''k-ary'' [[ खोज वृक्ष |सर्च ट्री]] है। ट्री ([[डेटा संरचना]]) डेटा संरचना का उपयोग सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये '''कुंजियाँ (<math>\text{key}</math>)''' अधिकतर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि विशिष्ट [[ चरित्र (कंप्यूटिंग) |अक्षरों (कंप्यूटिंग)]] द्वारा परिभाषित होती हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनः प्राप्त करने, उसे परिवर्तित करने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए [[गहराई-पहली खोज|डेप्थ-फर्स्ट सर्च]] को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है। | ||
[[बाइनरी सर्च ट्री]] के विपरीत ट्राई में नोड्स अपनी संबंधित कुंजी को संग्रहीत नहीं करते हैं। इसके स्थान पर ट्राई में एक नोड की स्थिति उस कुंजी को परिभाषित करती है जिसके साथ वह संबद्ध है। यह प्रत्येक कुंजी के मान को डेटा संरचना में वितरित करता है और इसका अर्थ है कि आवश्यक नहीं कि प्रत्येक नोड का एक संबद्ध मान हो। | [[बाइनरी सर्च ट्री]] के विपरीत ट्राई में नोड्स अपनी संबंधित कुंजी को संग्रहीत नहीं करते हैं। इसके स्थान पर ट्राई में एक नोड की स्थिति उस कुंजी को परिभाषित करती है जिसके साथ वह संबद्ध है। यह प्रत्येक कुंजी के मान को डेटा संरचना में वितरित करता है और इसका अर्थ है कि आवश्यक नहीं कि प्रत्येक नोड का एक संबद्ध मान हो। | ||
| 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>\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> गैर-शून्य होता है और यदि संबंधित मान ट्राई में पाया जाता है तो यह सर्च हिट है और यदि ऐसा नहीं है तो सर्च मिस हो | यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं तो BST की तुलना में ट्राई कम स्थान घेरता है क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।{{r|reema18|p=358}} ट्री के टर्मिनल नोड में <math>\text{Value}</math> गैर-शून्य होता है और यदि संबंधित मान ट्राई में पाया जाता है तो यह सर्च हिट है और यदि ऐसा नहीं है तो सर्च मिस हो जाता है।{{r|robert11|p=733}} | ||
=== प्रविष्टि === | === प्रविष्टि === | ||
| Line 90: | Line 90: | ||
=== विलोपन === | === विलोपन === | ||
ट्राई से <math>\text{key}</math>-वैल्यू पेअर को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत | ट्राई से <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> टर्मिनल नोड या स्ट्रिंग कुंजी के अंत के आगमन को दर्शाता है। यदि टर्मिनल और | <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>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> जब कुंजी मान को सरलता से स्ट्रिंग के रूप में प्रस्तुत नहीं किया जा सकता है तो | जबकि हैश तालिका की तुलना में ट्राई कम कुशल होते हैं जब डेटा को सीधे कंप्यूटर डेटा स्टोरेज जैसे कि हार्ड डिस्क ड्राइव पर एक्सेस किया जाता है जिसमें मुख्य मेमोरी की तुलना में अधिक [[रैंडम एक्सेस]] समय होता है।<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 134: | Line 134: | ||
{{see also| x-तीव्र ट्राई|बिटमैप के साथ बिटवाइज़ ट्राई}} | {{see also| x-तीव्र ट्राई|बिटमैप के साथ बिटवाइज़ ट्राई}} | ||
सरल पॉइंटर वेक्टर कार्यान्वयन में ट्राइ नोड्स के लिए विशाल स्थान की आवश्यकता को संबोधित करने | सरल पॉइंटर वेक्टर कार्यान्वयन में ट्राइ नोड्स के लिए विशाल स्थान की आवश्यकता को संबोधित करने हेतु बिटवाइज़ ट्राई का उपयोग किया जाता है। स्ट्रिंग कुंजी सेट में प्रत्येक वर्ण को अलग-अलग बिट्स के माध्यम से दर्शाया जाता है जिसका उपयोग स्ट्रिंग कुंजी पर ट्राई को पार करने के लिए किया जाता है। इस प्रकार के ट्राई के कार्यान्वयन निश्चित-लंबाई कुंजी इनपुट में पहला सेट खोजने के लिए [[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| | {{main|रेडिक्स ट्री}} | ||
रेडिक्स ट्री जिसे कंप्रेस्ड ट्राई के रूप में भी जाना जाता है ट्राई का एक अंतरिक्ष-अनुकूलित संस्करण है जिसमें केवल चाइल्ड वाले नोड्स अपने पेरेंट के साथ विलय हो जाते हैं; एकल चाइल्ड के साथ नोड्स की शाखाओं को हटाने से अंतरिक्ष और समय मेट्रिक्स दोनों में उन्नत परिणाम मिलते हैं।<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 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> | ||
==== पेट्रीसिया ट्री ==== | ==== पेट्रीसिया ट्री ==== | ||
| 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}} पेट्रीसिया ट्री में नोड्स की खोज, इंसर्शन और डिलीशन के लिए स्किप नंबर महत्वपूर्ण है और प्रत्येक पुनरावृत्ति के समय | स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व <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]] | ट्राई का उपयोग जैव सूचना विज्ञान में किया जाता है विशेष रूप से [[अनुक्रम संरेखण]] सॉफ़्टवेयर अनुप्रयोगों जैसे कि BLAST (जैव प्रौद्योगिकी) एल्गोरिदम में जो कंप्रेस्ड ट्राइ में उनकी घटनाओं की स्थिति को संग्रहीत करके किसी पाठ की लंबाई k (जिसे [[k-mer|k-मर्स]] कहा जाता है) के सभी अलग-अलग सबस्ट्रिंग अनुक्रम डेटाबेस{{r|prieto16|p=75}} को अनुक्रमित करता है। | ||
=== इंटरनेट रूटिंग === | === इंटरनेट रूटिंग === | ||
{{see also| | {{see also|लुलिया एल्गोरिथ्म}} | ||
ट्राई के कंप्रेस्ड वेरिएंट जैसे कि [[अग्रेषण सूचना आधार]] ( | ट्राई के कंप्रेस्ड वेरिएंट जैसे कि [[अग्रेषण सूचना आधार]] (FIB) के प्रबंधन के लिए डेटाबेस का उपयोग आईपी [[मार्ग|रूटिंग]] में [[वाइल्डकार्ड मास्क]] आधारित संचालन को हल करने के लिए प्रिफिक्स-आधारित लुकअप के लिए रूटिंग और [[नेटवर्क ब्रिज]] के भीतर [[सबनेटवर्क]] को संग्रहीत करने में किया जाता है।{{r|prieto16|p=75}} | ||
== यह भी देखें == | == यह भी देखें == | ||
{{div col|colwidth=22em}} | {{div col|colwidth=22em}} | ||
* | * सफ़िक्स ट्री | ||
* [[हैश ट्राई]] | * [[हैश ट्राई]] | ||
* हैश ऐरे मैप किया गया ट्राई | * हैश ऐरे मैप किया गया ट्राई | ||
* | * प्रीफिक्स हैश [[Ctrie]] | ||
*सीट्री | *सीट्री | ||
* [[HAT- | * [[HAT-ट्राई]] | ||
{{div col end}} | {{div col end}} | ||
| Line 199: | Line 199: | ||
{{Data structures}} | {{Data structures}} | ||
{{Strings}} | {{Strings}} | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category:CS1 errors]] | |||
[[Category: | [[Category:Collapse templates]] | ||
[[Category:Commons category link from Wikidata]] | |||
[[Category:Created On 10/07/2023]] | [[Category:Created On 10/07/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Multi-column templates]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages using div col with small parameter]] | |||
[[Category:Pages with maths render errors]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Templates using under-protected Lua modules]] | |||
[[Category:Wikipedia fully protected templates|Div col]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:उदाहरण के लिए पायथन (प्रोग्रामिंग भाषा) कोड वाले लेख]] | |||
[[Category:पेड़ (डेटा संरचनाएं)]] | |||
[[Category:स्वचालित रूप से समाप्त हो गया]] | |||
Latest revision as of 11:17, 28 July 2023
| Trie | ||||||||
|---|---|---|---|---|---|---|---|---|
| Type | tree | |||||||
| Invented | 1960 | |||||||
| Invented by | Edward Fredkin, Axel Thue, and René de la Briandais | |||||||
| Time complexity in big O notation | ||||||||
| ||||||||