20

搜索引擎如何合并倒排索引的结果？

例如，如果我搜索单词“dog”和“bat”的倒排索引，每个包含这两个单词之一的文档都会有两个巨大的列表。

我怀疑搜索引擎是否会遍历这些列表，一次一个文档，并尝试查找与列表结果匹配的内容。在算法上做了什么来使这个合并过程变得非常快？

4

2 回答 2

10

实际上搜索引擎确实合并了这些文档列表。它们通过使用其他技术获得了良好的性能，其中最重要的是剪枝：例如，对于每个单词，文档按 pagerank 递减的顺序存储，并获得有机会进入前 10 个的结果（这将显示给用户）你可能只遍历狗和蝙蝠列表的一小部分，比如前一千个。（当然，还有缓存，但这与查询执行算法无关）

此外，毕竟关于狗和蝙蝠的文件并不多：即使是数百万，也可以在执行良好的情况下变成分秒。

PS 我曾在我们国家领先的搜索引擎工作，但不是在我们的旗舰搜索产品的引擎中工作，但我与它的开发人员交谈并惊讶地发现查询执行算法实际上相当愚蠢：事实证明，一个可能会被挤压在可接受的时间范围内进行大量计算。当然，这一切都非常优化，但没有魔法也没有奇迹。

于 2010-03-06T22:11:27.357 回答
7

由于倒排索引是按 docId 排序的，因此它们可以非常快速地合并。[如果其中一个单词从 docId 23 开始，第二个单词从 docId 100001 开始，您也可以立即快进到第一个列表中的 docId 100001 或更高版本。]

由于典型的文档交叉点最多为几百万，因此可以非常快速地对它们进行排序。我搜索了“dog cat”[非常常见的 2 个词]，它只返回了 5400 万次点击。

在我的 Mac 中，使用单线程代码对 10 万个随机整数进行排序仅需 2.3 秒 [100 万个需要 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);
 }

}

于 2010-03-06T22:24:17.127 回答