7

我有一个倒排索引（作为字典），我想将一个布尔搜索查询作为输入来处理它并产生结果。

倒排索引是这样的：

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

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

例子：

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

布尔搜索查询：test OR try 结果应该是所有具有测试或尝试的文档。

布尔搜索查询：test AND NOT try 结果应该是所有有测试但没有尝试的文档。

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

提前致谢！

4

3 回答 3

3

编辑：我保留了答案的第一部分，因为如果这不是学校作业，我认为这仍然是完成任务的更好方法。我将答案的第二部分替换为更新匹配 OP 的问题。

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

有两种方法。

  1. 根据您所写的内容，到目前为止，最简单的解决方案是将数据加载到任何 SQL 数据库（例如，SQLite，它不需要完整的运行 SQL 服务器），将字典键作为单独的字段加载（如果您不关心普通格式 &c，您的其余数据可能都在另一个字段中），并将传入的查询转换为 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 数据库运行时，它将返回键（可能还有数据）以进行进一步处理。

  1. 现在是纯 Python 版本。

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

分析字符串以将其简化为特定组件（及其交互）是解析。如果您真的想构建自己的完全成熟的解析器，那么会有 Python 模块，但是，对于学校作业，我希望您的任务是构建自己的。

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

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

既然你说优先级并不相关，你可以用简单的方法逐字解析。

然后，您必须将关键字与文件名匹配，正如另一个答案中提到的那样，使用sets最容易做到这一点。

因此，它可能大致是这样的：

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

请注意，这不是一个完整的解决方案（例如，它不包括处理查询的第一项，并且它要求布尔运算符为大写），并且未经测试。但是，它的主要目的应该是向您展示如何去做。做更多的事情就是为你写课程作业，这对你不利。因为你应该学习如何去做，这样你才能理解它。随时要求澄清。

于 2017-10-27T18:06:36.270 回答
3

另一种方法可能是发布列表的内存交集（对于您的 AND 案例，您可以为 OR、NOT 等增强此功能）。

附上一个简单的合并算法，在发布列表上执行，假设列表是排序的（增加 doc_id 顺序，如果我们正确索引我们的术语，这很容易实现） - 这将提高时间复杂度 (O(n1+n2))因为我们将对排序列表执行线性合并，并且可能会更早停止。

现在假设我们的位置倒排索引看起来像这样：（类似于您的，但将列表作为列表而不是 dict 发布 - 这将允许在未来使用中进行压缩）其中映射 - String > Terms，而每个术语由 (tf, 张贴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

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

于 2019-06-18T11:23:38.303 回答
0

考虑到你有那个倒排索引，这是一个带有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()))
于 2017-10-27T15:40:39.470 回答