ट्राई: 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>

[[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{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{x}</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}}

* <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>

 

 

वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को छोटे वर्णमाला पर लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। {{mvar|n}} बाइट्स की एक स्ट्रिंग को वैकल्पिक रूप से {{math|2''n''}} चार-बिट इकाइयों की एक स्ट्रिंग के रूप में माना जा सकता है और प्रति नोड सोलह पॉइंटर्स के साथ ट्राइ में संग्रहीत किया जा सकता है। जबकि सबसे खराब स्थिति में लुकअप को दोगुने नोड्स पर जाने की आवश्यकता होती है जबकि स्थान की आवश्यकताएँ आठ गुना कम हो जाती हैं।{{r| brass|p= 347–352}} अन्य तकनीकों में ASCII वर्णमाला का प्रतिनिधित्व करने वाले 256 बिट्स के बिटमैप के रूप में 256 ASCII पॉइंटर्स के वेक्टर को संग्रहीत करना सम्मिलित है जो व्यक्तिगत नोड्स के आकार को नाटकीय रूप से कम कर देता है।<ref>{{cite book|last1=Bellekens|first1=Xavier|title=Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14|chapter=A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems|date=2014|publisher=ACM|location=Glasgow, Scotland, UK|isbn=978-1-4503-3033-6|pages=302:302–302:309|doi=10.1145/2659651.2659723|arxiv=1704.02272|s2cid=12943246}}</ref>

=== बिटवाइज़ ट्राई ===

{{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>{{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>

==== पेट्रीसिया ट्री ====

| footer = चित्र. 4: पेट्रीसिया ट्री स्ट्रिंग कुंजियों का प्रतिनिधित्व: इन, पूर्णांक, अंतराल, स्ट्रिंग और संरचना।