उपसर्ग खोज पेड़ों के विषय को हब पर कई बार उठाया गया है यहां , उदाहरण के लिए, यह संक्षेप में वर्णन करता है कि एक उपसर्ग वृक्ष क्या है और इसकी आवश्यकता क्यों है, और ऐसे पेड़ों पर मूल संचालन का वर्णन करता है (खोज, डालें, हटाएं)। दुर्भाग्य से, कार्यान्वयन के बारे में कुछ नहीं कहा गया है। यह हालिया पोस्ट अजगर डेट्री लाइब्रेरी, लिब्डाट्री लाइब्रेरी के लिए साइथॉन रैपर को देखता है। अंतिम लिंक नियतात्मक परिमित राज्य मशीनों (गिरफ्तारी का उपयोग करके) के रूप में आंशिक रूप से संकुचित उपसर्ग पेड़ों के कार्यान्वयन का एक अच्छा विवरण प्रदान करता है। मैंने इस विषय पर अपने पाँच सेंट का योगदान करने का निर्णय लिया, जो कि पॉइंटर्स का उपयोग करते हुए उपसर्ग पेड़ों के C ++ में कार्यान्वयन पर विचार करता है। इसके अलावा, एक और लक्ष्य था - संतुलित बाइनरी सर्च ट्री ( AVL ट्री ) और एक संपीड़ित उपसर्ग ट्री का उपयोग करके एक दूसरे के साथ तार की खोज की तुलना करना।

परिचय

याद रखें कि एक उपसर्ग वृक्ष एक डेटा संरचना है जिसे वस्तुओं को थोड़ा संरचना के साथ स्टोर करने के लिए डिज़ाइन किया गया है, जैसे कि तार। अगला, हम ASCII वर्णमाला में बिल्कुल तारों के भंडारण के लिए उपसर्ग पेड़ों के कार्यान्वयन पर विचार करेंगे, प्रत्येक पंक्ति एक टर्मिनल चरित्र के साथ समाप्त होती है, जो स्ट्रिंग में कहीं और नहीं मिलती है। आंकड़ों और उदाहरणों में, टर्मिनल चिन्ह को डॉलर के संकेत द्वारा और शून्य वर्ण द्वारा कोड में दर्शाया जाएगा (इस प्रकार, हमारे कार्यान्वयन में, तार मानक सी-स्ट्रिंग्स होंगे, जो हमें मानक पुस्तकालय string.h का उपयोग करने की अनुमति देता है)। अन्य वर्णमालाओं के लिए, निम्नलिखित में से सभी को मूल रूप से लिया जाना चाहिए।

एक साधारण उपसर्ग वृक्ष में, एक निश्चित प्रतीक प्रत्येक किनारे को सौंपा जाता है, जबकि कोने में विभिन्न सेवा (या उपयोगकर्ता) जानकारी संग्रहीत होती है। इस प्रकार, पेड़ की जड़ से इसकी कुछ पत्तियों तक का कोई भी मार्ग ठीक एक पंक्ति को परिभाषित करता है। इस स्ट्रिंग को निर्दिष्ट पेड़ में संग्रहीत माना जाता है। उदाहरण के लिए, निम्नलिखित आकृति में, उपसर्ग वृक्ष लाइनों के निम्नलिखित सेट को संग्रहीत करता है {abab $, aba $, bc $, b $, bac $, baca $}। बाईं ओर जड़, पत्तियां (उनकी संख्या लाइनों की संख्या के साथ मेल खाती है) - दाईं ओर। बाका $ लाइन के अनुरूप पथ को लाल रंग में हाइलाइट किया गया है।

एक चौकस पाठक आसानी से नोटिस करेगा कि इस अवतार में, उपसर्ग पेड़ एक साधारण नियतात्मक परिमित राज्य मशीन है , जो स्वीकार करने वाले राज्य पेड़ की पत्तियों के अनुरूप हैं। दरअसल, लिबडाट्री लाइब्रेरी में उपसर्ग पेड़ों का कार्यान्वयन इस विचार पर आधारित है । ऑटोमेटन स्वयं को सरणियों का उपयोग करके दर्शाया गया है।

