索引许多文档以启用支持和/或操作的查询

所需的基本数据结构是 inverted index . 这会将每个单词映射到包含它的文档集。让我们说 lookup lookup: W -> Pos(D) W 是一组词, D Pos(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 表达式被转换为联合表达式,所有表达式都是递归计算的。我敢肯定,如果你盯着上面看足够长的时间,你会看到它的美丽:)

你可以代表每一组 返回)作为哈希集。如果您使用Java,还可以使用guava的lazy union 和 intersection

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

这就是我目前找到的解决方案: 1) keyMap,HashMap,其中key是关键字,value是文档的LinkedList。 2) docMap,HashMap,其中键是文档id,值是一组关键字

现在,对于这样一个查询(“key1和key2”),我将:

LinkedList docs = keyMap.get(key1);
for each (HashSet doc:docs)
     if(doc.contains(keys))
            result.add(doc);
return result

有没有更好的办法? 三个关键词怎么样?

Google Desktop

有很多文件,像 Lucene 变得非常有吸引力。

正如@Wrikken所说,使用lucene。

由于您对使用的算法有很多感兴趣,您可以找到一个起点 here 以及更多信息 here .