data-structures
Trie (उपसर्ग वृक्ष / मूलांक वृक्ष)

तीनों का परिचय

क्या आपने कभी सोचा है कि सर्च इंजन कैसे काम करते हैं? Google केवल कुछ मिलीसेकंड में आपके सामने लाखों परिणामों को कैसे पंक्तिबद्ध करता है? हजारों मील की दूरी पर स्थित एक विशाल डेटाबेस आप से मिली जानकारी को कैसे खोजता है और उन्हें वापस आपके पास भेजता है? इसके पीछे का कारण केवल तेज इंटरनेट और सुपर-कंप्यूटर का उपयोग करके संभव नहीं है। खोज के कुछ एल्गोरिदम और डेटा-संरचना इसके पीछे काम करते हैं। उनमें से एक ट्राई है ।

ट्राइ , जिसे डिजिटल ट्री और कभी-कभी रेडिक्स ट्री या प्रीफिक्स ट्री भी कहा जाता है (जैसा कि वे उपसर्गों द्वारा खोजा जा सकता है), एक प्रकार का खोज ट्री है - एक ऑर्डर किया गया ट्री डेटा स्ट्रक्चर, जिसका उपयोग डायनामिक सेट या एसोसिएटिव एरे को स्टोर करने के लिए किया जाता है, जहाँ कुंजियाँ होती हैं। आमतौर पर तार। यह उन डेटा-संरचनाओं में से एक है जिन्हें आसानी से लागू किया जा सकता है। मान लीजिए कि आपके पास लाखों शब्दों का एक विशाल डेटाबेस है। आप इन सूचनाओं को संग्रहीत करने के लिए trie का उपयोग कर सकते हैं और इन शब्दों को खोजने की जटिलता केवल उस शब्द की लंबाई पर निर्भर करती है जिसे हम खोज रहे हैं। इसका मतलब है कि यह इस बात पर निर्भर नहीं करता है कि हमारा डेटाबेस कितना बड़ा है। क्या यह आश्चर्यजनक नहीं है?

मान लेते हैं कि हमारे पास इन शब्दों के साथ एक शब्दकोश है:

algo
algea
also
tom
to

हम इस शब्दकोश को स्मृति में इस तरह संग्रहीत करना चाहते हैं कि हम आसानी से उस शब्द का पता लगा सकें, जिसकी हम तलाश कर रहे हैं। विधियों में से एक शब्द को समसामयिक रूप से क्रमबद्ध करना शामिल होगा-वास्तविक जीवन के शब्दकोशों को शब्दों में कैसे संग्रहीत किया जाए। तब हम बाइनरी सर्च करके शब्द खोज सकते हैं । एक अन्य तरीका संक्षेप में प्रीफिक्स ट्री या ट्राइ का उपयोग कर रहा है। ' ट्राई ' शब्द री ट्राई वैल शब्द से आया है। यहाँ, उपसर्ग स्ट्रिंग के उपसर्ग को दर्शाता है जिसे इस तरह परिभाषित किया जा सकता है: वे सभी सबस्ट्रिंग जो एक स्ट्रिंग की शुरुआत से शुरू किए जा सकते हैं, उन्हें उपसर्ग कहा जाता है। उदाहरण के लिए: 'c', 'ca', 'cat' ये सभी 'string' कैट के उपसर्ग हैं।

अब आइये वापस ट्राइ करने के लिए। जैसा कि नाम से पता चलता है, हम एक पेड़ बनाएंगे। सबसे पहले, हमारे पास बस जड़ के साथ एक खाली पेड़ है:

हम 'एल्गो' शब्द डालेंगे । हम एक नया नोड बनाएंगे और इन दो नोड्स 'a' के बीच किनारे को नाम देंगे। नए नोड से हम 'l' नामक एक और बढ़त बनाएंगे और इसे दूसरे नोड से जोड़ेंगे। इस तरह, हम 'g' और 'o' के लिए दो नए किनारों का निर्माण करेंगे। ध्यान दें, हम नोड्स में कोई जानकारी संग्रहीत नहीं कर रहे हैं। अभी के लिए, हम केवल इन नोड्स से नए किनारों को बनाने पर विचार करेंगे। अब से, 'x' - एज-एक्स नामक एक किनारे को कॉल करते हैं

