6

我正在尝试实现未排序的布尔检索。为此，我需要构建一棵树并执行 DFS 来检索文档。我有叶子节点，但我很难构建树。

例如：查询 = OR ( AND (maria sharapova) 网球)

结果：

      或者
     | |
     和网球
     | |
  玛丽亚莎拉波娃

我使用 DFS 遍历树并计算某些文档 ID 的布尔等效值，以从语料库中识别所需的文档。有人可以帮助我使用 python 设计这个吗？我现在已经解析了查询并检索了叶节点。

编辑：我是新来的，所以对缺乏清晰度表示歉意。我基本上是在尝试构建一个非常幼稚的搜索引擎。因此，用户输入任何布尔查询，例如：OR（AND (maria sharapova) 网球）。我有一个维基百科文档语料库，根据您键入的查询显示给用户。

到目前为止，我已经解析了查询以检索单个运算符（如 OR、AND 等）。并且，个人搜索词（玛丽亚、网球等）。解析代码只是一个函数，它基本上将所有运算符和查询术语按类型分组。即（玛丽亚莎拉波娃），（网球），或，和。我以这种方式解析了这个函数，以便自下而上地创建一个树。现在，对相应的关键字（如网球、玛丽亚、莎拉波娃等）使用倒排列表，我对倒排列表执行布尔运算以获得某个“documentid”。然后将此 documentid 传递给 API，然后该 API 将检索正确的维基百科页面。

只是为了更详细地解释该主题，请参阅此文档以获取有关我手头问题的更多信息： http ://www.ccs.neu.edu/home/jaa/CSG339.06F/Lectures/boolean.pdf

4

2 回答 2

5

首先，如果您希望查询语言的精美语法支持许多运算符、范围查询或通配符，您绝对应该参考 Joran 指出的 lex/yacc 解决方案。

其次，从您发布的演讲幻灯片中，我认为您更关心如何实现布尔查询模型，而不是在 python 中构建树。那么你就不需要担心查询本身了。假设查询格式正确，如下所示：

"OR ( AND ( maria sharapova ) tennis )"

也就是说，运算符（AND/OR）和关键字/括号之间有空格。然后您只需要两个堆栈（不使用树数据结构上的 DFS）来解析查询并从中获取组合的搜索结果。

第一个堆栈包含运算符 (AND/OR) 和操作数（例如，maria、网球）。您将括号视为打开/关闭条件以处理堆栈顶部的当前操作数。只有在看到右括号时才处理搜索操作)。

第二个堆栈保存当前的搜索结果。

让我们使用上面的示例进行逐步演示。您从左到右扫描查询。

第 1 步。您将“OR”运算符推入堆栈。

+               +
+               +
+    OR         +
+ + + + + + + + +

第 2 步。您会看到一个左括号(，请跳过它。

第 3 步。您将“AND”运算符推入堆栈。现在堆栈如下所示：

+               +
+    AND        +
+    OR         +
+ + + + + + + + +

第 4 步。您跳过另一个(.

第 5 步。您将“maria”推送到您的堆栈中。

第 6 步。您将“sharapova”推入堆栈。现在堆栈如下所示：

+   sharapova   +
+    maria      +
+    AND        +
+    OR         +
+ + + + + + + + +

第 7 步。您会看到一个右括号)。现在是时候进行第一次手术了。您弹出堆栈顶部的所有项目，直到看到一个运算符。弹出操作符以获取当前操作符。现在您分别处理“sharapova”和“maria”的搜索，并使用运算符“AND”组合搜索结果。假设对于“玛丽亚”，您会得到 3 个文档 ID：[1, 2, 3]. 对于“莎拉波娃”，您将获得另外 5 个文档 ID [2, 3, 8, 9, 10]：. 将结果与“AND”组合后，您将[2,3]在
第二个堆栈中保存当前搜索结果。当前情况如下所示：右侧是结果缓冲区。

+               +           +         +
+               +           +         +
+               +           +         +
+    OR         +           +  [2,3]  +
+ + + + + + + + +           + + + + + +

第 8 步。您将网球推入堆栈。

+               +           +         +
+               +           +         +
+    tennis     +           +         +
+    OR         +           +  [2,3]  +
+ + + + + + + + +           + + + + + +

第 9 步。您会看到另一个右括号)。同样，您弹出堆栈顶部的所有项目，直到您看到“或”。您开始使用“网球”进行搜索，并假设您得到了结果 doc ids: [3, 5, 7]。此时，您使用运算符“OR”将此结果与缓冲区中的先前结果组合，以便最终获得 doc ids: [2,3,5,7]。

我的示例代码在这里。len(word)注意我通过随机采样整数来模拟搜索和返回文档 ID 。

代码的打印输出逐步显示了系统在处理当前查询项（第 1 列）之前的样子、结果缓冲区的状态（第 2 列）、堆栈中的项（第 3 列）和立即搜索结果（第 4 列）。

于 2012-10-24T20:25:15.033 回答
2

列表列表是在 Python 中表示树的一种自然方式（无需创建类）：

>>> query = ['OR', ['AND', 'maria', 'sharapova'], 'tennis']
于 2012-09-08T06:32:19.397 回答