algorithm - 包含不需要的单词的文档检索

Question

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

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

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

我可以通过预处理保持 O(n²) 数据结构并为 O(1) 时间检索准备好所有可能的答案来轻松做到这一点，但目标是构建这种数据结构在 O(n) 空间中，并使查询尽可能高效。

Answer 1

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

假设您的 n 是单词出现次数中语料库的总长度(而不是词汇量)，则可以在 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进行深度治疗。