मशीन के आकार को कम करने के लिए, पेड़ का उपयोग आंशिक रूप से संपीड़ित रूप में किया जाता है, जब पेड़ के सभी "पूंछ" (बिना पत्तों वाली शाखाएं) लाइनों (चित्रा नीचे) में पैक किए जाते हैं। आप आगे जा सकते हैं और एक समान तरीके से शाखा के बिना सभी जंजीरों को संकुचित कर सकते हैं (चित्रा बी )। इस मामले में, पेड़ एक परिमित राज्य मशीन बनना बंद कर देता है (या बल्कि, यह एक राज्य मशीन है, लेकिन तारों के वर्णमाला के ऊपर, वर्ण नहीं) और इसके उपयोग से सरणियों का उपयोग समस्याग्रस्त हो जाता है - एक पेड़ के साथ काम करना, एक ऑटोमेटन के साथ, इस तथ्य पर बहुत निर्भर करता है कि वर्णमाला का आकार क्या है? परिमित और ओ (1) समय में किसी भी वर्ण के लिए इस वर्णमाला में इसकी क्रम संख्या निर्धारित करना संभव है (यह तकनीक तार के साथ काम नहीं करेगी)। हालाँकि, यदि पॉइंटर्स स्ट्रिंग स्टोरेज की समस्याओं को लागू करते हैं, तो उन्हें नहीं होना चाहिए।

संकेत के साथ एक पेड़ का प्रतिनिधित्व

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

एक अन्य समस्या - ट्री नोड का आउटगोइंग डिग्री मनमाना हो सकता है (उपयोग किए गए वर्णमाला के आकार तक)। इस समस्या को हल करने के लिए, हम मानक तकनीक लागू करते हैं, अर्थात्, हम प्रत्येक नोड में बाल नोड्स की एक सूची संग्रहीत करेंगे। सूची बस से जुड़ी होगी और हम केवल नोड में सूची के प्रमुख (सबसे बड़ी बेटी) को संग्रहीत करेंगे। यह हमें एक ही समय में खाली जड़ को छोड़ने की अनुमति देगा। अब पेड़ को एक पॉइंटर द्वारा पुरानी जड़ के बच्चे के नोड्स की सूची के प्रमुख को दर्शाया जाएगा (यानी हम पेड़ को जंगल से बदल देते हैं)। इस प्रकार, प्रत्येक नोड में अब ठीक दो पॉइंटर्स होंगे: लिंक - सबसे बड़ी चाइल्ड नोड के लिए, अगली - अपनी छोटी बहन के लिए। निम्नलिखित आंकड़ा इस तरह के परिवर्तन की प्रक्रिया को दर्शाता है, नीले तीर लिंक बिंदुओं के अनुरूप हैं, लाल तीर अगले बिंदुओं के अनुरूप हैं।

इसके अलावा, एक पेड़ के साथ काम करने के तर्क को समझने के लिए, बाईं ओर की आकृति में दिखाए गए आरेख को ध्यान में रखना उपयोगी है, जबकि पेड़ का वास्तविक प्रतिनिधित्व दाईं ओर दिखाया जाएगा।

इसलिए, स्पष्ट रूप से, हमने एक पेड़ से एक परिवर्तनशील आउटगोइंग डिग्री (सामान्य वृक्ष) के साथ एक बाइनरी ट्री पर स्विच किया, जिसमें लिंक और अगले पॉइंटर्स दाएं और बाएं उपप्रकारों के लिए पॉइंटर्स की भूमिका निभाते हैं। निम्न चित्र यह प्रदर्शित करता है।

