ट्राई: Difference between revisions
No edit summary |
No edit summary |
||
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 118: | Line 118: | ||
=== [[हैश तालिका]]ओं के लिए प्रतिस्थापन === | === [[हैश तालिका]]ओं के लिए प्रतिस्थापन === | ||
ट्राई का उपयोग हैश टेबल को परिवर्तित करने के लिए किया जा सकता है जिसके निम्नलिखित लाभ हैं:{{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> तालिका के भीतर नोड्स की कुल संख्या को दर्शाता है। | ||
* हैश टेबल के विपरीत ट्राइज़ को ऑपरेशन के लिए हैश फ़ंक्शन की आवश्यकता नहीं होती है; ट्राई में विभिन्न कुंजियों की कोई [[हैश टक्कर]] भी नहीं होती है। | * हैश टेबल के विपरीत ट्राइज़ को ऑपरेशन के लिए हैश फ़ंक्शन की आवश्यकता नहीं होती है; ट्राई में विभिन्न कुंजियों की कोई [[हैश टक्कर]] भी नहीं होती है। | ||
* ट्राई में बकेट जो हैश टेबल बकेट के समान होते हैं जो कुंजी टकराव को संग्रहीत करते हैं एवं केवल तभी आवश्यक होते हैं जब कुंजी एक से अधिक मान से जुड़ी होती है। | * ट्राई में बकेट जो हैश टेबल बकेट के समान होते हैं जो कुंजी टकराव को संग्रहीत करते हैं एवं केवल तभी आवश्यक होते हैं जब कुंजी एक से अधिक मान से जुड़ी होती है। | ||
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 174: | Line 174: | ||
=== इंटरनेट रूटिंग === | === इंटरनेट रूटिंग === | ||
{{see also| | {{see also|लुलिया एल्गोरिथ्म}} | ||
ट्राई के कंप्रेस्ड वेरिएंट जैसे कि [[अग्रेषण सूचना आधार]] (एफआईबी) के प्रबंधन के लिए डेटाबेस का उपयोग आईपी [[मार्ग]] में [[वाइल्डकार्ड मास्क]] आधारित संचालन को हल करने के लिए प्रिफिक्स-आधारित लुकअप के लिए रूटिंग और [[नेटवर्क ब्रिज]] के भीतर [[सबनेटवर्क]] को संग्रहीत करने में किया जाता है।{{r|prieto16|p=75}} | ट्राई के कंप्रेस्ड वेरिएंट जैसे कि [[अग्रेषण सूचना आधार]] (एफआईबी) के प्रबंधन के लिए डेटाबेस का उपयोग आईपी [[मार्ग]] में [[वाइल्डकार्ड मास्क]] आधारित संचालन को हल करने के लिए प्रिफिक्स-आधारित लुकअप के लिए रूटिंग और [[नेटवर्क ब्रिज]] के भीतर [[सबनेटवर्क]] को संग्रहीत करने में किया जाता है।{{r|prieto16|p=75}} | ||
Revision as of 22:36, 20 July 2023
Trie | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | tree | |||||||||||||||
Invented | 1960 | |||||||||||||||
Invented by | Edward Fredkin, Axel Thue, and René de la Briandais | |||||||||||||||
Time complexity in big O notation | ||||||||||||||||
|
कंप्यूटर विज्ञान में ट्राई जिसे डिजिटल ट्री या प्रिफिक्स ट्री भी कहा जाता है[1] जो एक प्रकार का k-ary सर्च ट्री है। ट्री (डेटा संरचना) डेटा संरचना का उपयोग सेट के भीतर से विशिष्ट कुंजियों को ज्ञात करने के लिए किया जाता है। ये कुंजियाँ () अधिकतर स्ट्रिंग (कंप्यूटर विज्ञान) होती हैं जिसमें नोड्स के मध्य लिंक पूरी कुंजी द्वारा नहीं बल्कि विशिष्ट अक्षरों (कंप्यूटिंग) द्वारा परिभाषित होती हैं। किसी कुंजी तक पहुंचने के लिए (उसके मूल्य को पुनः प्राप्त करने, उसे परिवर्तित करने या उसे हटाने के लिए) नोड्स के मध्य लिंक का अनुसरण करते हुए डेप्थ-फर्स्ट सर्च को पार किया जाता है जो कुंजी में प्रत्येक वर्ण का प्रतिनिधित्व करता है।
बाइनरी सर्च ट्री के विपरीत ट्राई में नोड्स अपनी संबंधित कुंजी को संग्रहीत नहीं करते हैं। इसके स्थान पर ट्राई में एक नोड की स्थिति उस कुंजी को परिभाषित करती है जिसके साथ वह संबद्ध है। यह प्रत्येक कुंजी के मान को डेटा संरचना में वितरित करता है और इसका अर्थ है कि आवश्यक नहीं कि प्रत्येक नोड का एक संबद्ध मान हो।
नोड के सभी छोटे भागों में उस मूल नोड से जुड़े स्ट्रिंग का सामान्य प्रिफिक्स होता है और रूट रिक्त स्ट्रिंग से सम्बद्ध होता है। इसके प्रिफिक्स द्वारा पहुंच योग्य डेटा को संग्रहीत करने का यह कार्य रेडिक्स ट्री को नियोजित करके मेमोरी-अनुकूलित उपाय से पूरा किया जा सकता है।
जबकि ट्राई को कैरेक्टर स्ट्रिंग्स द्वारा कुंजीबद्ध किया जा सकता है लेकिन ऐसा होना आवश्यक नहीं है। समान एल्गोरिदम को किसी भी अंतर्निहित प्रकार की ऑर्डर की गई सूचियों के लिए अनुकूलित किया जा सकता है उदाहरण के लिए, अंकों या आकृतियों का क्रम परिवर्तन। विशेष रूप से 'बिटवाइज़ ट्राई' को अलग-अलग बिट्स पर कुंजीबद्ध किया जाता है जो निश्चित-लंबाई वाले बाइनरी डेटा का एक टुकड़ा बनाता है जैसे पूर्णांक या मेमोरी एड्रेस। ट्राई की कुंजी लुकअप जटिलता कुंजी आकार के समानुपाती रहती है। अनुभवहीन कार्यान्वयन में ट्राइ की विशाल स्पेस आवश्यकता से निपटने के लिए कंप्रेस्ड ट्राई जैसे विशिष्ट ट्राइ कार्यान्वयन का उपयोग किया जाता है।
इतिहास, व्युत्पत्ति, और उच्चारण
स्ट्रिंग्स के सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार सन 1912 में एक्सल थ्यू द्वारा संक्षेप में वर्णित किया गया था।[2][3]ट्राइज़ का वर्णन पहली बार सन1959 में रेने डे ला ब्रिंडैस द्वारा कंप्यूटर संदर्भ में किया गया था।[4][3][5]: 336
इस विचार का वर्णन सन 1960 में एडवर्ड फ्रेडकिन द्वारा स्वतंत्र रूप से किया गया था[6] जिन्होंने ट्राई शब्द का उच्चारण करते हुए इसे गढ़ा /ˈtriː/ (ट्री के रूप में), पुनः प्राप्ति के मध्य अक्षर के पश्चात।[7][8]जबकि अन्य लेखक इसका उच्चारण /ˈtraɪ/ (जैसा ट्राई करें) इसे मौखिक रूप से ट्री से पृथक करने के प्रयास में करते हैं।[7][8][3]
अवलोकन
ट्राई, स्ट्रिंग-अनुक्रमित लुक-अप डेटा संरचना का रूप है जिसका उपयोग उन शब्दों की शब्दकोश सूची को संग्रहीत करने के लिए किया जाता है जिन्हें इस उपाय से खोजा जा सकता है जो स्वत: पूर्ण की कुशल पीढ़ी की अनुमति देता है।[9][10]: 1 प्रिफिक्स ट्राई क्रमबद्ध ट्री डेटा संरचना है जिसका उपयोग एक परिमित वर्णमाला सेट पर स्ट्रिंग्स के सेट के प्रतिनिधित्व में किया जाता है जो सामान्य प्रिफिक्स के साथ शब्दों के कुशल भंडारण की अनुमति देता है।[1]
ट्राई बाइनरी सर्च ट्री की तुलना में स्ट्रिंग-सर्च एल्गोरिदम जैसे पूर्वानुमानित पाठ, अनुमानित स्ट्रिंग मिलान और वर्तनी जांच पर प्रभावशाली हो सकते हैं।[11][8][12]: 358 ट्राई को ट्री के आकार के नियतात्मक परिमित ऑटोमेशन के रूप में देखा जा सकता है।[13]
संचालन
ट्राई, विभिन्न परिचालनों (स्ट्रिंग कुंजी का इंसर्शन, डिलीशन और लुकअप) का समर्थन करता है। द्वारा ट्राई का निर्माण होता है जिसमें ऐसे लिंक सम्मिलित हैं जो या तो अन्य चाइल्ड सफिक्स चाइल्ड नोड्स के संदर्भ हैं या । रूट को छोड़कर, प्रत्येक नोड को केवल अन्य नोड द्वारा इंगित किया जाता है जिसे पैरेंट कहा जाता है। प्रत्येक नोड में लिंक सम्मिलित है जहाँ लागू वर्णमाला (औपचारिक भाषाओं) की प्रमुखता है जबकि ट्राई की पर्याप्त संख्या लिंक है। अधिकतर स्थितियों में का आकार (अहस्ताक्षरित) ASCII की स्थितियों में सरणी अक्षरों का सांकेतिक अक्षरों में परिवर्तन की बिटलेंथ - 256 है।[14]: 732 h> भीतर लिंक में निम्नलिखित विशेषताओं पर जोर देता है:[14]: 734 [5]: 336
- वर्ण और स्ट्रिंग कुंजियाँ अंतर्निहित रूप से ट्राई डेटा संरचना प्रतिनिधित्व में संग्रहीत होती हैं और इसमें स्ट्रिंग-समाप्ति को इंगित करने वाला वर्ण प्रहरी मान सम्मिलित होता है।
- प्रत्येक नोड में सेट की मजबूत कुंजियों के प्रिफिक्स का संभावित लिंक होता है।
ट्राई में नोड्स का बुनियादी समग्र डेटा प्रकार इस प्रकार है; वैकल्पिक रूप से सम्मिलित हो सकता है तथा जो स्ट्रिंग या टर्मिनल नोड के अंतिम अक्षर में संग्रहीत प्रत्येक कुंजी से सम्बद्ध हुआ है।
structure Node Children Node[Alphabet-Size] Is-Terminal Boolean Value Data-Type end structure |
खोजना
ट्राइ में की सर्च स्ट्रिंग कुंजी में वर्णों द्वारा निर्देशित की जाती है क्योंकि ट्राइ में प्रत्येक नोड में दिए गए स्ट्रिंग में प्रत्येक संभावित वर्ण के लिए संबंधित लिंक होता है। इस प्रकार ट्राइ के भीतर स्ट्रिंग का अनुसरण करने से दी गई स्ट्रिंग कुंजी के लिए संबंधित परिणाम प्राप्त होता है। सर्च निष्पादन के भीतर लिंक कुंजी की अस्तित्वहीनता को इंगित करता है।[14]: 732-733
निम्नलिखित स्यूडोकोड किसी दी गई स्ट्रिंग कुंजी () के लिए जड़ित ट्राइ () में सर्च प्रक्रिया को लागू करता है[15]: 135
Trie-Find(x, key) for 0 ≤ i < key.length do if x.Children[key[i]] = nil then return false end if x := x.Children[key[i]] repeat return x.Value |
उपरोक्त छद्म कोड में और क्रमशः ट्राई के रूट नोड और स्ट्रिंग कुंजी के सूचक से मेल खाते हैं। मानक ट्राई में सर्च अभियान चलता है तथा स्ट्रिंग पैरामीटर आकार का है और वर्णमाला (औपचारिक भाषाएँ) से मेल खाती है।[16]: 754 दूसरी ओर बाइनरी सर्च ट्री लें सबसे खराब स्थिति में, चूँकि सर्च ट्री की ऊँचाई पर निर्भर करती है () बीएसटी का (संतुलित ट्री की स्थिति में), जहां और , की संख्या और की लंबाई है।[12]: 358
यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं तो BST की तुलना में ट्राई कम स्थान घेरता है क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।[12]: 358 ट्री के टर्मिनल नोड में गैर-शून्य होता है और यदि संबंधित मान ट्राई में पाया जाता है तो यह सर्च हिट है और यदि ऐसा नहीं है तो सर्च मिस हो जाती है।[14]: 733
प्रविष्टि
ट्राई में इंसर्शन को कैरेक्टर एन्कोडिंग, कैरेक्टर मैप और कोड पेजों को इंडेक्स के रूप में उपयोग करके निर्देशित किया जाता है। स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने तक सरणी।[14]: 733-734 ट्राई में प्रत्येक नोड रेडिक्स सॉर्ट रूटीन की कॉल से मेल खाता है क्योंकि ट्राई संरचना टॉप-डाउन रेडिक्स सॉर्ट के पैटर्न के निष्पादन को दर्शाती है।[15]: 135
1 Trie-Insert(x, key, value) 2 for 0 ≤ i < key.length do 3 if x.Children[key[i]] = nil then 4 x.Children[key[i]] := Node() 5 end if 6 x := x.Children[key[i]] 7 repeat 8 x.Value := value 9 x.Is-Terminal := True |
यदि स्ट्रिंग कुंजी के अंतिम अक्षर तक पहुंचने से पहले लिंक का सामना करना पड़ता है एवं नया बनाया गया है जैसे पंक्ति 3-5 के साथ।[14]: 745 इनपुट को सौंपा जाता है; यदि इंसर्शन के समय नहीं था एवं दी गई स्ट्रिंग कुंजी से सम्बद्ध मान वर्तमान कुंजी से प्रतिस्थापित हो जाता है।
विलोपन
ट्राई से -वैल्यू पेअर को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत पर चिह्नित करना सम्मिलित है। तदनुसार.[14]: 740
रूटेड ट्राई () से स्ट्रिंग कुंजी () को हटाने के लिए रिकर्सन (कंप्यूटर विज्ञान) प्रक्रिया निम्नलिखित है,
1 Trie-Delete(x, key) 2 if key = nil then 3 if x.Is-Terminal = True then 4 x.Is-Terminal := False 5 x.Value := nil 6 end if 7 for 0 ≤ i < x.Children.length 8 if x.Children[i] != nil 9 return x 10 end if 11 repeat 12 return nil 13 end if 14 x.Children[key[0]] := Trie-Delete(x.Children[key[0]], key[1:]) 15 return x |
प्रक्रियाएँ जाँचने से प्रारम्भ होती हैं; टर्मिनल नोड या स्ट्रिंग कुंजी के अंत के आगमन को दर्शाता है। यदि टर्मिनल और यदि इसमें कोई चाइल्ड नहीं है तो नोड को ट्राइ से हटा दिया जाता है (पंक्ति 14 वर्ण सूचकांक को निर्दिष्ट करता है) ) जबकि नोड के टर्मिनल के बिना स्ट्रिंग कुंजी का अंत इंगित करता है कि कुंजी उपस्थित नहीं है इस प्रकार प्रक्रिया ट्राई को संशोधित नहीं करती है। प्रत्यावर्तन वृद्धि करके का सूचकांक आगे बढ़ता है।
अन्य डेटा संरचनाओं को परिवर्तित करना
हैश तालिकाओं के लिए प्रतिस्थापन
ट्राई का उपयोग हैश टेबल को परिवर्तित करने के लिए किया जा सकता है जिसके निम्नलिखित लाभ हैं:[12]: 358
- आकार की संबद्ध कुंजी के साथ नोड को सर्च करना की जटिलता है जबकि अपूर्ण हैश फ़ंक्शन में कई टकराने वाली कुंजियाँ हो सकती हैं और ऐसी तालिका की सबसे खराब स्थिति वाली लुकअप गति होगी जहाँ तालिका के भीतर नोड्स की कुल संख्या को दर्शाता है।
- हैश टेबल के विपरीत ट्राइज़ को ऑपरेशन के लिए हैश फ़ंक्शन की आवश्यकता नहीं होती है; ट्राई में विभिन्न कुंजियों की कोई हैश टक्कर भी नहीं होती है।
- ट्राई में बकेट जो हैश टेबल बकेट के समान होते हैं जो कुंजी टकराव को संग्रहीत करते हैं एवं केवल तभी आवश्यक होते हैं जब कुंजी एक से अधिक मान से जुड़ी होती है।
- ट्राई के भीतर स्ट्रिंग कुंजियों को पूर्व निर्धारित वर्णमाला क्रम का उपयोग करके क्रमबद्ध किया जा सकता है।
जबकि हैश तालिका की तुलना में ट्राई कम कुशल होते हैं जब डेटा को सीधे कंप्यूटर डेटा स्टोरेज जैसे कि हार्ड डिस्क ड्राइव पर एक्सेस किया जाता है जिसमें मुख्य मेमोरी की तुलना में अधिक रैंडम एक्सेस समय होता है।[6] जब कुंजी मान को सरलता से स्ट्रिंग के रूप में प्रस्तुत नहीं किया जा सकता है तो कोशिशें भी हानिकारक होती हैं जैसे कि फ़्लोटिंग पॉइंट संख्याएँ जहाँ एकाधिक प्रतिनिधित्व संभव हैं (उदाहरण के लिए 1, 1.0, +1.0, 1.00, आदि के बराबर है)[12]: 359 जबकि इसे दो के पूरक प्रारूप की तुलना में IEEE 754 में बाइनरी संख्या के रूप में स्पष्ट रूप से दर्शाया जा सकता है।[17]
कार्यान्वयन रणनीतियाँ
मेमोरी उपयोग और संचालन की गति के मध्य विभिन्न ट्रेड-ऑफ के अनुरूप ट्राई को कई उपायों द्वारा दर्शाया जा सकता है।[5]: 341 किसी ट्राई का प्रतिनिधित्व करने के लिए पॉइंटर्स के वेक्टर का उपयोग करने से बड़े स्थान की खपत होती है; जबकि यदि प्रत्येक नोड वेक्टर के लिए एकल लिंक की गई सूची का उपयोग किया जाता है तो मेमोरी स्पेस को रनिंग टाइम के मूल्य पर कम किया जा सकता है क्योंकि वेक्टर की अधिकांश प्रविष्टियाँ सम्मिलित हैं।[3]: 495
वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को छोटे वर्णमाला पर लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। n बाइट्स की एक स्ट्रिंग को वैकल्पिक रूप से 2n चार-बिट इकाइयों की एक स्ट्रिंग के रूप में माना जा सकता है और प्रति नोड सोलह पॉइंटर्स के साथ ट्राइ में संग्रहीत किया जा सकता है। जबकि सबसे खराब स्थिति में लुकअप को दोगुने नोड्स पर जाने की आवश्यकता होती है जबकि स्थान की आवश्यकताएँ आठ गुना कम हो जाती हैं।[5]: 347–352 अन्य तकनीकों में ASCII वर्णमाला का प्रतिनिधित्व करने वाले 256 बिट्स के बिटमैप के रूप में 256 ASCII पॉइंटर्स के वेक्टर को संग्रहीत करना सम्मिलित है जो व्यक्तिगत नोड्स के आकार को नाटकीय रूप से कम कर देता है।[18]
बिटवाइज़ ट्राई
सरल पॉइंटर वेक्टर कार्यान्वयन में ट्राइ नोड्स के लिए विशाल स्थान की आवश्यकता को संबोधित करने हेतु बिटवाइज़ ट्राई का उपयोग किया जाता है। स्ट्रिंग कुंजी सेट में प्रत्येक वर्ण को अलग-अलग बिट्स के माध्यम से दर्शाया जाता है जिसका उपयोग स्ट्रिंग कुंजी पर ट्राई को पार करने के लिए किया जाता है। इस प्रकार के ट्राई के कार्यान्वयन निश्चित-लंबाई कुंजी इनपुट में पहला सेट खोजने के लिए SIMD CPU निर्देशों का उपयोग करते हैं (उदाहरण के लिए जीएनयू कंपाइलर संग्रह) __builtin_clz()
आंतरिक कार्य)। तदनुसार, सेट बिट का उपयोग 32- या 64-प्रविष्टि आधारित बिटवाइज़ ट्री में पहले आइटम या चाइल्ड नोड को अनुक्रमित करने के लिए किया जाता है। इसके पश्चात कुंजी में प्रत्येक आगामी बिट का परीक्षण करके खोज आगे बढ़ती है।[19]
यह प्रक्रिया सीपीयू रजिस्टर स्वतंत्रता के कारण कैच-स्थानीय और समानांतर प्रोग्रामिंग मॉडल भी है और इस प्रकार क्रम से बाहर यह निष्पादित सीपीयू पर प्रदर्शन करती है।[19]
कंप्रेस्ड ट्राइ
रेडिक्स ट्री जिसे कंप्रेस्ड ट्राई के रूप में भी जाना जाता है ट्राई का एक अंतरिक्ष-अनुकूलित संस्करण है जिसमें केवल चाइल्ड वाले नोड्स अपने पेरेंट के साथ विलय हो जाते हैं; एकल चाइल्ड के साथ नोड्स की शाखाओं को हटाने से अंतरिक्ष और समय मेट्रिक्स दोनों में उन्नत परिणाम मिलते हैं।[20][21]: 452 यह तब सबसे अच्छा कार्य करता है जब ट्राई स्थिर रहता है और संग्रहीत कुंजियों का सेट उनके प्रतिनिधित्व स्थान के भीतर बहुत विरल होता है।[22]: 3–16
एक और दृष्टिकोण ट्राइ को पैक करना है जिसमें स्वचालित हाइफ़नेशन एल्गोरिथ्म पर लागू एक विरल पैक ट्राइ का कुशल स्थानीय कार्यान्वयन होता है जिसमें प्रत्येक नोड के वंशजों को मेमोरी में इंटरलीव किया जा सकता है।[8]
पेट्रीसिया ट्री
पेट्रीसिया ट्री कंप्रेस्ड बाइनरी ट्राइ का विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के बाइनरी कोड का उपयोग करता है।[23][15]: 140 पेट्रीसिया ट्री के प्रत्येक नोड में निर्देशिका होती है जिसे स्किप नंबर के रूप में जाना जाता है जो ट्रैवर्सल के समय रिक्त सब ट्री से बचने के लिए नोड के ब्रांचिंग इंडेक्स को संग्रहीत करता है।[15]: 140-141 कुंजियों के विरल वितरण के कारण बड़ी संख्या में लीफ-नोड्स के कारण ट्राई के सरल कार्यान्वयन में अत्यधिक भंडारण की खपत होती है; ऐसे स्थितियों के लिए पेट्रीसिया के ट्री कारगर हो सकते हैं।[15]: 142 [24]: 3
स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व चित्र 4 में दिखाया गया है और नोड्स से सटे प्रत्येक सूचकांक मान स्किप संख्या का प्रतिनिधित्व करता है - बिट का सूचकांक जिसके साथ शाखा तय की जानी है।[24]: 3 नोड 0 पर स्किप नंबर 1 बाइनरी एन्कोडेड ASCII में स्थिति 1 से मेल खाता है जहां कुंजी सेट में सबसे बाईं ओर का बिट भिन्न था।[24]: 3-4 पेट्रीसिया ट्री में नोड्स की खोज, इंसर्शन और डिलीशन के लिए स्किप नंबर महत्वपूर्ण है और प्रत्येक पुनरावृत्ति के समय थोड़ा मास्किंग ऑपरेशन किया जाता है।[15]: 143
अनुप्रयोग
ट्राई डेटा संरचनाओं का उपयोग सामान्य रूप से पूर्वानुमानित पाठ या स्वत: पूर्ण शब्दकोशों और अनुमानित स्ट्रिंग मिलान में किया जाता है।[11] ट्राई तीव्र खोजों को सक्षम करते हैं जो कम जगह घेरते हैं एवं खासकर जब सेट में बड़ी संख्या में छोटे तार होते हैं तथा इस प्रकार वर्तनी जांच, हाइफ़नेशन अनुप्रयोगों और सबसे लंबे प्रिफिक्स मिलान एल्गोरिदम में उपयोग किया जाता है।[8][12]: 358 जबकि यदि शब्दकोश शब्दों को संग्रहीत करना ही आवश्यक है (अर्थात प्रत्येक शब्द से जुड़े मेटाडेटा को संग्रहीत करने की कोई आवश्यकता नहीं है) एवं न्यूनतम DAFSA या रेडिक्स ट्री एक ट्राई की तुलना में कम भंडारण स्थान का उपयोग करेगा। ऐसा इसलिए है क्योंकि DAFSAs और रेडिक्स ट्री ट्राई से समान शाखाओं को कंप्रेस्ड कर सकते हैं जो संग्रहीत किए जा रहे विभिन्न शब्दों के समान प्रत्ययों (या भागों) से मेल खाते हैं। स्ट्रिंग शब्दकोशों का उपयोग प्राकृतिक भाषा प्रसंस्करण में भी किया जाता है जैसे कि पाठ कोष का शब्दकोष खोजना।[25]: 73
श्रेणीबद्ध करना
स्ट्रिंग कुंजियों के सेट के लेक्सिकोग्राफ़िक क्रम को दी गई कुंजियों के लिए ट्राई बनाकर और ट्री ट्रैवर्सल प्री-ऑर्डर कार्यान्वयन में ट्री को पार करके कार्यान्वित किया जा सकता है;[26] यह भी मूलांक प्रकार का एक रूप है।[27] ट्राई बर्स्टसॉर्ट के लिए मूलभूत डेटा संरचनाएं भी हैं जो 2007 तक सबसे तीव्र स्ट्रिंग सॉर्टिंग एल्गोरिदम होने [28] एवं सीपीयू कैच (कंप्यूटिंग) के कुशल उपयोग के लिए उल्लेखनीय है।[29]
पूर्ण-टेक्स्ट सर्च
विशेष प्रकार की ट्राई जिसे [[प्रीफिक्स ट्री]] कहा जाता है का उपयोग तीव्रता से पूर्ण-टेक्स्ट सर्च करने के लिए किसी टेक्स्ट में सभी प्रीफिक्स को अनुक्रमित करने के लिए किया जा सकता है।[30]
वेब सर्च इंजन
विशेष प्रकार की ट्राई जिसे कंप्रेस्ड ट्राई कहा जाता है का उपयोग वेब सर्च इंजनों में वेब अनुक्रमण को संग्रहीत करने के लिए किया जाता है - जो सभी खोजने योग्य शब्दों का एक संग्रह है।[31] प्रत्येक टर्मिनल नोड कीवर्ड से मेल खाने वाले पेजों के लिए यूआरएल की सूची से सम्बद्ध होता है - जिसे घटना सूची कहा जाता है। ट्राई को मुख्य मेमोरी में संग्रहीत किया जाता है जबकि घटना को बाहरी स्टोरेज में रखा जाता है एवं अधिकतर बड़े कंप्यूटर क्लस्टर में या इन-मेमोरी इंडेक्स बाहरी स्थान पर संग्रहीत दस्तावेजों को इंगित करता है।[32]
जैव सूचना विज्ञान
ट्राई का उपयोग जैव सूचना विज्ञान में किया जाता है विशेष रूप से अनुक्रम संरेखण सॉफ़्टवेयर अनुप्रयोगों जैसे कि BLAST (जैव प्रौद्योगिकी) एल्गोरिदम में जो कंप्रेस्ड ट्राइ में उनकी घटनाओं की स्थिति को संग्रहीत करके किसी पाठ की लंबाई k (जिसे k-mers कहा जाता है) के सभी अलग-अलग सबस्ट्रिंग अनुक्रम डेटाबेस[25]: 75 को अनुक्रमित करता है।
इंटरनेट रूटिंग
ट्राई के कंप्रेस्ड वेरिएंट जैसे कि अग्रेषण सूचना आधार (एफआईबी) के प्रबंधन के लिए डेटाबेस का उपयोग आईपी मार्ग में वाइल्डकार्ड मास्क आधारित संचालन को हल करने के लिए प्रिफिक्स-आधारित लुकअप के लिए रूटिंग और नेटवर्क ब्रिज के भीतर सबनेटवर्क को संग्रहीत करने में किया जाता है।[25]: 75
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 Maabar, Maha (17 November 2014). "डेटा संरचना का प्रयास करें". CVR, University of Glasgow. Archived from the original on 27 January 2021. Retrieved 17 April 2022.
- ↑ Thue, Axel (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen". Skrifter Udgivne Af Videnskabs-Selskabet I Christiania. 1912 (1): 1–67. Cited by Knuth.
- ↑ 3.0 3.1 3.2 3.3 Knuth, Donald (1997). "6.3: Digital Searching". The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 492. ISBN 0-201-89685-0.
- ↑ de la Briandais, René (1959). परिवर्तनीय लंबाई कुंजियों का उपयोग करके फ़ाइल खोज (PDF). Proc. Western J. Computer Conf. pp. 295–298. doi:10.1145/1457838.1457895. S2CID 10963780. Archived from the original (PDF) on 2020-02-11. Cited by Brass and by Knuth.
- ↑ 5.0 5.1 5.2 5.3 Brass, Peter (8 September 2008). उन्नत डेटा संरचनाएँ. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 978-0521880374.
- ↑ 6.0 6.1 Edward Fredkin (1960). "स्मृति का प्रयास करें". Communications of the ACM. 3 (9): 490–499. doi:10.1145/367390.367400. S2CID 15384533.
- ↑ 7.0 7.1 Black, Paul E. (2009-11-16). करें.html "प्रयास करें". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. करें.html Archived from the original on 2011-04-29.
{{cite web}}
: Check|archive-url=
value (help); Check|url=
value (help) - ↑ 8.0 8.1 8.2 8.3 8.4 Franklin Mark Liang (1983). कॉम-पुट-एर द्वारा वर्ड हाई-फेन-ए-टियन (PDF) (Doctor of Philosophy thesis). Stanford University. Archived (PDF) from the original on 2005-11-11. Retrieved 2010-03-28.
- ↑ "प्रयास करें". School of Arts and Science, Rutgers University. 2022. Archived from the original on 17 April 2022. Retrieved 17 April 2022.
- ↑ Connelly, Richard H.; Morris, F. Lockwood (1993). "ट्राई डेटा संरचना का सामान्यीकरण". Mathematical Structures in Computer Science. Syracuse University. 5 (3): 381–418. doi:10.1017/S0960129500000803. S2CID 18747244.
- ↑ 11.0 11.1 Aho, Alfred V.; Corasick, Margaret J. (Jun 1975). "Efficient String Matching: An Aid to Bibliographic Search" (PDF). Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855. S2CID 207735784.
- ↑ 12.0 12.1 12.2 12.3 12.4 12.5 Thareja, Reema (13 October 2018). "Hashing and Collision". सी का उपयोग कर डेटा संरचनाएं (2 ed.). Oxford University Press. ISBN 9780198099307.
- ↑ Daciuk, Jan (24 June 2003). स्ट्रिंग्स के सेट से न्यूनतम, चक्रीय, नियतात्मक, परिमित-राज्य ऑटोमेटा के लिए निर्माण एल्गोरिदम की तुलना. International Conference on Implementation and Application of Automata. Springer Publishing. pp. 255–261. doi:10.1007/3-540-44977-9_26. ISBN 978-3-540-40391-3.
- ↑ 14.0 14.1 14.2 14.3 14.4 14.5 14.6 Sedgewick, Robert; Wayne, Kevin (3 April 2011). एल्गोरिदम (4 ed.). Addison-Wesley, Princeton University. ISBN 978-0321573513.
- ↑ 15.0 15.1 15.2 15.3 15.4 15.5 Gonnet, G. H.; Yates, R. Baeza (January 1991). Handbook of algorithms and data structures: in Pascal and C (2 ed.). Boston, United States: Addison-Wesley. ISBN 978-0-201-41607-7.
- ↑ Patil, Virsha H. (10 May 2012). C++ का उपयोग कर डेटा संरचनाएँ. Oxford University Press. ISBN 9780198066231.
- ↑ S. Orley; J. Mathews. "The IEEE 754 Format". Department of Mathematics and Computer Science, Emory University. Archived from the original on 28 March 2022. Retrieved 17 April 2022.
- ↑ Bellekens, Xavier (2014). "A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems". Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14. Glasgow, Scotland, UK: ACM. pp. 302:302–302:309. arXiv:1704.02272. doi:10.1145/2659651.2659723. ISBN 978-1-4503-3033-6. S2CID 12943246.
- ↑ 19.0 19.1 Willar, Dan E. (27 January 1983). "अंतरिक्ष O(n) में लॉग-लघुगणकीय सबसे खराब स्थिति वाले श्रेणी प्रश्न संभव हैं". Information Processing Letters. ScienceDirect. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3.
- ↑ Sartaj Sahni (2004). "Data Structures, Algorithms, & Applications in C++: Tries". University of Florida. Archived from the original on 16 July 2016. Retrieved 17 April 2022.
{{cite web}}
:|archive-date=
/|archive-url=
timestamp mismatch (help) - ↑ Mehta, Dinesh P.; Sahni, Sartaj (7 March 2018). "Tries". डेटा संरचनाओं और अनुप्रयोगों की पुस्तिका (2 ed.). Chapman & Hall, University of Florida. ISBN 978-1498701853.
- ↑ Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard E. Watson (1 March 2000). "न्यूनतम एसाइक्लिक परिमित-राज्य ऑटोमेटा का वृद्धिशील निर्माण". Computational Linguistics. MIT Press. 26 (1): 3–16. arXiv:cs/0007009. Bibcode:2000cs........7009D. doi:10.1162/089120100561601.
- ↑ "Patricia tree". National Institute of Standards and Technology. Archived from the original on 14 February 2022. Retrieved 17 April 2022.
- ↑ 24.0 24.1 24.2 Crochemore, Maxime; Lecroq, Thierry (2009). "Trie". डेटाबेस सिस्टम का विश्वकोश. Boston, United States: Springer Publishing. Bibcode:2009eds..book.....L. doi:10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0 – via HAL (open archive).
- ↑ 25.0 25.1 25.2 Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (March 2016). "व्यावहारिक संपीड़ित स्ट्रिंग शब्दकोश". Information Systems. Elsevier. 56: 73–108. doi:10.1016/j.is.2015.08.008. ISSN 0306-4379.
- ↑ Kärkkäinen, Juha. "Lecture 2" (PDF). University of Helsinki.
एक ट्राइ में नोड्स का प्रीऑर्डर उन स्ट्रिंग्स के लेक्सिकोग्राफ़िकल क्रम के समान है जो वे प्रतिनिधित्व करते हैं, यह मानते हुए कि नोड के बच्चों को किनारे के लेबल द्वारा ऑर्डर किया गया है।
- ↑ Kallis, Rafael (2018). "The Adaptive Radix Tree (Report #14-708-887)" (PDF). University of Zurich: Department of Informatics, Research Publications.
- ↑ Ranjan Sinha and Justin Zobel and David Ring (Feb 2006). "प्रतिलिपि का उपयोग करके कैश-कुशल स्ट्रिंग सॉर्टिंग" (PDF). ACM Journal of Experimental Algorithmics. 11: 1–32. doi:10.1145/1187436.1187439. S2CID 3184411.
- ↑ J. Kärkkäinen and T. Rantala (2008). "Engineering Radix Sort for Strings". In A. Amir and A. Turpin and A. Moffat (ed.). स्ट्रिंग प्रोसेसिंग और सूचना पुनर्प्राप्ति, प्रोक। शिखर. Lecture Notes in Computer Science. Vol. 5280. Springer. pp. 3–14. doi:10.1007/978-3-540-89097-3_3. ISBN 978-3-540-89096-6.
- ↑ Giancarlo, Raffaele (28 May 1992). "अनुप्रयोगों के साथ वर्गाकार मैट्रिक्स में प्रत्यय वृक्ष का सामान्यीकरण". SIAM Journal on Computing. Society for Industrial and Applied Mathematics. 24 (3): 520–562. doi:10.1137/S0097539792231982. ISSN 0097-5397.
- ↑ Yang, Lai; Xu, Lida; Shi, Zhongzhi (23 March 2012). "शब्दकोष खोज के लिए एक उन्नत गतिशील हैश TRIE एल्गोरिथ्म". Enterprise Information Systems. 6 (4): 419–432. Bibcode:2012EntIS...6..419Y. doi:10.1080/17517575.2012.665483. S2CID 37884057.
- ↑ Transier, Frederik; Sanders, Peter (December 2010). "इन-मेमोरी टेक्स्ट सर्च इंजन की इंजीनियरिंग बुनियादी एल्गोरिदम". ACM Transactions on Information Systems. Association for Computing Machinery. 29 (1): 1–37. doi:10.1145/1877766.1877768. S2CID 932749.