使用Python构建树

Question

我正在尝试实现一个未经过排名的布尔检索.为此,我需要构造一个树并执行DFS来检索文档.我有叶节点,但我很难构建树.

例如:query = OR(AND(玛丽亚莎拉波娃)网球)

结果:

      OR
     |   |
     AND tennis
     | | 
  maria sharapova

我使用DFS遍历树并计算某些文档ID的布尔等价物,以从语料库中识别所需的文档.有人可以用python帮助我设计这个吗？我已解析查询并立即检索叶节点.

编辑:我是新来的,所以道歉是因为缺乏清晰度.我基本上试图建立一个非常天真的搜索引擎.因此,用户输入任何布尔查询,如:OR(AND(maria sharapova)tennis).我有一个维基百科文档集,根据您输入的查询显示给用户.

直到现在,我已经解析了查询以检索单个运算符(如OR,AND等).而且,个人搜索条件(玛丽亚,网球等).解析代码只是一个基本上将所有运算符和查询项组合为类型的函数.即(玛丽亚莎拉波娃),(网球),或,和.我以这种方式解析这个函数,以便自下而上创建一个树.现在,使用倒置列表作为网球,玛丽亚,莎拉波娃等相应的关键词,我使用倒排列表执行布尔运算,得到一定的"文档化".然后将此文档传递给API,然后API将检索正确的维基百科页面.

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

Answer 1

首先，如果您希望查询语言的精美语法支持许多运算符，范围查询或通配符，则一定要引用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.将“玛丽亚”推入堆栈。

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

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

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

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

步骤8。将网球推入堆栈。

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

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

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

代码的打印输出逐步显示了在处理当前查询项目（第一列），结果缓冲区的状态（第二列），堆栈中的项目（第三列）和立即数之前系统的外观。搜索结果（第4列）。