अब हम कार्यान्वयन के लिए आगे बढ़ सकते हैं। ट्री नोड एक कीचेन है, इसकी लंबाई लेन है (टर्मिनल वर्णों के साथ श्रृंखला समाप्त नहीं होती है, इसलिए आपको इसकी लंबाई स्पष्ट रूप से जानने की आवश्यकता है), और दो लिंक और अगले पॉइंटर्स। प्लस एक न्यूनतम कंस्ट्रक्टर जो एक ट्रीवियल ट्री बनाता है जिसमें एक दिए गए कुंजी के साथ एक नोड होता है (हम वर्णों को कॉपी करने के लिए मानक strncpy फ़ंक्शन का उपयोग करेंगे), और इससे भी अधिक न्यूनतम विध्वंसक।

struct node //      { char* key; int len; node* link; node* next; node(char* x, int n) : len(n), link(0), next(0) { key = new char[n]; strncpy(key,x,n); } ~node() { delete[] key; } };

कुंजी खोज

पहला ऑपरेशन जिस पर हम विचार करेंगे, वह है उपसर्ग वृक्ष में एक नई लाइन डालने का ऑपरेशन। खोज का विचार मानक है। हम पेड़ की जड़ से चलते हैं। अगर जड़ खाली है, तो खोज असफल है। अन्यथा, वर्तमान पंक्ति x के साथ नोड में कुंजी कुंजी की तुलना करें। ऐसा करने के लिए, हम निम्नलिखित फ़ंक्शन का उपयोग करते हैं, जो किसी दिए गए लंबाई की दो लाइनों के सबसे बड़े सामान्य उपसर्ग की लंबाई की गणना करता है।

 int prefix(char* x, int n, char* key, int m) //      x  key { for( int k=0; k<n; k++ ) if( k==m || x[k]!=key[k] ) return k; return n; }

खोज के मामले में, हम तीन मामलों में रुचि रखते हैं:

सामान्य उपसर्ग खाली हो सकता है, फिर आपको इस नोड की छोटी बहन में खोज को फिर से जारी रखने की आवश्यकता है, अर्थात। अगले लिंक का पालन करें;
सामान्य उपसर्ग खोज स्ट्रिंग x के बराबर है - खोज सफल है, नोड पाया जाता है (यहां हम अनिवार्य रूप से इस तथ्य का उपयोग करते हैं कि स्ट्रिंग का अंत टर्मिनल प्रतीक की उपस्थिति के कारण केवल पेड़ की पत्ती में पाया जा सकता है);
सामान्य उपसर्ग कुंजी से मेल खाता है, लेकिन x से मेल नहीं खाता है - सीनियर चाइल्ड नोड के लिंक लिंक के माध्यम से पुनरावर्ती रूप से जाएं, इसे खोज के लिए पाए गए उपसर्ग के बिना स्ट्रिंग x पास करें।

यदि कोई सामान्य उपसर्ग है, लेकिन कुंजी से मेल नहीं खाता है, तो खोज भी असफल है।

 node* find(node* t, char* x, int n=0) //   x   t { if( !n ) n = strlen(x)+1; if( !t ) return 0; int k = prefix(x,n,t->key,t->len); if( k==0 ) return find(t->next,x,n); //    if( k==n ) return t; if( k==t->len ) return find(t->link,x+k,nk); //     return 0; }

स्ट्रिंग x की लंबाई n डिफ़ॉल्ट रूप से शून्य के बराबर है (और फिर यह स्पष्ट रूप से गणना की गई है), ताकि आप खोज फ़ंक्शन को कॉल कर सकें, केवल पेड़ की जड़ और खोज करने के लिए स्ट्रिंग निर्दिष्ट करें:

  ... node* p = find(t,"baca"); ...

निम्नलिखित आंकड़ा उपरोक्त वृक्ष में तीन लाइनें (एक सफल और दो नहीं तो) खोजने की प्रक्रिया को दर्शाता है।

ध्यान दें कि, यदि सफल होता है, तो खोज फ़ंक्शन उस पॉइंटर को उस पेड़ के पत्ते पर लौटाता है जहां खोज समाप्त हुई। यह इस नोड में है कि वांछित स्ट्रिंग से संबंधित सभी जानकारी स्थित होनी चाहिए।

मुख्य प्रविष्टि

