高效查询大型文档集中的短语

Question

在一次采访中，我收到了一个问题，要求我去为一个在线图书馆设计一个搜索引擎，里面有成千上万的文档和数百万单词的。最初，面试官只要求我搜索单个单词，澄清：

搜索确切的关键字(“溢出”返回true，而"overflo“not)

• Case-sensitivity可以忽略

)

我的回答是使用爬虫算法，在执行任何查询之前，遍历每个文档并创建一个查找表，该查找表存储文档中使用给定单词的信息。然后，一旦执行了查询，算法所要做的就是在查找表中找到单词，并返回使用该词的文档列表。

在第二步，他们问我，如果他们想搜索多个单词(不一定是连续的)，我会做什么?我的回答是对每个单词进行新的查询，并找到结果的交集。

最后，面试官问我，如果他们想让我在上查询连续单词或短语，我会怎么做？“堆栈溢出”)。此时，我的查找表失败了，因为在连续的单词之间没有联系，而且我无法在这种方法中找到解决方案。我如何处理这类查询？我最初的答案和设计有什么问题吗？我在网上搜索过，但没有发现任何值得注意的东西。

Answer 1

对于第二种情况，生成映射，使每个键都是一个单词，每个值都是一组具有以下属性的对象

{
  string document name : location/document_name,
  integer index : index, //location in document,
  toString : hash the object
}

然后，当您需要找到“堆栈溢出”的结果时

对于集合1中的所有元素，该值是否存在于set 2中，但使用item_index + 1进行了修改。

得到两个单词的结果，但只返回文档名。如果有三个单词，那么对两个单词执行相同的处理，但对于第三个单词，只检查单词1和单词2中的匹配项，并检查这些项是否存在于带有item_index +1的集合3中。