खोज इंजन एक उलटा इंडेक्स से परिणाम कैसे विलय करते हैं?

Question

खोज इंजन एक उलटा इंडेक्स से परिणाम कैसे विलय करते हैं?

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

मुझे संदेह है कि एक खोज इंजन इन सूचियों के माध्यम से चलता है, एक समय में एक दस्तावेज़, और सूचियों के परिणामों के साथ मिलान खोजने का प्रयास करता है। इस विलय प्रक्रिया को तेजी से तेज करने के लिए एल्गोरिदमिक रूप से क्या किया जाता है?

Answer 1

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

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

---

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

Answer 2

चूंकि उलटा सूचकांक docId द्वारा आदेश दिया जाता है, इसलिए उन्हें बहुत तेजी से विलय किया जा सकता है। [यदि डॉकआईड 100001 में दूसरा शब्द डॉकआईड 23 और दूसरे पर शुरू होता है, तो आप तुरंत पहले सूची में 100001 या उससे अधिक के लिए आगे बढ़ सकते हैं। ]

चूंकि सामान्य दस्तावेज़ चौराहे लगभग कुछ मिलियन हैं, इसलिए उन्हें रैंक के लिए क्रमशः क्रमबद्ध किया जा सकता है। मैंने 'कुत्ते बिल्ली' की खोज की [बहुत आम 2 शब्द] जो केवल 54 मिलियन हिट लौटे।

10 मिलियन यादृच्छिक पूर्णांकों के छंटनी ने मेरे मैक में केवल 2.3 सेकंड को सिंगल थ्रेडेड कोड के साथ लिया [1 मिलियन 206 एमएस ले लिया!] और चूंकि हमें आमतौर पर केवल शीर्ष 10 चुनने की आवश्यकता नहीं है, यहां तक ​​कि पूर्ण प्रकार की आवश्यकता भी नहीं है।

कोई कोड है अगर कोई कोड लिखने के लिए बहुत आलसी और बहुत आलसी कोशिश करना चाहता है तो कोड है!

import java.lang.*; 
import java.math.*; 
import java.util.*; 

public class SortTest { 
    public static void main(String[] args) { 
    int count = Integer.parseInt(args[0]); 

Random random = new Random(); 
int[] values = new int[count]; 
int[] bogusValues = new int[100000]; //screw cache 
    for(int i = 0; i < values.length;++i) { 
    values[i] = random.nextInt(count); 
} 
for(int i = 0; i < bogusValues.length;++i) { 
    bogusValues[i] = random.nextInt(count); 
} 
long start = System.currentTimeMillis(); 
System.out.println(start); 
     Arrays.sort(values); 
System.out.println(System.currentTimeMillis()); 
System.out.println(System.currentTimeMillis()-start); 
    Arrays.sort(bogusValues); 
} 

}