Python 查询处理和布尔搜索

Question

我是一名有用的助手，可以为您翻译文本。

我有一个反向索引（作为字典），我想要将布尔搜索查询作为输入进行处理并产生结果。

反向索引如下所示：

{
Test : { FileName1: [213, 1889, 27564], FileName2: [133, 9992866, 27272781, 78676818], FileName3: [9211] },
Try : { FileName4 ...
.....
}

现在，给定一个布尔搜索查询，我需要返回结果。

示例：

布尔搜索查询：test AND try 结果应该是所有包含单词test和try的文档。

布尔搜索查询：test OR try 结果应该是所有包含test或try的文档。

布尔搜索查询：test AND NOT try 结果应该是所有包含test但不包含try的文档。

我该如何构建这个搜索引擎来处理给定的布尔搜索查询？

提前感谢！

- Muenze

---

你能在搜索部分更具体一些吗？测试和尝试将在哪里进行搜索？ - Tim Givois

在倒排索引中，对于第一个例子，程序必须定位“test”的倒排列表和“try”的倒排列表，然后取它们的交集。 - Muenze

这在 SQL 中完成会更自然。然而，关键问题是你希望如何构建查询？AND/OR 组合从哪里来？ - Gnudiff

@Gnudiff，我刚看到你的评论。布尔运算符是由用户输入的。假设我正在寻找包含单词“Project AND Gutenberg”的文档。因此查询是project AND Gutenberg。 - Muenze

是的，我想获取与输入查询匹配的文件名。因此，如果输入的查询是“Test AND NOT Gnudiff”，结果应该是包含单词test但不含Gnudiff的文档的文件名。 - Muenze

Answer 1

编辑：我保留了我的答案的第一部分，因为如果这不是一项学校任务，那么在我看来，这仍然是一种更好的方法。我用更新替换了答案的第二部分以匹配 OP 的问题。

您似乎想要做的是创建一个查询字符串解析器，它将读取查询字符串并将其转换为一系列 AND/OR/NOT 组合以返回正确的键。

有两种方法可以实现这一点。

1. 根据您所写的需求，迄今为止最简单的解决方案是将数据加载到任何 SQL 数据库中（例如 SQLite，它不需要完整运行的 SQL 服务器），将字典键加载为单独的字段（如果您不关心正常形式等，则您的其余数据可以全部位于另一个字段中），并将传入的查询转换为 SQL，大致如下：

SQL 表至少具有以下内容：

CREATE TABLE my_data(
dictkey text,
data text);

---

python_query="foo OR bar AND NOT gazonk"
sql_keywords=["AND","NOT","OR"]
sql_query=[]
for word in python_query.split(" "):
    if word in sql_keywords:
        sql_query+=[ word ]
    else:
        sql_query+=["dictkey='%s'" % word]

real_sql_query=" ".join(sql_query)

这需要一些转义和控制检查以防止 SQL 注入和特殊字符，但通常它只会将您的查询转换为 SQL，当针对 SQL 数据库运行时，将返回键（可能还有数据）以进行进一步处理。

2. 现在是纯 Python 版本。

您需要做的是分析您获得的字符串并将逻辑应用于您现有的 Python 数据。

将字符串分析为特定组件（及其交互）的过程称为 解析。如果您实际上想要构建自己的完整解析器，那么会有 Python 模块可用，但是对于学校作业，我希望您被要求构建自己的解析器。

根据您的描述，查询可以用准 BNF 形式 表达为：

(<[NOT] word> <AND|OR>)...

既然您说优先级并不重要，那么您可以采用逐字逐句解析的简单方式。

接下来，您需要将关键词与文件名匹配，而如其他答案中所提到的，最简单的方法是使用集合。

因此，大致可以按以下方式进行：

import re

query="foo OR bar AND NOT gazonk"

result_set=set()
operation=None

for word in re.split(" +(AND|OR) +",query):
    #word will be in ['foo', 'OR', 'bar', 'AND', 'NOT gazonk']

    inverted=False # for "NOT word" operations

    if word in ['AND','OR']:
        operation=word
        continue

    if word.find('NOT ') == 0:
        if operation is 'OR':
        # generally "OR NOT" operation does not make sense, but if it does in your case, you 
        # should update this if() accordingly
            continue

        inverted=True
        # the word is inverted!
        realword=word[4:]
    else:
        realword=word

    if operation is not None:
        # now we need to match the key and the filenames it contains:
        current_set=set(inverted_index[realword].keys())

        if operation is 'AND':
            if inverted is True:
                result_set -= current_set
            else:
                result_set &= current_set
        elif operation is 'OR':
            result_set |= current_set

    operation=None

print result_set

请注意，这不是一个完整的解决方案（例如它没有包括处理查询的第一个术语，并且它要求布尔运算符为大写），也没有经过测试。但是，它应该能够实现展示如何处理它的主要目的。做更多的事情将会为您编写课程作业，这对您来说是不利的，因为您应该学习如何做它以便理解它。随时询问以获得澄清。

- Gnudiff

---

它是用Python编写的，而不是SQL。 - Tim Givois

那又怎样？我难道不能提出不同的方法吗？与将数据移动到SQL相比，创建解析器并不是那么琐碎的事情。 - Gnudiff

嗨，Gnudiff。感谢你的到来。实际上，我需要使用Python解决这个问题。关于优先级规则，让我们忽略它们。我首先想知道如何读取字符串查询并根据运算符的数量将其分成几部分。 - Muenze

@Muenze，那你已经在我的回答中部分地得到了答案。我会稍作修改以使其更清晰明了。 - Gnudiff

好的，我现在明白你想要什么了，根据我在原帖中的评论。这样更有意义，但意味着我的答案需要重新写。现在太累了，如果明天没有人回答，我会尽量更新它。 - Gnudiff

Answer 2

另一种方法是内存中的交集（对于您的AND情况，您可以增强OR，NOT等），可以在posting列表上执行合并算法，假设列表已排序（doc_id顺序递增，如果正确索引了我们的术语，这很容易实现）-这将改善时间复杂度（O（n1 + n2）），因为我们将在已排序的列表上执行线性合并，并可能更早地停止。

现在假设我们的倒排索引如下所示:（与您的类似，但帖子列表为列表而不是字典-这将允许在将来使用中进行压缩） 其中它映射-String>Terms，每个术语由(tf，posting list ([P1，P2，...]))组成，每个Posting具有（docid，df，position list）。 现在，我们可以迭代地对所有张贴列表执行简单的AND：

def search(self, sq: BoolQuery) -> list:

    # Performs a search from a given query in boolean retrieval model,
    # Supports AND queries only and returns sorted document ID's as result:

    if sq.is_empty():
        return super().search(sq)

    terms = [self.index[term] for term in sq.get_terms() if term in self.index]
    if not terms:
        return []

    # Iterate over posting lists and intersect:
    result, terms = terms[0].pst_list, terms[1:]
    while terms and result:
        result = self.intersect(result, terms[0].pst_list)
        terms = terms[1:]
    return [p.id for p in result]

现在让我们看一下交集：

def intersect(p1: list, p2: list) -> list:

    # Performs linear merge of 2x sorted lists of postings,
    # Returns the intersection between them (== matched documents):

    res, i, j = list(), 0, 0
    while i < len(p1) and j < len(p2):
        if p1[i].id == p2[j].id:
            res.append(p1[i])
            i, j = i + 1, j + 1
        elif p1[i].id < p2[j].id:
            i += 1
        else:
            j += 1
    return res

这个简单算法可以在执行短语搜索时进行扩展（编辑交集以计算 slop 距离，例如：|pos1-pos2| < slop）。

- a.k

Answer 3

考虑到您拥有反向索引，即一个以test和try为键的字典，您可以定义以下功能并与它们进行交互：

def intersection(list1, list2):
    return list(set(list1).intersection(list2))
def union(list1, list2):
    return list(set(list1).union(list2))
def notin(list1, list2)
    return [filter(lambda x: x not in list1, sublist) for sublist in list2]

intersection(inverted_index['people'].keys(), intersection(inverted_index['test'].keys(), inverted_index['try'].keys()))

- Tim Givois

---

嗨，Tim。好的，那很有道理。但我需要代码能够灵活处理任何给定的单词作为输入。此外，它可能会有超过两个运算符，例如：test AND try AND people... - Muenze

是的，您可以创建函数并使用它构建查询，最困难的部分是弄清楚如何实际执行交集。我想那就是问题所在。 - Tim Givois

是的，这就是它。如果你能帮我弄清楚，我会很感激。 - Muenze

是的，答案具有交集、并集等函数。对于三个字符，您可以使用以下代码：intersection(inverted_index['people'].keys(), intersection(inverted_index['test'].keys(), inverted_index['try'].keys()))，等等。 - Tim Givois

@a.k 我不确定，似乎有人想让他的回答获得更多的投票 :( - Tim Givois

更好的实现可以是一个简单的线性合并（因为我们已经排序了帖子列表），我也会发布我的尝试。关于NOT部分-为什么不使用集合差分操作？ - a.k