2

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

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

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

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

4

1 回答 1

2

听起来倒排索引对您仍然有用。它是将单词映射到包含它们的有序文档列表上。文档需要有一个共同的、总的顺序，并且就是按照它们出现在每个单词桶中的顺序。

假设你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必然的文档不会被添加到results.

此查询是称为布尔查询的通用类的示例；可以扩展此算法以覆盖大多数布尔表达式。某些查询破坏了算法的效率（通过强制它遍历整个词汇空间），但基本上只要您不否定每个术语（即不要求not P1 and not P2），您就可以了。请参阅此进行深入治疗。

于 2012-06-20T07:04:41.310 回答