अब हम 'अल्जीया' शब्द जोड़ना चाहते हैं। हमें एक रूट -ए की आवश्यकता है, जो हमारे पास पहले से है। इसलिए हमें नई बढ़त जोड़ने की जरूरत नहीं है। इसी तरह, हमारे पास 'ए' से 'एल' और 'एल' से 'जी' तक बढ़त है। इसका मतलब है कि 'alg' पहले से ही trie में है । हम केवल इसके साथ किनारे-ई और किनारे जोड़ देंगे।

हम 'भी' शब्द जोड़ेंगे। हमारे पास जड़ से उपसर्ग 'अल' है। हम केवल इसके साथ 'ऐसा' जोड़ेंगे।

चलो 'टॉम' जोड़ें। इस बार, हम रूट से एक नया किनारा बनाते हैं क्योंकि हमारे पास पहले निर्मित कोई उपसर्ग नहीं है।

अब हमें 'को' कैसे जोड़ना चाहिए? 'to' पूरी तरह से 'tom' का उपसर्ग है, इसलिए हमें किसी भी किनारे को जोड़ने की आवश्यकता नहीं है। हम क्या कर सकते हैं, हम कुछ नोड्स में अंत-चिह्न डाल सकते हैं। हम उन नोड्स में अंतिम अंक डालेंगे जहां कम से कम एक शब्द पूरा हो गया है। ग्रीन सर्कल अंत-चिह्न को दर्शाता है। तीनों की तरह दिखेगा:

आप आसानी से समझ सकते हैं कि हमने अंत-अंक क्यों जोड़े। हम तीनों में संग्रहीत शब्दों को निर्धारित कर सकते हैं। अक्षर किनारों पर होंगे और नोड्स में अंत-चिह्न होंगे।

अब आप पूछ सकते हैं कि इस तरह के शब्दों को संग्रहीत करने का उद्देश्य क्या है? मान लीजिए, आपको शब्दकोश में शब्द 'एलिस' खोजने के लिए कहा गया है। आप ट्राय करेंगे। यदि कोई किनारे से जड़ है तो आप जांच करेंगे। फिर 'a' से जांचें, अगर कोई एज-एल है । उसके बाद, आपको कोई भी बढ़त नहीं मिलेगी, इसलिए आप इस निष्कर्ष पर पहुँच सकते हैं कि, शब्द alice शब्दकोष में मौजूद नहीं है।

यदि आपको शब्दकोश में शब्द 'अल्ग' खोजने के लिए कहा गया है, तो आप रूट-> ए , ए-> एल , एल-> जी को पार कर लेंगे, लेकिन आपको अंत में एक ग्रीन नोड नहीं मिलेगा। तो शब्द शब्दकोश में मौजूद नहीं है। यदि आप 'टॉम' की खोज करते हैं, तो आप एक हरे रंग के नोड में समाप्त हो जाएंगे, जिसका अर्थ है कि शब्द शब्दकोश में मौजूद है।

जटिलता:

किसी शब्द को किसी त्रि में खोजने के लिए आवश्यक अधिकतम कदम उस शब्द की लंबाई है जिसे हम खोज रहे हैं। जटिलता हे (लंबाई) है । सम्मिलन के लिए जटिलता समान है। तीनों को लागू करने के लिए आवश्यक मेमोरी की मात्रा कार्यान्वयन पर निर्भर करती है। हम एक अन्य उदाहरण में एक कार्यान्वयन देखेंगे जहां हम एक ट्राइ में 10 ⁶ अक्षर (शब्द, अक्षर नहीं) स्टोर कर सकते हैं।

तीनों का उपयोग:

• डालने, हटाने और शब्दकोश में एक शब्द के लिए खोज करने के लिए।
• यह जानने के लिए कि क्या एक स्ट्रिंग दूसरे स्ट्रिंग का उपसर्ग है।
• यह पता लगाने के लिए कि कितने तारों में एक सामान्य उपसर्ग है।
• हमारे फोन में संपर्क नामों का सुझाव हम उपसर्ग के आधार पर दर्ज करते हैं।
• दो तार के 'सबसे लंबे आम पदार्थ' का पता लगाना।
• 'सबसे लंबे पूर्वज' का उपयोग करते हुए दो शब्दों के लिए 'कॉमन प्रीफ़िक्स' की लंबाई का पता लगाना

