ट्राई: Difference between revisions

[[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> जोकि एक प्रकार का के-एरी [[ खोज वृक्ष |खोज ट्री]] है। ट्री ([[डेटा संरचना]]) डेटा संरचना जिसका उपयोग  सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये कुंजियाँ अधिकतर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि व्यक्तिगत [[ चरित्र (कंप्यूटिंग) |चरित्र (कंप्यूटिंग)]] द्वारा परिभाषित होते हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनर्प्राप्त करने, उसे परिवर्तित करने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए [[गहराई-पहली खोज]] को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है।

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

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

इस विचार का वर्णन सन 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: ट्राई स्ट्रिंग सेट का प्रतिनिधित्व: see, sells और she।]]विभिन्न परिचालनों (स्ट्रिंग कुंजी का सम्मिलन, विलोपन और लुकअप) का समर्थन करने का प्रयास करता है। <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{x}</math>) से स्ट्रिंग कुंजी (<math>\text{key}</math>) को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है,

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

[[File:Pointer implementation of a trie.svg|thumb|चित्र 3: बाएं-चाइल्ड के दाएं-सिबलिंग बाइनरी ट्री के रूप में कार्यान्वित ट्राइ: ऊर्ध्वाधर तीर {{mono|child}} सूचक हैं, धराशायी क्षैतिज तीर {{mono|next}} सूचक हैं। इस ट्राई में संग्रहित स्ट्रिंग्स {{mono|{baby, bad, bank, box, dad, dance}}} का सेट है। सूचियों को शब्दकोषीय क्रम में ट्रैवर्सल की अनुमति देने के लिए क्रमबद्ध किया गया है।]]मेमोरी उपयोग और संचालन की गति के मध्य विभिन्न ट्रेड-ऑफ के अनुरूप ट्राई को कई उपायों द्वारा दर्शाया जा सकता है।{{r| brass|p=341}} किसी ट्राई का प्रतिनिधित्व करने के लिए पॉइंटर्स के वेक्टर का उपयोग करने से बड़े स्थान की खपत होती है; जबकि यदि प्रत्येक नोड वेक्टर के लिए एकल लिंक की गई सूची का उपयोग किया जाता है तो मेमोरी स्पेस को रनिंग टाइम के मूल्य पर कम किया जा सकता है क्योंकि वेक्टर <math>\text{nil}</math> की अधिकांश प्रविष्टियाँ सम्मिलित हैं।{{r| KnuthVol3|p=495}}

===संपीड़ित ट्राइ ===

रेडिक्स ट्री जिसे संपीड़ित ट्राई के रूप में भी जाना जाता है ट्राई का एक अंतरिक्ष-अनुकूलित संस्करण है जिसमें केवल चाइल्ड वाले नोड्स अपने पेरेंट के साथ विलय हो जाते हैं; एकल चाइल्ड के साथ नोड्स की शाखाओं को हटाने से अंतरिक्ष और समय मेट्रिक्स दोनों में उन्नत परिणाम मिलते हैं।<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>{{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}}