यह वास्तव में एक वास्तविक समस्या है जिस पर मैं काम कर रहा हूं, लेकिन सादगी के लिए, आइए दिखाएं कि मैं Google हूं।एकाधिक मानों के लिए इंडेक्स को खोजने के लिए एल्गोरिदम क्या है?
उपयोगकर्ता को "नैनोस्केल टुपपरवेयर" की खोज करने के लिए कहें। दोनों शब्दों के साथ बहुत सारे पेज नहीं हैं ... केवल 3k। लेकिन "नैनोस्केल" के साथ ~ 2 मिलियन पेज और "टुपपरवेयर" के साथ ~ 4 मिलियन हैं। फिर भी, Google ने 0.3 सेकंड में मेरे लिए 3k पाता है।
यह कैसे करता है?
एकमात्र एल्गोरिदम मुझे पता है कि "नैनोस्केल" के लिए दस्तावेज़ प्राप्त करना, "टुपपरवेयर" के लिए दस्तावेज़ प्राप्त करना है, और फिर सूची विलय करना है। लेकिन वह ओ (एन + एम), या ओ (5,000,000) है जो थोड़ा धीमा लगता है। विशेष रूप से अगर मैं इसे एक उबेर-तेज़ क्लस्टर के बजाय डेस्कटॉप पर चला रहा हूं।
तो क्या वास्तव में Google क्या कर रहा है, और उनकी गति ज्यादातर इस तथ्य के कारण है कि वे अपने बड़े पैमाने पर वितरित क्लस्टर पर इस महंगे गणना को चला रहे हैं?
या क्या कोई बेहतर एल्गोरिदम है जिसे मुझे पता नहीं है? विकिपीडिया और Google मेरे लिए कुछ भी नहीं बदल रहे हैं।
संपादित करें:
के बाद से लोगों को मेरे सवाल का गूगल पहलू पर ध्यान केंद्रित करने लगते हैं, मुझे लगता है मैं वास्तविक संदर्भ में यह को फिर से करेंगे।
मेरे पास कुंजी/मूल्य जोड़े के रूप में लागू कई बहुत बड़ी (लाखों आइटम) इंडेक्स हैं। कुंजी सरल शब्द हैं, मूल्य दस्तावेज़ों के समूह हैं। एक आम उपयोग मामला विभिन्न इंडेक्स पर कई खोजों पर परिणामों के छेड़छाड़ को प्राप्त करना है: दर्द बिंदु दस्तावेज़ सेट के चौराहे को प्राप्त कर रहा है।
मैं अपनी अनुक्रमणिका को फिर से कार्यान्वित कर सकता हूं हालांकि मैं चाहता हूं - यह ज्यादातर इस समय एक अकादमिक परियोजना है।
शायद इसमें बहुत से चालाक कैशिंग शामिल हैं ... –
मुझे यकीन है कि एक लाख अन्य चालाक अनुकूलन के साथ भी है। लेकिन मुझे सच में संदेह है कि वे मेरी खोज के * परिणाम * को कैश कर रहे हैं, इसलिए मैं अभी भी उत्सुक हूं - वास्तव में परिणाम सूची प्राप्त करने के लिए वे किस एल्गोरिदम का उपयोग कर रहे हैं? – levand
Google के पास सूचकांक हैं। सूचकांक के बहुत सारे। संभवतः यह क्या करता है 'नैनोस्केल' शब्द के लिए प्री-जेनरेटेड इंडेक्स को पकड़ लेता है, और उसके बाद सूचीबद्ध प्रत्येक पृष्ठ के लिए, उस पृष्ठ के सभी शब्दों की पूर्व-जेनरेट की गई क्रमबद्ध सूची को देखें, यह देखने के लिए कि 'टुपपरवेयर' होता है या नहीं। वह हिस्सा बड़े पैमाने पर वितरित किया जाएगा। यह परिणाम कैश करेगा, ताकि अगली बार जब आप एक ही शब्द खोज सकें तो यह केवल पूर्व-जनरेटेड "नैनोस्केल टुपपरवेयर" अनुक्रमणिका को पकड़ लेगा। निश्चित रूप से Google ने आवृत्ति के अनुसार शीर्ष 10,000 अंग्रेजी शब्दों में से किसी भी 2 के संभावित संयोजन के लिए प्री-जेनरेट किए गए इंडेक्स हैं: यह "केवल" पृष्ठों की 100 मिलियन सूचियां हैं। –