एक खोज इंजन के लिए एक सूचकांक का निर्माण

मेरे खोज इंजन लेखों की पूरी सामग्री और सूची यहां अपडेट की जाएगी।

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

इंडेक्सर मॉड्यूल से पिछले चरण डेटाफ्लो में, हमें डायरेक्ट इंडेक्स, लिंक जानकारी और पेज जानकारी के रूप में डेटा का एक टुकड़ा मिला। आमतौर पर यह मेरे लिए लगभग 200-300mb का होता है और इसमें लगभग 100 हजार पृष्ठ होते हैं। समय के साथ, मैंने एक ठोस फॉरवर्ड इंडेक्स को स्टोर करने की रणनीति को छोड़ दिया, और मैं इन सभी टुकड़ों + पूर्ण रिवर्स इंडेक्स को कई संस्करणों में संग्रहीत करता हूं ताकि मैं वापस रोल कर सकूं।

रिवर्स इंडेक्स डिवाइस सरल लगता है, हम फ़ाइल को स्टोर करते हैं, इसमें शुरुआत में प्रत्येक शब्द के लिए डेटा की शुरुआत के पते की एक तालिका होती है, फिर डेटा ही। यह मैंने अतिरंजित किया। तो यह उस प्रारूप का पता लगाता है जो खोज की गति को अनुकूलित करने के लिए सबसे अधिक फायदेमंद है - पृष्ठों के माध्यम से कूदने की आवश्यकता नहीं है - जैसा कि ब्रिन और पेज ने लिखा है, - 1 की तलाश, 1 पढ़ा। पुनर्निर्माण के प्रत्येक पुनरावृत्ति पर, मैं ऊपर वर्णित 20-50 टुकड़ों का उपयोग करता हूं, जाहिर है कि मैं उनसे सभी जानकारी को मेमोरी में लोड नहीं कर सकता, खासकर जब से यह सूचकांक के बारे में बहुत सारे सहायक डेटा को संग्रहीत करने के लिए उपयोगी है।

इसे हल करने के लिए और एफएस, डिस्क की सीमाओं से जुड़ी कई अन्य समस्याओं, पृष्ठों की कई सूचियों के समानांतर पहुंच, मैंने पूरे सूचकांक को 256 भागों में विभाजित किया। भाग I में WORD_ID% 256 = I शब्दों के लिए पृष्ठ सूचियाँ शामिल हैं
इस प्रकार, हम सूचकांक को लगभग समान भागों में विभाजित करते हैं। इसके अलावा, सूचकांक के पुनर्निर्माण के अगले पुनरावृत्ति पर सभी प्रसंस्करण केवल एक हिस्से के ढांचे के भीतर जुड़ा हुआ है। यानी 200-300 एमबी प्रत्येक के डेटाबेस के 20-50 टुकड़ों से, आपको केवल उस डेटा को डाउनलोड करने की आवश्यकता है जो संसाधित भाग में आने वाले शब्दों से जुड़ा हुआ है।

कुल: एक ही प्रक्रिया के 256 दोहराव:

1. हम शब्दों, पृष्ठों और यूआरएल पृष्ठों के बारे में सभी जानकारी डाउनलोड करने के बाद, डेटाबेस के इनपुट टुकड़ों से आवश्यक डेटा पढ़ते हैं। स्मृति में हम सॉर्ट करते हैं, हम सही संरचना की सूची बनाते हैं। हम पृष्ठ के बारे में जानकारी पैक करते हैं और इसकी आईडी, एचएएसएच और अन्य डेटा जोड़ते हैं।
2. पढ़ने के लिए "चरम संस्करण" के रिवर्स इंडेक्स को बैरल (मैंने इंडेक्स के टुकड़े कहा जाता है) को खोलें। हम लेखन के लिए सूचकांक के "नए संस्करण" का एक खाली बैरल खोलते हैं।
3. प्रत्येक शब्द के लिए, हम क्रम में 2 सूचियों को मर्ज करते हैं - एक निर्मित मेमोरी में सॉर्ट किया जाता है, और दूसरा पठनीय और पहले से ही एक फ़ाइल में सॉर्ट किया जाता है।
4. हम बंद करते हैं, हमें जो कुछ भी ज़रूरत है उसे जोड़ते हैं, आनन्दित होते हैं।

