Как поисковые системы объединяют результаты инвертированного индекса?

Question

Как поисковые системы объединяют результаты инвертированного индекса?

Например, если бы я искал инвертированные индексы слов «собака» и «летучая мышь», было бы два огромных списка каждого документа, содержащего одно из двух слов.

Я сомневаюсь, что поисковая система просматривает эти списки, по одному документу за раз, и пытается найти совпадения с результатами списков. Что сделано алгоритмически, чтобы этот процесс слияния быстро вспыхнул?

Answer 1

На самом деле поисковые системы do объединить эти списки документов. Они получают хорошую производительность, используя другие методы, наиболее важным из которых является обрезка: например, для каждого слова документы хранятся в порядке убывания страницы и получать результаты, которые имеют шанс попасть в первые 10 (что будет показать пользователю), вы можете пересечь только небольшую часть списков собак и летучих мышей, скажем, первую тысячу. (И, конечно же, есть кэширование, но это не связано с алгоритмом выполнения самого запроса)

Кроме того, в конце концов, не что много документов о собаках и о летучих мышах: даже если это миллионы, то получается в разделенные секунды с хорошей реализацией.

---

P.S. Однако я работал в ведущей поисковой системе нашей страны, но не в самом двигателе нашего флагманского поискового продукта, но я говорил со своими разработчиками и с удивлением узнал, что алгоритмы выполнения запросов на самом деле довольно глупые: оказывается, что можно скворовать огромный количество вычислений в допустимые временные рамки. Конечно, все это очень оптимизировано, но нет никакой магии и чудес.

Answer 2

Поскольку инвертированные индексы упорядочены docId, их можно очень быстро слить. [Если одно из слов начинается с docId 23 и второе - в docId 100001, вы можете сразу же переслать вперед в docId 100001 или выше в первом списке. ]

Поскольку типичные пересечения документов составляют почти несколько миллионов, они могут быть отсортированы по рангу очень быстро. Я искал «собачий кот» [очень распространенные слова 2], который вернул всего 54 миллиона хитов.

Сортировка 10 миллионных случайных целых чисел занимает всего 2,3 секунды на моем Mac с однопоточным кодом [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); 
} 

}