python - 使用 Python 构建树

Question

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

例如:query = OR ( AND (maria sharapova) tennis)

结果:

      OR     |   |     AND tennis     | |   maria sharapova

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

编辑:我是新来的，很抱歉不清楚。我基本上是在尝试构建一个非常简单的搜索引擎。因此，用户输入任何 bool 查询，例如:OR ( AND (maria sharapova) tennis)。我有一个维基百科文档语料库，它根据您键入的查询显示给用户。

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

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

Answer 1

首先，如果您想要一种奇特的查询语言语法来支持许多运算符、范围查询或通配符，您绝对应该引用 Joran 指出的 lex/yacc 解决方案。

其次，从您发布的讲座幻灯片来看，我认为您更关心如何实现 bool 查询模型，而不是在 python 中构建树。那么您无需担心查询本身。假设查询的格式如下:

"OR ( AND ( maria sharapova ) tennis )"

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

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

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

让我们使用上面的例子做一个循序渐进的演示。您从左到右扫描查询。

第 1 步。将“或”运算符压入堆栈。

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

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

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

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

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

第 5 步。将“maria”插入堆栈。

第 6 步。将“莎拉波娃”插入堆栈。现在堆栈如下所示:

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

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

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

第 8 步。将网球插入堆栈。

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

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

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

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