使用逻辑运算符进行TRIE搜索

Question

我想使用TRIE (http://en.wikipedia.org/wiki/Trie)构建一个简单的搜索器但是我遇到了逻辑操作符(AND, OR, NOT)对我的尝试的问题。有没有办法给Trie添加一个运算符?

我想在下面搜索一些情况:

用3句话输入数据:

1. Tom is husband of Marry.
2. Tom is a teacher.
3. Tom is old friend of Marry.

查询:

(Tom AND Marry NOT friend). 
=> result is 1st sentence.

和2种方法来构建trie:

。从Query中构建tree，并在其上读取输入数据。

b。根据每个句子的输入数据构建trie。在tree上搜索每个查询词

谢谢。

Answer 1

需要一个数据结构来将关键字与一组句子关联起来。这可以是一个hashmap或一个trie。在您的示例中:

Tom => [1, 2, 3]
Mary => [1, 3]
husband => [1]
teacher => [2]
friend => [3]

该数据结构不包括逻辑操作符。您可以分别应用它们，例如:

"Tom" => lookup("Tom")
"Tom AND Mary" => intersection(lookup("Tom"), lookup("Mary"))
"Tom OR Mary" => union(lookup("Tom"), lookup("Mary"))
"Tom NOT Mary" => difference(lookup("Tom"), lookup("Mary"))

在这段伪代码中，只有lookup对树或用于存储单词的任何数据结构进行操作。其他函数操作集合，即存储项的值。

在你的设计中，你需要回答两个问题:我如何把单词和一组句子联系起来?我怎么表示一组句子呢?一个Trie只是第一个问题的答案。 当然，还有一个问题是如何解析查询以获得所需的逻辑函数。(您没有指定语言，但在实现trie之前，我会尝试使用您可用的标准数据结构。)