ट्राई: Difference between revisions

{{about|a tree data structure|the French commune|Trie-sur-Baïse}}

[[Image:trie example.svg|thumb|250px|चित्र 1: कुंजियों के लिए एक प्रयास ए, टू, टी, टेड, टेन, आई, इन, और इन। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ एक मनमाना पूर्णांक मान सम्बद्ध होता है।|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> जोकि एक प्रकार का के-एरी [[ खोज वृक्ष |खोज ट्री]] है। ट्री ([[डेटा संरचना]]) डेटा संरचना जिसका उपयोग  सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये कुंजियाँ अधिकतर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि व्यक्तिगत [[ चरित्र (कंप्यूटिंग) |चरित्र (कंप्यूटिंग)]] द्वारा परिभाषित होते हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनर्प्राप्त करने, उसे बदलने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए [[गहराई-पहली खोज]] को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है।

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

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

इस विचार का वर्णन सन 1960 में [[एडवर्ड फ्रेडकिन]] द्वारा स्वतंत्र रूप से किया गया था<ref name=triememory/> जिन्होंने ट्राई शब्द का उच्चारण करते हुए इसे गढ़ा {{IPAc-en|ˈ|t|r|iː}} (ट्री के रूप में), पुनर्प्राप्ति के मध्य अक्षर के पश्चात।<ref name = DADS>{{cite web|url=https://xlinux.nist.gov/dads/HTML/प्रयास करें.html|title=प्रयास करें|first=Paul E.|last=Black|date=2009-11-16|work=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology]]|archive-url=https://web.archive.org/web/20110429080033/http://xlinux.nist.gov/dads/HTML/प्रयास करें.html|url-status=live|archive-date=2011-04-29}}</ref><ref name="Liang1983"/>जबकि अन्य लेखक इसका उच्चारण करते हैं {{IPAc-en|ˈ|t|r|aɪ}} (जैसा प्रयास करें) इसे मौखिक रूप से ट्री से अलग करने के प्रयास में।<ref name=DADS/><ref name="Liang1983"/><ref name = KnuthVol3>{{cite book|last=Knuth|first=Donald|author-link=Donald Knuth|title=The Art of Computer Programming Volume 3: Sorting and Searching|edition=2nd|year=1997|publisher=Addison-Wesley|isbn=0-201-89685-0|page=492|chapter=6.3: Digital Searching}}</ref>

'''ट्राई,''' स्ट्रिंग-अनुक्रमित लुक-अप डेटा संरचना का रूप है जिसका उपयोग उन शब्दों की शब्दकोश सूची को संग्रहीत करने के लिए किया जाता है जिन्हें इस उपाय से खोजा जा सकता है जो [[स्वत: पूर्ण]] की कुशल पीढ़ी की अनुमति देता है।<ref>{{cite web|url=https://ds.cs.rutgers.edu/assignment-trie/|title=प्रयास करें|year=2022|publisher=School of Arts and Science, [[Rutgers University]]|archive-url=https://ghostarchive.org/archive/Vagxe|url-status=live|archive-date=17 April 2022|access-date=17 April 2022}}</ref><ref>{{cite journal|publisher=[[Syracuse University]]|url=https://surface.syr.edu/eecs_techreports/162/ |doi=10.1017/S0960129500000803|first1=Richard H.|last1=Connelly|first2=F. Lockwood|last2=Morris|year=1993|title= ट्राई डेटा संरचना का सामान्यीकरण|journal= Mathematical Structures in Computer Science|volume=5 |issue=3 |pages=381–418 |s2cid=18747244 }}</ref>{{rp|p=1}} '''उपसर्ग ट्राई''' क्रमबद्ध ट्री डेटा संरचना है जिसका उपयोग एक परिमित वर्णमाला सेट पर स्ट्रिंग्स के सेट के प्रतिनिधित्व में किया जाता है जो सामान्य उपसर्गों के साथ शब्दों के कुशल भंडारण की अनुमति देता है।<ref name="cvr14" />

ट्राई बाइनरी खोज ट्री की तुलना में [[स्ट्रिंग-खोज एल्गोरिदम]] जैसे पूर्वानुमानित पाठ, [[अनुमानित स्ट्रिंग मिलान]] और [[वर्तनी जांच]] पर प्रभावशाली हो सकते हैं।<ref name="aho75" /><ref name="Liang1983" />{{r|reema18|p=358}} ट्राई को ट्री के आकार के [[नियतात्मक परिमित ऑटोमेटन|नियतात्मक परिमित ऑटोमेशन]] के रूप में देखा जा सकता है।<ref>{{cite conference|conference= International Conference on Implementation and Application of Automata |title=स्ट्रिंग्स के सेट से न्यूनतम, चक्रीय, नियतात्मक, परिमित-राज्य ऑटोमेटा के लिए निर्माण एल्गोरिदम की तुलना|first=Jan|last=Daciuk|date=24 June 2003|doi=10.1007/3-540-44977-9_26|url=https://link.springer.com/chapter/10.1007/3-540-44977-9_26|isbn= 978-3-540-40391-3|publisher=[[Springer Publishing]]|pages=255–261}}</ref>

[[File:Trie representation.png|thumb|right|400px|चित्र 2: स्ट्रिंग सेट का प्रतिनिधित्व करने का प्रयास करें: समुद्र, बेचता है, और वह।]]विभिन्न परिचालनों (स्ट्रिंग कुंजी का सम्मिलन, विलोपन और लुकअप) का समर्थन करने का प्रयास करता है। <math>\text{nodes}</math> प्रयत्नों से बना है जिसमें ऐसे लिंक सम्मिलित हैं जो या तो अन्य चाइल्ड प्रत्यय चाइल्ड नोड्स के संदर्भ हैं या <math>\text{nil}</math>।  रूट को छोड़कर, प्रत्येक नोड को केवल अन्य नोड द्वारा इंगित किया जाता है जिसे पैरेंट कहा जाता है। प्रत्येक नोड में <math>\text{R}</math> लिंक सम्मिलित है जहाँ <math>\text{R}</math> लागू वर्णमाला (औपचारिक भाषाओं) की [[प्रमुखता]] है जबकि कोशिशों की पर्याप्त संख्या <math>\text{nil}</math> लिंक है। अधिकतर स्थितियों में <math>\text{Children}</math> का आकार (अहस्ताक्षरित) [[ASCII]] की स्थितियों में सरणी [[अक्षरों को सांकेतिक अक्षरों में बदलना|अक्षरों को सांकेतिक अक्षरों में परिवर्तन]] की बिटलेंथ - 256 है।<ref name="robert11">{{cite book|title=एल्गोरिदम|edition=4|first1=Robert|last1=Sedgewick|first2=Kevin|last2=Wayne|author1-link= Robert_Sedgewick_(computer_scientist) |publisher=[[Addison-Wesley]], [[Princeton University]]|date=3 April 2011|isbn= 978-0321573513 |url=https://algs4.cs.princeton.edu/home/}}</ref>{{rp|p=732}} <math>\text{nil}</math> h> भीतर लिंक <math>\text{Children}</math> में <math>\text{Node}</math> निम्नलिखित विशेषताओं पर जोर देता है:{{r|robert11|p=734}}{{r|brass|p=336}}

# प्रत्येक नोड में सेट की मजबूत कुंजियों के उपसर्ग का संभावित लिंक होता है।

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

ट्राइ में <math>\text{Value}</math> की खोज स्ट्रिंग कुंजी में वर्णों द्वारा निर्देशित की जाती है क्योंकि ट्राइ में प्रत्येक नोड में दिए गए स्ट्रिंग में प्रत्येक संभावित वर्ण के लिए संबंधित लिंक होता है। इस प्रकार ट्राइ के भीतर स्ट्रिंग का अनुसरण करने से दी गई <math>\text{Value}</math> स्ट्रिंग कुंजी के लिए संबंधित परिणाम प्राप्त होता है। <math>\text{nil}</math> खोज निष्पादन के भीतर लिंक कुंजी की अस्तित्वहीनता को इंगित करता है।{{r| robert11|p=732-733}}

निम्नलिखित स्यूडोकोड किसी दी गई स्ट्रिंग कुंजी (<math>\text{key}</math>) के लिए जड़ित ट्राइ (<math>\text{x}</math>) में खोज प्रक्रिया को लागू करता है{{r|gonnet91|p=135}}

उपरोक्त छद्म कोड में <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> चाबियों की संख्या और चाबियों की लंबाई।{{r|reema18|p=358}}

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

=== निवेशन ===

ट्राई में सम्मिलन को कैरेक्टर एन्कोडिंग#कैरेक्टर सेट, कैरेक्टर मैप और कोड पेजों को इंडेक्स के रूप में उपयोग करके निर्देशित किया जाता है। <math>\text{Children}</math> स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने तक सरणी।{{r|robert11|p=733-734}} ट्राई में प्रत्येक नोड [[ मूलांक छँटाई ]] रूटीन की एक कॉल से मेल खाता है, क्योंकि ट्राई संरचना टॉप-डाउन रेडिक्स सॉर्ट के पैटर्न के निष्पादन को दर्शाती है।{{r| gonnet91|p=135}}

यदि एक <math>\text{nil}</math> स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने से पहले लिंक का सामना करना पड़ता है, एक नया <math>\text{Node}</math> बनाया गया है, जैसे पंक्ति 3-5 के साथ।{{r|robert11|p=745}} <math>\text{x.Value}</math> इनपुट को सौंपा जाता है <math>\text{value}</math>; अगर <math>\text{x.Value}</math> नहीं था <math>\text{nil}</math> सम्मिलन के समय, दी गई स्ट्रिंग कुंजी से सम्बद्ध मान वर्तमान कुंजी से प्रतिस्थापित हो जाता है।

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

स्ट्रिंग कुंजी को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है (<math>\text{key}</math>) जड़ित त्रि से (<math>\text{x}</math>).

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

== अन्य डेटा संरचनाओं को बदलना ==

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

ट्राई का उपयोग हैश टेबल को बदलने के लिए किया जा सकता है, जिसके निम्नलिखित फायदे हैं:{{r|reema18|p=358}}

* आकार की संबद्ध कुंजी के साथ एक नोड की खोज करना <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>