python - 在 Python 中查找字符串是否与单词、短语、 bool AND 列表中的任何术语匹配的最快方法是什么？

Question

我试图在 Python 中找到一种快速方法来检查术语列表是否可以与大小从 50 到 50,000 个字符的字符串匹配。

一个术语可以是:

一个词，例如。 '苹果'

一个短语，例如。 “樱桃派”

单词和短语的 bool 与运算，例如。 “甜馅饼和咸味馅饼和蛋白酥皮”

匹配是单词或短语围绕单词边界存在的地方，因此:

match(term='apple', string='An apple a day.') # True
match(term='berry pie', string='A delicious berry pie.') # True
match(term='berry pie', string='A delicious blueberry pie.') # False

我目前有大约 40 个术语，其中大部分是简单的单词。术语的数量会随着时间的推移而增加，但我不希望它超过 400。

我对字符串匹配的术语不感兴趣，或者它在字符串中匹配的位置不感兴趣，我只需要一个真/假值来匹配每个字符串 - 更有可能没有术语与字符串匹配，因此对于匹配的 500 分之一，我可以存储字符串以供进一步处理。

速度是最重要的标准，我想利用比我更聪明的人的现有代码，而不是试图实现白皮书。 :)

到目前为止，我想出的最快的解决方案是:

def data():
    return [
        "The apple is the pomaceous fruit of the apple tree, species Malus domestica in the rose family (Rosaceae).",
        "This resulted in early armies adopting the style of hunter-foraging.",
        "Beef pie fillings are popular in Australia. Chicken pie fillings are too."
    ]

def boolean_and(terms):
    return '(%s)' % (''.join(['(?=.*\\b%s\\b)' % (term) for term in terms]))

def run():
    words_and_phrases = ['apple', 'cherry pie']
    booleans = [boolean_and(terms) for terms in [['sweet pie', 'savoury pie', 'meringue'], ['chicken pie', 'beef pie']]]
    regex = re.compile(r'(?i)(\b(%s)\b|%s)' % ('|'.join(words_and_phrases), '|'.join(booleans)))
    matched_data = list()
    for d in data():
        if regex.search(d):
            matched_data.append(d)

正则表达式结束为:

(?i)(\b(apple|cherry pie)\b|((?=.*\bsweet pie\b)(?=.*\bsavoury pie\b)(?=.*\bmeringue\b))|((?=.*\bchicken pie\b)(?=.*\bbeef pie\b)))

所以所有的术语都被 ORed 在一起，大小写被忽略，单词/短语被包裹在\b 中作为单词边界， bool AND 使用前瞻来匹配所有的术语，但它们不必以特定的顺序匹配。

时间结果:

 print timeit.Timer('run()', 'from __main__ import run').timeit(number=10000)
 1.41534304619

没有前瞻(即 bool AND)，这真的很快，但是一旦添加，速度就会大大减慢。

有没有人有关于如何改进的想法？有没有办法优化前瞻，或者可能是一种完全不同的方法？我不认为词干提取会起作用，因为它对匹配的东西往往有点贪婪。

Answer 1

我将在这里给出部分答案，但为什么不将测试和匹配字符串拆分为单词边界并构建一个 set .您可以非常快速地交叉集合，如果集合匹配，那么您可以进行昂贵的正则表达式测试。