ट्राई का क्रियान्वयन

इस उदाहरण को पढ़ने से पहले, यह अनुशंसा की जाती है कि आप पहले ट्राई का परिचय पढ़ें।

ट्राई को लागू करने के सबसे आसान तरीकों में से एक लिंक की गई सूची का उपयोग करना है।

नोड:

नोड्स से मिलकर बनेगा:

1. एंड-मार्क के लिए परिवर्तनीय।
2. अगले नोड को इंगित करें।

एंड-मार्क वैरिएबल बस निरूपित करेगा कि यह एंड-पॉइंट है या नहीं। पॉइंटर सरणी उन सभी संभावित किनारों को दर्शाएगा जो बनाए जा सकते हैं। अंग्रेजी वर्णमाला के लिए, सरणी का आकार 26 होगा, क्योंकि अधिकतम 26 किनारों को एक नोड से बनाया जा सकता है। बहुत शुरुआत में सूचक सरणी का प्रत्येक मान NULL होगा और अंतिम-चिह्न चर गलत होगा।

Node:
Boolean Endmark
Node *next[26]
Node()
    endmark = false
    for i from 0 to 25
        next[i] := NULL
    endfor
endNode

अगले [] सरणी में प्रत्येक तत्व दूसरे नोड को इंगित करता है। अगला [0] नोड शेयरिंग एज-ए की ओर इशारा करता है , अगला [1] नोड शेयरिंग एज-बी और इसी तरह से। हमने एंडमार्क को असत्य के रूप में आरंभ करने के लिए नोड के निर्माता को परिभाषित किया है और NULL को अगले [] सूचक सरणी के सभी मूल्यों में रखा है।

Trie बनाने के लिए, सबसे पहले हमें रूट को तत्काल करना होगा। फिर रूट से , हम जानकारी स्टोर करने के लिए अन्य नोड बनाएंगे।

प्रविष्टि:

Procedure Insert(S, root):    // s is the string that needs to be inserted in our dictionary
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        curr -> next[id] = Node()
    curr := curr -> next[id]
endfor
curr -> endmark = true

यहाँ हम az के साथ काम कर रहे हैं। इसलिए उनके ASCII मानों को 0-25 में बदलने के लिए, हम उनसे 'a' के ASCII मान को घटाते हैं। हम जांच करेंगे कि क्या वर्तमान नोड (वक्र) के हाथ में चरित्र के लिए बढ़त है। यदि ऐसा होता है, तो हम उस किनारे का उपयोग करते हुए अगले नोड पर जाते हैं, अगर ऐसा नहीं होता है तो हम एक नया नोड बनाते हैं। अंत में, हम एंडमार्क को सही में बदलते हैं।

खोज कर:

Procedure Search(S, root)      // S is the string we are searching
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        Return false
    curr := curr -> id
Return curr -> endmark

डालने के लिए प्रक्रिया समान है। अंत में, हम एंडमार्क वापस करते हैं। इसलिए यदि एंडमार्क सच है, तो इसका मतलब है कि शब्द शब्दकोश में मौजूद है। यदि यह गलत है, तो शब्द शब्दकोश में मौजूद नहीं है।

यह हमारा मुख्य कार्यान्वयन था। अब हम trie में कोई भी शब्द डाल सकते हैं और उसकी खोज कर सकते हैं।

विलोपन:

कभी-कभी हमें उन शब्दों को मिटाने की आवश्यकता होगी जो अब मेमोरी को बचाने के लिए उपयोग नहीं किए जाएंगे। इस उद्देश्य के लिए, हमें अप्रयुक्त शब्दों को हटाना होगा:

Procedure Delete(curr):       //curr represents the current node to be deleted
for i from 0 to 25
    if curr -> next[i] is not equal to NULL
        delete(curr -> next[i])
    delete(curr)               //free the memory the pointer is pointing to

इस समारोह, curr के सभी बच्चे नोड्स को जाता है उन्हें हटा देता है और उसके बाद curr स्मृति को मुक्त करने हटाया जाता है। अगर हम डिलीट (रूट) कहते हैं , तो यह पूरी ट्राइ को डिलीट कर देगा।

Trie भी सरणी का उपयोग कर कार्यान्वित किया जा सकता।