搜索引擎如何合并来自倒排索引的结果？
搜索引擎如何合并来自倒排索引的结果？
提问于 2010-03-07 03:15:19
搜索引擎如何合并来自倒排索引的结果？
例如，如果我搜索单词"dog“和"bat”的倒排索引，那么包含这两个单词之一的每个文档都会有两个巨大的列表。
我怀疑搜索引擎会遍历这些列表，一次一个文档，并试图找到与列表结果相匹配的内容。在算法上做了什么才能让这个合并过程更快呢？
回答 1
Stack Overflow用户
发布于 2010-03-07 06:24:17
由于倒排索引是按docId排序的，因此可以非常快地合并它们。如果其中一个单词从docId 23开始，第二个单词从docId 100001开始，您也可以立即快进到第一个列表中的docId 100001或更高版本。
由于典型的文档交叉点最多只有几百万个，因此可以非常快地对它们进行排序。我搜索了“狗猫”这两个很常见的词，结果只有5400万次点击。
排序1000万随机整数只花了2.3秒在我的Mac与单线程代码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);
}}
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2393781
复制相关文章
相似问题