database - 索引许多文档以启用支持 AND/OR 操作的查询

Question

我们有很多由单词组成的文档。 索引文档的最合适方法是什么。 搜索查询应支持 AND/OR 运算。

查询运行时应该尽可能高效。 请描述索引所需的空间。

文档仅包含单词(不包括 AND/OR)，查询包含单词和关键字 AND/OR。

编辑如果我只允许 2 个关键字和一个操作，算法会是什么 (例如 w1 和 w2)

Answer 1

所需的基本数据结构是 inverted index .这会将每个单词映射到包含它的文档集。假设 lookup 是一个从单词到文档集的函数:lookup: W -> Pos(D)(其中 W 是单词集, D 文档集, Pos(D) D 的幂集).

假设您有以下形式的查询表达式:

Expr ::= Word | AndExpression | OrExpression
AndExpression ::= Expr 'AND' Expr
OrExpression ::= Expr 'OR' Expr

所以你得到一个代表你的查询的抽象语法树。这是一棵具有以下类型节点的树:

abstract class Expression { }

class Word extends Expression {
  String word
}

class AndExpression extends Expression {
  Expression left
  Expression right
}

class OrExpression extends Expression {
  Expression left
  Expression right
}

例如，foo AND (bar OR baz) 将被翻译成这棵树:

       AndExpression
      /             \
     /               \
  Word('foo')         OrExpression
                    /             \
                   /               \
             Word('bar')       Word('baz')

要评估这棵树，请遵循以下用伪代码表示的简单规则:

Set<Document> evaluate(Expr e) {
   if (e is Word) 
      return lookup(e.word)
   else if (e is AndExpression) 
      return intersection(evaluate(e.left), evaluate(e.right))
   else if (e is OrExpression) 
      return union(evaluate(e.left), evaluate(e.right))

   //otherwise, throw assertion error: no other case remaining
}

//implemented by the inverted index, not shown
Set<Document> lookup(String word)

因此，AND 表达式基本上被翻译成集合交集，而 OR 表达式被翻译成联合表达式，所有这些都是递归计算的。我敢肯定，如果你盯着上面的时间足够长，你就会看到它的美丽:)

您可以将每个集合(lookup 返回的)表示为一个 HashSet。如果你使用Java，你也可以使用 Guava 的懒惰union和 intersection实现，这应该很有趣(特别是如果你研究代码或发挥你的想象力来了解“懒惰”在这种情况下的真正含义)。

尽管如此，据我所知，交集很少通过相交哈希表来计算 - 相反，通常会发生以下情况:假设有 3 个集合要相交，我们选择一个(最好是最小的)并分配一个计数器(等于 1) 到每个文件。然后我们迭代其他集合，增加每个找到的文档的计数器。最后，我们报告每个文档其计数器变为 3(这意味着该文档出现在所有集合中，因此存在于它们的交集中)。