👩🏾‍🤝‍👩🏼 ☸️ ⛹🏿 बिटमैप इंडेक्स के साथ उपसर्ग पेड़ 👉🏽 🏊 🐜

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

अन्य कार्यान्वयन सूट नहीं किया, सबसे पहले, भस्म स्मृति पर। और किसी भी स्थिति में, उपसर्ग वृक्ष का एक और कार्यान्वयन अतिरेक नहीं होगा।

विचार शायद इस लेख से प्रेरित था, क्योंकि यह नोड में बाद के नोड्स के लिंक को अनुक्रमित करने के लिए बिटमैप इंडेक्स का उपयोग करने का निर्णय लिया गया था।

जाहिर है, एक नोड में लिंक की संख्या 63 से अधिक नहीं हो सकती है (प्रत्येक रजिस्टर में एक स्थान के साथ 10 अंक, 26 पत्र)। इसलिए, बिटमैप इंडेक्स के लिए, प्रत्येक नोड पर 64-बिट नंबर का उपयोग किया जाता है। किसी भी स्थिति में सेट बिट का अर्थ है, संबंधित प्रतीक और नोड (उपप्रकार) की उपस्थिति।

बिटमैप इंडेक्स में वितरण निम्नानुसार है: 0 से 9 तक की संख्या 0 से 9 बिट्स पर कब्जा, 10 से 35 बिट्स से एज़ अक्षर, 36 से 62 बिट्स तक एज़ेड अक्षर और 63 बिट्स पर एक जगह होती है। बिट संख्या प्राप्त करने के लिए, ASCII वर्ण कोड का उपयोग किया जाता है, एक निश्चित संख्या से घटाया जाता है। वर्णों की प्रत्येक श्रेणी के लिए, संख्या भिन्न होती है: संख्याओं के लिए 48 (ASCII कोड में अंकों की सीमा 48 से शुरू होती है), अक्षर a 87 के लिए (अक्षरों की श्रेणी az की शुरुआत माइनस 10 बिट्स से होती है जो पहले से ही 10 अंकों और इसी तरह से व्याप्त है)।

नीचे दी गई तालिका को दिखाया गया है।

चरित्र वितरण
प्रतीक	0	1	...	9	एक	ख	...	z	एक	बी	...	जेड	अंतरिक्ष बार
बिट संख्या	0	1	...	9	10	11	...	35	36	37	...	61	62

नीचे दिए गए कोड द्वारा नोड का प्रतिनिधित्व किया गया है:

type Trie struct { rw sync.RWMutex characters uint64 subTries []*Trie data interface{} }

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

इनपुट में प्रवेश करते समय, कुंजी प्रतीकात्मक रूप से पेड़ से गुजरती है, रूट नोड से शुरू होती है। अपने ASCII कोड से प्रत्येक वर्ण के लिए, बिट संख्या की गणना की जाती है, और इसके आधार पर सूचकांक को लिंक करने के लिए लिंक (सबट्री) के स्लाइस में गणना की जाती है। सूचकांक मूल्य वांछित बिट से पहले बिट्स की संख्या है। उदाहरण के लिए, हमारे पास ऐसा सूचकांक है: 00 ... 101। इसका मतलब यह है कि बिटमैप इंडेक्स में नंबर 0 और 2 हैं। फिर नंबर 0 के लिए इंडेक्स शून्य होगा, और नंबर 2 के लिए यह 1 होगा, यानी, सबट्रीज़ उप-सीरीज़ [0] और सबट्रीज़: 1 को जोड़ने के लिए 2 लिंक स्टोर करेगा। ।

वर्ण के लिए बिट संख्या प्राप्त करने के लिए कोड:

 func calcBitNum(char rune) (uint64, bool) { // Characters az use bit positions 10-35 if char > 96 && char < 123 { return uint64(char - 87), true } // Characters AZ use bit positions 36-61 if char > 64 && char < 91 { return uint64(char - 29), true } // digits 0-9 use bit positions 0-9 if char > 47 && char < 58 { return uint64(char - 48), true } // space uses 62 bit position if char == 32 { return 62, true } return 0, false }

वर्ण के लिए नोड इंडेक्स प्राप्त करने के लिए कोड:

 func (trie *Trie) getSubTreeIndex(bitNum uint64) int { shifted := trie.characters << (64 - bitNum) return bits.OnesCount64(shifted) }

दिए गए वर्ण के लिए नोड प्राप्त करने का कोड:

 func (trie *Trie) getSubTrie(char rune) (uint64, int, *Trie) { bitNum, _ := calcBitNum(char) subTrieId := trie.getSubTreeIndex(bitNum) // There is no subTrie under given character since the corresponding bit is zero if trie.characters&(1<<bitNum) == 0 { return bitNum, subTrieId, nil } return bitNum, subTrieId, trie.subTries[subTrieId] }

डालने

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

खोज

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

निष्कासन

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

परिणाम

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

उपसर्ग वृक्ष के उद्देश्य के आधार पर, इस समाधान का उपयोग एक शब्दकोश, खोज सूचकांक बनाने के लिए किया जा सकता है।

मैंने कोड डालने, खोज करने और हटाने का हवाला नहीं दिया, इसलिए लेख को अव्यवस्थित करने के लिए नहीं, इसके अलावा, स्रोत कोड जीथब पर उपलब्ध है।

बिटमैप इंडेक्स के साथ उपसर्ग पेड़

डालने

खोज

निष्कासन

परिणाम

More articles: