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

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

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

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

स्ट्रिंग्स के एक सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार 1912 में एक्सल थ्यू द्वारा संक्षेप में वर्णित किया गया था।<ref name=thue>{{cite journal|last=Thue|first=Axel|title=Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen|year=1912|pages=1–67|url=https://archive.org/details/skrifterutgitavv121chri/page/n11/mode/2up|journal=Skrifter Udgivne Af Videnskabs-Selskabet I Christiania|volume=1912|number=1}} Cited by Knuth.</ref><ref name=KnuthVol3/>ट्राइज़ का वर्णन पहली बार 1959 में रेने डे ला ब्रिंडैस द्वारा कंप्यूटर संदर्भ में किया गया था।<ref>{{cite conference |first=René |last=de la Briandais |year=1959 |title=परिवर्तनीय लंबाई कुंजियों का उपयोग करके फ़ाइल खोज|conference=Proc. Western J. Computer Conf. |pages=295–298 |doi=10.1145/1457838.1457895 |s2cid=10963780 |url=https://pdfs.semanticscholar.org/3ce3/f4cc1c91d03850ed84ef96a08498e018d18f.pdf |archive-url=https://web.archive.org/web/20200211163605/https://pdfs.semanticscholar.org/3ce3/f4cc1c91d03850ed84ef96a08498e018d18f.pdf |url-status=dead |archive-date=2020-02-11 }} Cited by Brass and by Knuth.</ref><ref name=KnuthVol3/><ref name="brass">{{cite book|last=Brass|first=Peter|title=उन्नत डेटा संरचनाएँ|publisher=[[Cambridge University Press]]|date=8 September 2008|isbn= 978-0521880374|location=[[UK]]|doi=10.1017/CBO9780511800191|url=https://www.cambridge.org/core/books/advanced-data-structures/D56E2269D7CEE969A3B8105AD5B9254C}}</ref>{{rp|p=336}}

 

== सिंहावलोकन ==

प्रयास स्ट्रिंग-अनुक्रमित लुक-अप डेटा संरचना का एक रूप है, जिसका उपयोग उन शब्दों की एक शब्दकोश सूची को संग्रहीत करने के लिए किया जाता है जिन्हें इस तरीके से खोजा जा सकता है जो [[स्वत: पूर्ण]] की कुशल पीढ़ी की अनुमति देता है।<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>