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