algorithm - 带有不需要的词的文档检索

Question

我正在构建一个数据结构来帮助索引总长度为 n 的 S 个文档的集合，这样它就支持以下查询:给定两个词 P1 和 P2，计算 包含的所有文档P1 但不是 P2。我希望答案完整(不要错过结果)。

我已经构建了一个广义后缀树，并挑选了每一个 sqrt(n)-th 叶子及其祖先(并删除了每一个单子(monad)节点)。对于每个内部节点 v，我预先计算针对节点 u 的查询的答案。

但是有了这个，如果查询包含出现在节点 v 和 u 的树中的单词，我可以在 O(1) 中得到答案，但是当单词不在节点之一中时我该怎么办我们选了？

我可以很容易地做到这一点，只需保留 O(n²) 数据结构进行预处理，并为 O(1) 时间检索准备好所有可能的答案，但目标是构建O(n) 空间中的这种数据结构，并使查询尽可能高效。

Answer 1

听起来像 inverted index仍然对你有用。它是单词到包含它们的有序文档列表的映射。这些文档需要有一个共同的、总的排序，它们就是按照这个顺序出现在它们的每个单词的桶中的。

假设您的 n 是词 occurrences 中语料库的总长度(而不是词汇表大小)，它可以在 O(n log n) 中构建 时间和线性空间。

给定 P1 和 P2，您进行两个单独的查询以分别获取包含这两个术语的文档。由于这两个列表共享相同的顺序，您可以执行类似线性合并的算法并仅选择那些包含 P1 但不包含 P2 的文档:

c1 <- cursor to first element of list of docs containing P1
c2 <- cursor to first element of list of docs containing P2
results <- [] # our return value

while c1 not exhausted
  if c2 exhausted or *c1 < *c2
    results.append(c1++)
  else if *c1 == *c2
    c1++
    c2++
  else # *c1 > *c2
    c2++

return results

注意循环的每一遍至少迭代一个游标；它以两个初始查询的大小总和的线性时间运行。由于只有 c1 游标中的内容进入 results，我们知道所有结果都包含 P1。

最后，请注意，我们始终只推进“滞后”游标:这(以及整个文档排序)保证如果一个文档出现在两个初始查询中，将会有一个循环迭代，其中两个游标都指向该文档。发生此迭代时，中间子句必然会启动，并且通过向前移动两个游标来跳过文档。因此，包含 P2 的文档必然不会添加到结果。

这个查询是一个叫做 bool 查询的通用类的例子；可以扩展此算法以涵盖大多数 bool 表达式。某些查询会破坏算法的效率(通过强制它遍历整个词汇空间)但基本上只要你不否定每个术语(即不要要求 not P1 and not P2) 你很好。参见 this进行深入治疗。