🧕🏾 🈚️ 🧦 जावास्क्रिप्ट में उपसर्ग पेड़ 🔨 🌶️ 🚩

यह कैसे लिखा गया

एक लंबी सर्दियों की शाम, मेरी पत्नी ने किताबी रोमांच खेला, और समय-समय पर मुझे उपलब्ध पत्रों से अधिक प्रामाणिक रूप से शब्दों की रचना के बारे में बताया। अक्षरों के एक सेट से शब्दों की रचना करने की अनुमति देने वाले पृष्ठों के इंटरनेट पर एक त्वरित खोज ने उन साइटों का एक गुच्छा दिया जो सर्वर साइड पर ऐसा करने की कोशिश करते हैं, और एक जो जावा क्लाइंट एप्लेट पर ऐसा करता है। सर्वर क्षमता के साथ शब्द बनाने वालों के पास या तो अक्षरों के सेट के आकार पर सीमा होती है (आमतौर पर, किसी कारण से, 8 पर), या गहराई से सोचें तो उन्हें सेट "abcdefghijklmnopqrstuvstxyxy" भेजा जाता है। हालाँकि, जावा एप्लेट में 12 अक्षरों की सीमा थी, यह चालाकी से काम करता था और लगभग उपयुक्त था (शब्दों की रचना के लिए खेल में 16 अक्षर प्रस्तुत किए जाते हैं)।

जावा एप्लेट के बगल में, 170 हजार अंग्रेजी शब्दों का एक शब्दकोश था। उससे कुछ समय पहले, मैंने एक साक्षात्कार किया और एक कार्य पूछा, जो उपसर्ग वृक्षों का उपयोग करके हल किया जाना था, फिर, मेरी शर्म की बात, उपसर्ग वृक्षों के बारे में सभी ज्ञान का, मेरे पास केवल मेरे सिर में एक नाम था और इसका उपयोग करने का कोई अनुभव नहीं था। इसलिए, इस अंतर को भरने का निर्णय लिया गया।

मैं C ++ में प्रोग्रामिंग करके पैसे कमाता हूं, इसलिए मूल संस्करण को C ++ में कंसोल एप्लिकेशन के रूप में लिखा गया था। इसने जल्दी और सही तरीके से काम किया, लेकिन मैं अपनी पत्नी को एक काले पाठ की खिड़की से डराना नहीं चाहता था, इसलिए इसे जावास्क्रिप्ट में फिर से लिखने का फैसला किया गया। मैं जावास्क्रिप्ट में उपसर्ग वृक्ष के निर्माण को लिखना नहीं चाहता था, इसलिए मैंने मौजूदा C ++ प्रोग्राम को जोड़ा जो कि JSON में पेड़ उतराई है। आउटपुट 40 मेगाबाइट (2 मेगाबाइट के मूल शब्दकोश से) की एक फ़ाइल थी, शायद इस समय यह शब्दकोश से एक पेड़ के निर्माण को हथौड़ा देने और लिखने के लायक था, लेकिन पहले खोज लिखने का फैसला किया, क्योंकि एक शब्दकोश है। सब कुछ ठीक रहा, लेकिन पेज लोड करने में हार्ड ड्राइव से 5-10 सेकंड लगे। जावास्क्रिप्ट में पेड़ के निर्माण को फिर से लिखा गया था, और परिणाम कुछ आश्चर्यजनक था: लोडिंग वास्तव में काफी तेज हो गया (यह उम्मीद की गई थी), आश्चर्य की बात यह थी कि इस मामले में ब्राउज़र मेमोरी की खपत तीन गुना कम थी। क्रोम टैब, जिसमें तैयार उपसर्ग पेड़ लोड किया गया था, में 150 मेगाबाइट मेमोरी का उपभोग किया गया था, और एक ही पेड़ को शब्दकोश से बनाया गया था, जिसका उपभोग केवल 50 किया गया था। परिणामस्वरूप, दोनों लोडिंग विकल्पों को तुलना के लिए अंतिम संस्करण में छोड़ दिया गया था। स्रोत BitBucket पर उपलब्ध हैं।

यह सब कैसे काम करता है

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