एक नई कुंजी सम्मिलित करना (जैसे कि बाइनरी सर्च ट्री में) कुंजी खोजने के समान है। स्वाभाविक रूप से कुछ मतभेदों के साथ। सबसे पहले, एक खाली पेड़ के मामले में, आपको दिए गए कुंजी के साथ एक नोड (तुच्छ पेड़) बनाने की जरूरत है और इस नोड को एक पॉइंटर लौटाएं। दूसरे, यदि वर्तमान कुंजी और वर्तमान लाइन x के आम उपसर्ग की लंबाई शून्य से अधिक है, लेकिन कुंजी की लंबाई (अपर्याप्त खोज के दूसरे मामले) से कम है, तो हमें वर्तमान नोड को दो में विभाजित करने की आवश्यकता है, मूल उपसर्ग में पाया उपसर्ग छोड़कर और शेष पी को बच्चे के नोड पी में रखकर। कुंजी का हिस्सा। यह ऑपरेशन स्प्लिट फ़ंक्शन द्वारा कार्यान्वित किया जाता है। अलग होने के बाद, आपको पाया गया उपसर्ग के बिना नोड पी पर स्ट्रिंग एक्स को सम्मिलित करने की प्रक्रिया को जारी रखने की आवश्यकता है।

नोड विभाजन कोड:

 void split(node* t, int k) //   t  k-   { node* p = new node(t->key+k,t->len-k); p->link = t->link; t->link = p; char* a = new char[k]; strncpy(a,t->key,k); delete[] t->key; t->key = a; t->len = k; }

कोड डालें:

 node* insert(node* t, char* x, int n=0) //   x   t { if( !n ) n = strlen(x)+1; if( !t ) return new node(x,n); int k = prefix(x,n,t->key,t->len); if( k==0 ) t->next = insert(t->next,x,n); else if( k<n ) { if( k<t->len ) //   ? split(t,k); t->link = insert(t->link,x+k,nk); } return t; }

उपरोक्त पेड़ में कीजा $ और एब्सीडी $ डालने की एक मिसाल निम्न आकृति में दिखाई गई है।

ध्यान दें कि यदि निर्दिष्ट स्ट्रिंग x पहले से ही पेड़ में निहित है, तो कोई प्रविष्टि नहीं की जाएगी। इस दृष्टिकोण से, उपसर्ग वृक्ष एक सम्मानजनक सेट के रूप में व्यवहार करता है।

कुंजी निकालना

हमेशा की तरह, एक कुंजी को हटाना सबसे कठिन ऑपरेशन है। यद्यपि उपसर्ग वृक्ष के मामले में, सब कुछ इतना डरावना नहीं दिखता है। तथ्य यह है कि जब एक कुंजी को हटा दिया जाता है, तो केवल एक पत्ती नोड को हटा दिया जाता है, जिसे हटाने के लिए कुछ कुंजी का प्रत्यय होता है। पहले हम इस नोड को खोजते हैं, यदि खोज सफल होती है, तो हम इसे हटा देते हैं और इस नोड की छोटी बहन को एक सूचक लौटाते हैं (इसमें बेटियां नहीं हैं, यह एक सूची है, लेकिन बहनें हो सकती हैं)।

सिद्धांत रूप में, हटाने की प्रक्रिया पूरी हो सकती थी, लेकिन एक छोटी सी समस्या उत्पन्न होती है - एक नोड को हटाने के बाद, पेड़ में दो नोड्स टी और पी की एक श्रृंखला बन सकती है, जिसमें पहले नोड टी में एक एकल बच्चा नोड पी होता है। इसलिए, यदि हम पेड़ को संपीड़ित रूप में रखना चाहते हैं, तो हमें मर्ज ऑपरेशन करते हुए, इन दो नोड्स को एक में जोड़ना होगा।

मर्ज फ़ंक्शन का कोड काफी तुच्छ है - हम एक नई कुंजी बनाते हैं, नोड पी के नोड को फिर से निलंबित करते हैं, नोड पी को हटाते हैं:

 void join(node* t) //   t  t->link { node* p = t->link; char* a = new char[t->len+p->len]; strncpy(a,t->key,t->len); strncpy(a+t->len,p->key,p->len); delete[] t->key; t->key = a; t->len += p->len; t->link = p->link; delete p; }

वरिष्ठ नोड विलय के लिए जिम्मेदार है, क्योंकि युवा नोड को अपने माता-पिता के बारे में जानकारी नहीं है। विलय के मानदंड 1) लिंक द्वारा कुंजी को हटाने, और अगले द्वारा नहीं; 2) हटाने के बाद, नए लिंक का कोई अगला लिंक नहीं है (केवल एक बच्चा नोड है, इसलिए इसे वर्तमान के साथ विलय किया जा सकता है)।

 node* remove(node* t, char* x, int n=0) //   x   t { if( !n ) n = strlen(x)+1; if( !t ) return 0; int k = prefix(x,n,t->key,t->len); if( k==n ) //   { znode* p = t->next; delete t; return p; } if( k==0 ) t->next = remove(t->next, x, n); else if( k==t->len ) { t->link = remove(t->link, x+k, nk); if( t->link && !t->link->next ) //   t   ? join(t); } return t; }

विलय के बिना चाबी निकालने के उदाहरण:

और मर्ज के साथ:

प्रभावशीलता

ऑपरेटिंग समय और मेमोरी खपत के संदर्भ में एवीएल पेड़ों और उपसर्ग पेड़ों की तुलना में एक छोटा संख्यात्मक अध्ययन किया गया था। मेरे लिए परिणाम कुछ हद तक हतोत्साहित करने वाले थे (शायद किसी के हाथों की वक्रता प्रभावित हुई)। लेकिन क्रम में ... परीक्षण के लिए, लाइनों के 8 परीक्षण सेट बनाए गए थे। उनकी संक्षिप्त विशेषताओं को तालिका में सूचीबद्ध किया गया है।

सबसे पहले, एक दिए गए सेटों से एक पेड़ बनाने के लिए समय लिया गया था और एक ही सेट (यानी, केवल एक सफल खोज) से सभी कुंजियों के लिए इसमें खोज करने का समय था। निम्नलिखित ग्राफ एवीएल पेड़ और उपसर्ग पेड़ के निर्माण समय की तुलना दर्शाता है। यह देखा जा सकता है कि उपसर्ग वृक्ष थोड़ा तेज बनाया जा रहा है।

निम्नलिखित ग्राफ समान दो पेड़ों के लिए सभी उपलब्ध कुंजियों को खोजने में लगने वाले समय की तुलना दर्शाता है। और यहाँ सब कुछ के रूप में इरादा नहीं निकला। एक संतुलित बाइनरी ट्री औसतन वृक्ष के रूप में खोज करने में लगभग आधा समय खर्च करता है।

अंत में, यह देखना दिलचस्प था कि प्रति चरित्र मेमोरी लागत क्या है। परिणाम निम्नलिखित ग्राफ में दिखाए गए हैं।

औसतन, दोनों प्रकार के पेड़ों के लिए, प्रति वर्ण लगभग 2 बाइट्स प्राप्त होते हैं, जो मेरी राय में बहुत बुरा नहीं है। दिलचस्प बात यह है कि झंडे के मामले में, उपसर्ग वृक्ष एक चरित्र को एक बाइट (कई सामान्य लंबे उपसर्गों) से कम खर्च करता है।

इसलिए, एक स्पष्ट विजेता की पहचान नहीं की गई थी। पंक्तियों की संख्या के सापेक्ष इन दो पेड़ों के संचालन समय की तुलना की जानी चाहिए, लेकिन उपरोक्त रेखांकन से देखते हुए, किसी भी क्रांतिकारी से कुछ भी उम्मीद नहीं की जा सकती है। और, ज़ाहिर है, हैश तालिकाओं के साथ इन दो दृष्टिकोणों की तुलना करना दिलचस्प होगा ...

आपका ध्यान के लिए धन्यवाद!

मैं टिप्पणियों और टिप्पणियों के लिए आभारी रहूंगा!

संपीडित उपसर्ग पेड़