Как поисковые системы объединяют результаты инвертированного индекса?
Например, если бы я искал инвертированные индексы слов «собака» и «летучая мышь», я бы нашел два огромных списка каждого документа, содержащего одно из двух слов.
Я сомневаюсь, что поисковая система просматривает эти списки, по одному документу за раз, и пытается найти совпадения с результатами списков. Что сделано алгоритмически, чтобы сделать этот процесс слияния быстрым?
На самом деле поисковые системы действительно объединяют эти списки документов. Они получают хорошую производительность за счет использования других приемов, важнейшим из которых является сокращение: например, для каждого слова документы хранятся в порядке убывания рейтинга страниц, и для получения результатов, имеющих шанс попасть в первую 10 (что быть показаны пользователю) вы можете просмотреть лишь небольшую часть списков собак и летучих мышей, скажем, первую тысячу. (и, конечно же, есть кеширование, но это не связано с самим алгоритмом выполнения запроса)
К тому же, ведь документов о собаках и о летучих мышах не так много: пусть и миллионы, но при хорошей реализации это доли секунды.
P.S. Я работал в ведущем поисковике нашей страны, правда, не в самом движке нашего флагманского поискового продукта, но общался с его разработчиками и был удивлен, узнав, что алгоритмы выполнения запросов на самом деле довольно тупые: оказывается, можно раздавить огромный объем вычислений в приемлемые сроки. Это все конечно очень оптимизировано, но никакой магии и чудес нет.
Поскольку инвертированные индексы упорядочены по docId, их можно очень быстро объединить. [если одно из слов начинается с docId 23, а второе — с docId 100001, вы также можете сразу перейти к docId 100001 или выше в первом списке. ]
Поскольку типичных пересечений документов не более нескольких миллионов, их можно очень быстро отсортировать по рангу. Я искал «dog cat» [очень распространенные 2 слова], который дал только 54 миллиона просмотров.
Сортировка 10 миллионов случайных целых чисел заняла на моем Mac всего 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);
}
}
