词Toptimizer

Question

for s_index, s in enumerate(sentences):
        s_tokens = s.split()
        if (local_q_set.intersection(set(s_tokens)) == local_q_set):
            q_results.append(s_index)

上面的代码段是我用来在包含查询中所有标记的海量文本数据中找到相关句子的核心算法。例如，对于查询“开心苹果”，它找到所有句子，这些句子恰好包括所有给定标记中的一个或多个（即“开心”和“苹果”）。我的方法非常简单：找到常见的相交集，看看它们是否匹配。但是，我没有得到足够的性能。如果有人看到针对此类问题的优化，则非常感谢您提供此想法的任何指导或链接-谢谢您的时间

Answer 1

您可以采取一些措施来提高顺序搜索的性能，但真正的提升将来自索引令牌。

集合差异

使用not local_q_set.difference(s_tokens)而不是将交集与原始集合进行比较可能会更快一些。

正则表达式过滤器

如果句子很长，则使用正则表达式可以通过将潜在的标记从句子中隔离出来，然后再根据标记集检查它们，从而提供一些速度上的改进：

import re
tokens     = re.compile("|".join(local_q_set))
tokenCount = len(local_q_set)
for s_index, s in enumerate(sentences):
    s_tokens = tokens.findall(s)
    if len(s_tokens) < tokenCount or local_q_set.difference(s.split()):
       continue
    q_results.append(s_index) 

使用in运算符进行过滤

您还可以使用简单的in运算符而不是正则表达式来检查标记的存在（当查询中的标记较少时，这应该会更快）：

result = []
tokenSet = set(queryTokens)
for index, sentence in enumerate(sentences):
     if any( token not in sentence for token in queryTokens) \
     or tokenSet.difference(sentence.split()):
         continue
     result.append(index)

缓存句子词集

为了在对同一句子列表进行多个查询时改进顺序搜索，可以构建与该句子相对应的单词集的缓存。这将消除在通过句子查找匹配项时解析句子的工作。

cachedWords = []

queryTokens = ["happy","apple"]

queryTokenSet = set(queryTokens)
if not cachedWords:
    cachedWords = [ set(sentence.split()) for sentence in sentences ]
result = [ index for index,words in enumerate(cachedWords) if not queryTokenSet.difference(words) ]

代币索引

如果要对同一句子列表执行许多查询，则在标记和句子索引之间创建映射会更有效。您可以使用字典来做到这一点，然后通过与查询标记的句子索引相交直接获得查询结果：

tokenIndexes = dict()
for index,sentence in enumerate(sentences):
    for token in sentence.lower().split():
        tokenIndexes.setdefault(token,[]).append(index)

def tokenSet(token): return set(tokenIndexes.get(token,[]))

queryTokens = ["happy","apple"]

from functools import reduce
result = reduce(set.intersection , (tokenSet(token) for token in queryTokens) )

这将允许您使用集合运算符经济地实现复杂的查询。例如：

import re

querySring = " happy & ( apple | orange | banana ) "
result = eval(re.sub("(\w+)",r"tokenSet('\1')", querySring)) 

# re.sub(...) transforms the query string into " tokenSet('happy') & ( tokenSet('apple') | tokenSet('orange') | tokenSet('banana') ) "

性能测试：

我进行了一些性能测试（在80,000个句子中的一个句子中找到了两个标记）：

original algorithm: 105 ms           1x
set.difference:      88 ms         1.2x
regular expression:  60 ms         1.8x
"in" operator:       43 ms         2.4x
caching word sets:   23 ms         4.6x (excluding 187ms to build cache)
token indexing:       0.0075 ms  14000x (excluding 238ms to build tokenIndexes)

因此，如果您要使用标记索引对同一个句子执行多个查询，则在构建tokenIndexes字典后，您将获得14,000倍的响应速度。