जैसा कि विकिपीडिया कहता है ( अंग्रेजी अधिक क्रिया है), एक उपसर्ग वृक्ष एक पेड़ है जो एक शब्दकोश से शब्दों के उपसर्गों (यानी, पहले कुछ अक्षर) को संग्रहीत करता है। पेड़ की संरचना ऐसी है कि जड़ के बाद पेड़ का प्रत्येक बाद का स्तर पिछले स्तर के सापेक्ष उपसर्ग के अगले अक्षर को संग्रहीत करता है। एक खाली उपसर्ग जिसमें कोई अक्षर नहीं है, उसे पेड़ की जड़ में जमा किया जाता है। यदि आप पेड़ की जड़ से एक पत्तीदार शिखर तक जाते हैं, और बाईं ओर से दाएं कोने की ओर से पत्र लिखते हैं, तो पथ के अंत में हमें शब्दकोश से कुछ शब्द मिलेगा। हालांकि, यह ध्यान देने योग्य है कि शब्द आवश्यक रूप से पत्ती के कोने पर समाप्त नहीं होते हैं, उदाहरण के लिए, शब्द BAD, CAB, CAD, DAB, AB, AD, BA का एक शब्द निम्नलिखित पेड़ द्वारा दर्शाया गया है:

तारांकन उन नोड्स को चिह्नित करते हैं जिन पर शब्द समाप्त होते हैं।

तो, कार्यक्रम में, पेड़ को रूट नोड के लिंक द्वारा दर्शाया जाता है, प्रत्येक नोड एक जावास्क्रिप्ट ऑब्जेक्ट है जिसमें data फ़ील्ड होते हैं, जिसमें नोड के अनुरूप पत्र संग्रहीत होता है; यदि शब्द इस नोड के साथ समाप्त होता है; और बाल पत्र के लिंक के साथ एक अक्षर के नाम के साथ कई फ़ील्ड्स जो कि संबंधित पत्र के लिए उपशीर्षक को स्टोर करता है। यानी JSON के रूप में आकृति से पेड़ A पहले स्तर का नोड इस तरह दिखता है:

 { "data" : "A", "terminator" : false, "B" : { "data" : "B", "terminator" : true }, "D" : { "data" : "D", "terminator" : true } }

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

 var trieRoot; function buildTrie(wordList) { trieRoot = { "data" : "", "terminator" : false }; for ( var i = 0; i < wordList.length; ++i ) { var word = wordList[i]; var letters = word.split(""); var curNode = trieRoot; for ( var j = 0; j < letters.length; ++j ) { if ( curNode[letters[j]] == undefined ) { curNode[letters[j]] = { "data" : letters[j], "terminator" : false }; } curNode = curNode[letters[j]]; } curNode.terminator = true; } }

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

 var letters = []; var used = []; var result = []; var words = {}; function findWords(node, depth) { if ( depth > 0 ) { result[depth - 1] = node.data; if ( node.terminator ) { var word = result.slice(0, depth).join(""); words[word] = 1; } } for ( var i = 0; i < letters.length; ++i ) { var child; if ( !used[i] && (child = node[letters[i]]) != undefined ) { used[i] = true; findWords(child, depth + 1); used[i] = false; } } }

letters सरणी में उपयोगकर्ता द्वारा दर्ज किए गए अक्षरों की एक सूची होती है, used सरणी वर्तमान स्थान में letters सरणी से सूचकांक के अनुरूप अक्षरों का उपयोग करने के लिए झंडे को संग्रहीत करती है। वर्तमान स्थान को result में संग्रहीत किया जाता है, words - पाया गया शब्द उस वस्तु में संग्रहीत किया जाता है, जिसका उपयोग उस मामले में दोहराव को बाहर करने के लिए एक साहचर्य सरणी के रूप में किया जाता है, जब उपयोगकर्ता एक अक्षर के कई दोहराव सेट करता है ("AAABBBCCCDDD")।

बाकी सभी कोड प्रसंस्करण इनपुट और आउटपुट के लिए समर्पित हैं, और पेड़ों के साथ खुद को बहुत कम करना है।

क्यों जरूरी है?

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

जावास्क्रिप्ट में उपसर्ग पेड़

यह कैसे लिखा गया

यह सब कैसे काम करता है

क्यों जरूरी है?

More articles: