Как поисковые системы объединяют результаты инвертированного индекса?
Как поисковые системы объединяют результаты инвертированного индекса?
Например, если бы я искал инвертированные индексы слов "собака" и "летучая мышь", то было бы два огромных списка каждого документа, который содержал одно из этих двух слов.
Я сомневаюсь, что поисковая система идет через эти списки, один документ за один раз, и пытается найти соответствия с результатами списков. Что сделано алгоритмически для создания этого процесса слияния, сверкающего быстро?
2 ответа
Фактически поисковые системы действительно объединяют эти списки документов. Они получают хорошую производительность за счет использования других методов, наиболее важным из которых является сокращение: например, для каждого слова документы сохраняются в порядке уменьшения рейтинга страниц и для получения результатов, которые имеют шанс попасть в первые 10 (что приведет к быть показанным пользователю) вы можете пройти лишь небольшую часть списков собак и летучих мышей, скажем, первую тысячу. (и, конечно, есть кеширование, но это не связано с самим алгоритмом выполнения запроса)
Кроме того, в конце концов, нет того того большого количества документов о собаках и о летучих мышах: даже если их миллионы , при хорошей реализации он превращается в доли секунды.
P.S. Я работал в ведущей поисковой системе нашей страны, но не в самой системе нашего флагманского поискового продукта, но я поговорил с ее разработчиками и был удивлен, узнав, что алгоритмы выполнения запросов на самом деле довольно глупы: оказывается, что можно раздавить огромный объем вычислений в приемлемые временные рамки. Конечно, все очень оптимизировано, но здесь нет ни волшебства, ни чудес.
Поскольку инвертированные индексы упорядочены по 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);
}
}