व्यवहार में, यह स्वाभाविक रूप से पता चला कि सूची जो पहले से ही सूचकांक के "पिछले संस्करण" में संग्रहीत है, नए पुनरावृत्ति के दौरान ही हल की जाती है जब पृष्ठों के बारे में कोई बाहरी जानकारी नहीं बदली गई है, लेकिन यह स्पष्ट रूप से ऐसा नहीं है।

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

मैं पृष्ठ पर शब्द (बैठकों की संख्या; बैठक की जगह - शीर्षक, मेटा, लिंक, पाठ, हाइलाइटिंग, स्वरूपण) के बारे में सामान्य जानकारी से निर्मित एक संयुक्त गुणांक का उपयोग करता है, विषयगत मैट्रिक्स से (अब तक वे बहुत खराब विकसित हैं); पीआर, शब्द के लिए शब्द पीआर से (मेरे पास हर शब्द के लिए पीआर भी है) और कुछ अन्य।

इसके अलावा, यह स्पष्ट है कि उच्च-आवृत्ति वाले प्रश्नों के साथ, भगवान को वास्तव में सूची में पहले 1000-2000 परिणामों की आवश्यकता है, हम सटीकता के लिए 262 हजार पर विचार करेंगे। क्योंकि सभी लोकप्रिय उत्तर स्पष्ट रूप से उनमें आ जाएंगे, और फिर आप उन पर एक रैंकिंग फ़ंक्शन चला सकते हैं जो उन्हें ठीक से सॉर्ट करेगा।
कम आवृत्ति वाले प्रश्नों के साथ, जब हमें वास्तव में 2-3-10 परिणामों की आवश्यकता होती है, तो सूचकांक का एक पूरा मार्ग अपरिहार्य है, हालांकि, पृष्ठों की सूची की कुल लंबाई शायद ही कभी होती है जब यह 100 हजार से अधिक होगी।

सामान्य तौर पर, अगर हम यह गारंटी दे सकते हैं कि सूची के पहले N हजार पृष्ठ शेष लाखों लोगों में से सबसे अच्छे होंगे, तो समस्या हल हो गई है, और यह गारंटी देने के लिए काफी सरल तरीके हैं। फिर प्रत्येक बैरल के सही पुनर्निर्माण के लिए:

1. हम याद करते हैं कि कौन से पीआरओ में बहुत कुछ बदला है
2. हम सूची से पहला एन हजार लोड करते हैं + पीआर मानदंड, पेज मेट्रिक्स और अन्य उत्तराधिकार के अनुसार शेष से थोड़ा सा
3. वहां हम इनपुट डेटा से वर्तमान बैरल के शब्दों के आवश्यक हिस्से को लोड करते हैं
4. केवल चयनित पृष्ठों के लिए हम पहले से ही सही, नए - पीआर, मैट्रिक्स के साथ सभी डेटा को अपडेट कर रहे हैं
5. लाखों के दसियों और पहले से ही स्मृति में, के बजाय सैकड़ों हजारों परिणाम छाँटें
6. हम सॉर्ट किए गए लिखते हैं, और बाकी केवल पिछले इंडेक्स से कॉपी किए गए डुप्लिकेट को हटाते हैं

ठीक है, निश्चित रूप से, आपके पास फ़ंक्शन "अपडेट पूरे" होना चाहिए जब एक महीने या छह महीने में एक बार, उदाहरण के लिए, सूचकांक पूरे सरलतम प्रत्यक्ष एल्गोरिथ्म को फिर से बनाया जाएगा।

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

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