ट्राई: Difference between revisions

Trie
Trie
Type	tree
Invented	1960
Invented by	Edward Fredkin, Axel Thue, and René de la Briandais
Time complexity in big O notation
Algorithm
Algorithm	Average
Space	O(n)
Search	O(n)
Insert	O(n)
Delete	O(n)

Revision as of 21:40, 16 July 2023

File:Trie example.svg

चित्र 1: कुंजियों के लिए एक प्रयास ए, टू, टी, टेड, टेन, आई, इन, और इन। प्रत्येक पूर्ण अंग्रेजी शब्द के साथ एक मनमाना पूर्णांक मान सम्बद्ध होता है।

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

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

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

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

इतिहास, व्युत्पत्ति, और उच्चारण

स्ट्रिंग्स के सेट का प्रतिनिधित्व करने के लिए ट्राई का विचार पहली बार सन 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]

संचालन

File:Trie representation.png

चित्र 2: स्ट्रिंग सेट का प्रतिनिधित्व करने का प्रयास करें: समुद्र, बेचता है, और वह।

विभिन्न परिचालनों (स्ट्रिंग कुंजी का सम्मिलन, विलोपन और लुकअप) का समर्थन करने का प्रयास करता है। ${\text{nodes}}$ प्रयत्नों से बना है जिसमें ऐसे लिंक सम्मिलित हैं जो या तो अन्य चाइल्ड प्रत्यय चाइल्ड नोड्स के संदर्भ हैं या ${\text{nil}}$ । रूट को छोड़कर, प्रत्येक नोड को केवल अन्य नोड द्वारा इंगित किया जाता है जिसे पैरेंट कहा जाता है। प्रत्येक नोड में ${\text{R}}$ लिंक सम्मिलित है जहाँ ${\text{R}}$ लागू वर्णमाला (औपचारिक भाषाओं) की प्रमुखता है जबकि कोशिशों की पर्याप्त संख्या ${\text{nil}}$ लिंक है। अधिकतर स्थितियों में ${\text{Children}}$ का आकार (अहस्ताक्षरित) ASCII की स्थितियों में सरणी अक्षरों को सांकेतिक अक्षरों में परिवर्तन की बिटलेंथ - 256 है।^[14]^: 732 ${\text{nil}}$ h> भीतर लिंक ${\text{Children}}$ में ${\text{Node}}$ निम्नलिखित विशेषताओं पर जोर देता है:^[14]^: 734^[5]^: 336

वर्ण और स्ट्रिंग कुंजियाँ अंतर्निहित रूप से ट्राई डेटा संरचना प्रतिनिधित्व में संग्रहीत होती हैं और इसमें स्ट्रिंग-समाप्ति को इंगित करने वाला वर्ण प्रहरी मान सम्मिलित होता है।
प्रत्येक नोड में सेट की मजबूत कुंजियों के उपसर्ग का संभावित लिंक होता है।

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

structure Node

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 31: / Line 31: @@
 == अवलोकन ==
-ट्राई स्ट्रिंग-अनुक्रमित लुक-अप डेटा संरचना का एक रूप है जिसका उपयोग उन शब्दों की शब्दकोश सूची को संग्रहीत करने के लिए किया जाता है जिन्हें इस उपाय से खोजा जा सकता है जो [[स्वत: पूर्ण]] की कुशल पीढ़ी की अनुमति देता है।<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>{{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>
+ट्राई बाइनरी खोज ट्री की तुलना में [[स्ट्रिंग-खोज एल्गोरिदम]] जैसे पूर्वानुमानित पाठ, [[अनुमानित स्ट्रिंग मिलान]] और [[वर्तनी जांच]] पर प्रभावशाली हो सकते हैं।<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}}
+[[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{Node}</math> वैकल्पिक रूप से सम्मिलित हो सकता है <math>\text{Value}</math> जो स्ट्रिंग या टर्मिनल नोड के अंतिम अक्षर में संग्रहीत प्रत्येक कुंजी से सम्बद्ध हुआ है।
 {|
 |- style="vertical-align:top"
@@ Line 53: / Line 53: @@
-===खोज रहा हूँ ===
+===खोजना ===
-खोज रहे हैं ए <math>\text{Value}</math> ट्राइ में खोज स्ट्रिंग कुंजी में वर्णों द्वारा निर्देशित किया जाता है, क्योंकि ट्राइ में प्रत्येक नोड में दिए गए स्ट्रिंग में प्रत्येक संभावित वर्ण के लिए एक संबंधित लिंक होता है। इस प्रकार, त्रि के भीतर स्ट्रिंग का अनुसरण करने से संबंधित परिणाम प्राप्त होता है <math>\text{Value}</math> दी गई स्ट्रिंग कुंजी के लिए. ए <math>\text{nil}</math> खोज निष्पादन के भीतर लिंक कुंजी की अस्तित्वहीनता को इंगित करता है।{{r| robert11|p=732-733}}
+ट्राइ में <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{key}</math>) के लिए जड़ित ट्राइ (<math>\text{x}</math>) में खोज प्रक्रिया को लागू करता है{{r|gonnet91|p=135}}
 {|
 |- style="vertical-align:top"
@@ Line 69: / Line 69: @@
       '''return''' x.Value
 |}
-उपरोक्त छद्म कोड में, <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}}
+उपरोक्त छद्म कोड में <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}}
+यदि इसमें बड़ी संख्या में छोटी स्ट्रिंग सम्मिलित हैं, तो बीएसटी की तुलना में ट्राई कम जगह घेरता है, क्योंकि नोड्स सामान्य प्रारंभिक स्ट्रिंग अनुवर्ती साझा करते हैं और संरचना पर कुंजी को अंतर्निहित रूप से संग्रहीत करते हैं।{{r|reema18|p=358}} पेड़ के टर्मिनल नोड में एक गैर-शून्य होता है <math>\text{Value}</math>, और यदि संबंधित मान ट्राई में पाया जाता है तो यह एक खोज हिट है, और यदि ऐसा नहीं है तो खोज मिस हो जाती है।{{r|robert11|p=733}}
 === निवेशन ===
@@ Line 91: / Line 91: @@
 === विलोपन ===
-ट्राई से कुंजी-मूल्य जोड़ी को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत पर चिह्नित करना शामिल है। <math>\text{nil}</math> तदनुसार.{{r|robert11|p=740}}
+ट्राई से कुंजी-मूल्य जोड़ी को हटाने में संबंधित स्ट्रिंग कुंजी के साथ टर्मिनल नोड ढूंढना, टर्मिनल संकेतक और मान को गलत पर चिह्नित करना सम्मिलित है। <math>\text{nil}</math> तदनुसार.{{r|robert11|p=740}}
 स्ट्रिंग कुंजी को हटाने के लिए [[रिकर्सन (कंप्यूटर विज्ञान)]] प्रक्रिया निम्नलिखित है (<math>\text{key}</math>) जड़ित त्रि से (<math>\text{x}</math>).
@@ Line 128: / Line 128: @@
 ==कार्यान्वयन रणनीतियाँ==
-[[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}}
+[[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}}
-वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को एक छोटे वर्णमाला पर एक लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। {{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>
+वर्णमाला में कमी जैसी तकनीकें मूल स्ट्रिंग को एक छोटे वर्णमाला पर एक लंबी स्ट्रिंग के रूप में पुन: व्याख्या करके उच्च स्थान की जटिलता को कम कर सकती हैं। {{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>
@@ Line 155: / Line 155: @@
 | width = 400
 }}
-पेट्रीसिया पेड़ संपीड़ित बाइनरी ट्राइ का एक विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के [[बाइनरी कोड]] का उपयोग करता है।<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}}
+पेट्रीसिया पेड़ संपीड़ित बाइनरी ट्राइ का एक विशेष कार्यान्वयन है जो इसके प्रतिनिधित्व में स्ट्रिंग कुंजियों के [[बाइनरी कोड]] का उपयोग करता है।<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}}
 स्ट्रिंग कुंजियों के साथ पेट्रीसिया पेड़ का प्रतिनिधित्व <math>\{in, integer, interval, string, structure\}</math> चित्र 4 में दिखाया गया है, और नोड्स से सटे प्रत्येक सूचकांक मान स्किप संख्या का प्रतिनिधित्व करता है - बिट का सूचकांक जिसके साथ शाखा तय की जानी है।<ref name="maxime09">{{cite book|title=डेटाबेस सिस्टम का विश्वकोश|first1=Maxime|last1=Crochemore|first2=Thierry|last2=Lecroq|url=https://link.springer.com/referencework/10.1007/978-0-387-39940-9|doi=10.1007/978-0-387-39940-9|isbn=978-0-387-49616-0|publisher=[[Springer Publishing]]|location=[[Boston]], [[United States]]|year=2009|chapter=Trie|bibcode=2009eds..book.....L |via=[[HAL (open archive)]]}}</ref>{{rp|p=3}} नोड 0 पर स्किप नंबर 1 बाइनरी एन्कोडेड ASCII में स्थिति 1 से मेल खाता है जहां कुंजी सेट में सबसे बाईं ओर का बिट भिन्न था <math>X</math>.{{r|maxime09|p=3-4}} पेट्रीसिया ट्री में नोड्स की खोज, सम्मिलन और हटाने के लिए स्किप नंबर महत्वपूर्ण है, और प्रत्येक पुनरावृत्ति के दौरान थोड़ा मास्किंग ऑपरेशन किया जाता है।{{r|gonnet91|p=143}}

Anonymous

Search

ट्राई: Difference between revisions

Namespaces

More

Page actions

Revision as of 21:40, 16 July 2023

Contents

इतिहास, व्युत्पत्ति, और उच्चारण

अवलोकन

संचालन