在Python中，快速判断字符串是否匹配列表中的词、短语或布尔与的方式是什么？

Question

我正在寻找一种快速的方法，用Python检查一组词是否可以与长度在50到50,000个字符之间的字符串匹配。

一个词可以是：

• 一个单词，比如说 'apple'（苹果）
• 一个短语，比如说 'cherry pie'（樱桃派）
• 多个词和短语的布尔与运算，比如说 'sweet pie AND savoury pie AND meringue'（甜派和咸派和蛋白霜）

匹配的意思是，某个单词或短语在单词的边界上出现，所以：

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个字符串中有1个匹配时，我可以把这个字符串存起来，方便后续处理。

速度是最重要的标准，我希望能利用那些比我聪明的人的现有代码，而不是自己去实现一个复杂的方案。:)

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

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)))

所以所有的词都用“或”连接，大小写不敏感，单词/短语用 \b 包裹以表示单词边界，而布尔与运算使用前瞻，这样所有的词都能匹配，但不需要按特定顺序匹配。

使用timeit测试的结果是：

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

如果不使用前瞻（也就是布尔与运算），速度非常快，但一旦加上前瞻，速度就会明显变慢。

有没有人有想法可以改进这个？有没有办法优化前瞻，或者换一种完全不同的方法？我觉得词干提取可能不太适用，因为它在匹配时往往会有点贪心。

Answer 1

我在这里给出一个部分答案。你可以试着把测试字符串和匹配字符串按照单词的边界分开，然后建立一个set（集合）。这样的话，你可以很快地对集合进行交集操作。如果集合匹配成功了，再进行比较复杂的正则表达式测试。

Answer 2

使用布尔与（AND）正则表达式和多个前瞻断言时，可以通过将它们固定在字符串的开头来大幅提高速度。更好的方法是使用两个正则表达式：一个用来处理用re.search方法的“或”（OR）条件列表，另一个用re.match方法处理布尔与（AND）条件列表，像这样：

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

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

对于这个数据集，效果好的正则表达式是：

regex1 = r'(?i)\b(?:apple|cherry pie)\b'
regex2 = r'(?i)(?=.*?\bsweet pie\b)(?=.*?\bsavoury pie\b)(?=.*?\bmeringue\b)|(?=.*?\bchicken pie\b)(?=.*?\bbeef pie\b)'

注意，第二个正则表达式实际上在开头有一个^锚点，因为它是用re.match方法来使用的。这还包括一些额外的小调整，比如去掉不必要的捕获组和将贪婪的点星（.*）改为懒惰模式。这种解决方案在我使用Python 3.0.1的Win32电脑上运行速度几乎快了10倍。

补充：那么为什么会更快呢？我们来看一个简单的例子，说明NFA正则表达式“引擎”是如何工作的。（注意，以下描述来源于经典著作：《正则表达式精髓（第三版）》，作者是Jeffrey Friedl（MRE3），这本书详细解释了所有这些效率问题——强烈推荐。）假设你有一个目标字符串，里面有一个单词，你想用正则表达式来检查这个单词是否是："apple"。这里有两个可能的正则表达式：

re1 = r'^apple'
re2 = r'apple'
s = r'orange'

如果你的目标字符串是：apple（或者applesauce、apple-pie等），那么这两个正则表达式都会很快匹配成功。但如果你的目标字符串是orange，情况就不同了。NFA正则表达式引擎必须尝试所有可能的正则表达式排列，才能宣布匹配失败。正则表达式“引擎”的工作方式是，它在目标字符串中保持一个内部指针，指向当前的位置，还有一个指针指向正则表达式模式中的位置，并随着处理的进行不断移动这些指针。注意，这些指针指向的是字符之间的位置，最开始时，目标字符串的指针设置在目标字符串第一个字母之前。

re1：正则表达式中的第一个标记是^，表示字符串的开始锚点。这个“锚点”是特殊的“断言”表达式之一，它匹配目标字符串中的位置，而实际上并不匹配任何字符。（前瞻和后顾以及\b单词边界表达式也是断言，它们匹配一个位置而不“消耗”任何字符。）好吧，目标字符串指针初始化在单词orange的第一个字母之前，正则表达式引擎检查^锚点是否匹配，结果是匹配的（因为这个位置确实是字符串的开头）。于是模式指针移动到正则表达式中的下一个标记，即字母a。（目标字符串指针没有移动）。接着，它检查正则表达式字母a是否与目标字符串字符o匹配。结果不匹配。此时，正则表达式引擎聪明地知道，正则表达式在目标字符串的其他位置永远无法成功匹配（因为^只能在开头匹配）。因此，它可以宣布匹配失败。

re2：在这种情况下，引擎首先检查模式中的第一个字符a是否与目标字符串的第一个字符o匹配。结果仍然不匹配。然而，在这种情况下，正则表达式引擎并没有结束！它已经确定模式在第一个位置不匹配，但必须在目标字符串的所有位置尝试（并失败）后才能宣布匹配失败。因此，引擎将目标字符串指针移动到下一个位置（Friedl称之为传输“逐步推进”）。对于每一次“逐步推进”，它会将模式指针重置回开头。于是它检查模式中的第一个标记a与目标字符串的第二个字符r。这也不匹配，所以传输再次推进到字符串中的下一个位置。此时，它测试模式中的第一个字符a与目标字符串的第三个字符a，这是匹配的。引擎同时移动两个指针，并检查正则表达式中的第二个字符p与目标字符串中的第四个字符n。这次不匹配。此时，引擎在orange中a之前的位置宣布失败，然后再次推进到n。它就这样继续，直到在目标字符串的每个位置都失败，这时它才能宣布整体匹配失败。

对于较长的目标字符串，这种额外的无谓工作可能会耗费很多时间。制作一个准确高效的正则表达式既是一种艺术，也是一门科学。要制作一个真正优秀的正则表达式，必须准确理解引擎在后台是如何工作的。获得这些知识需要时间和努力，但我认为花费的时间会得到多次回报。而且，学习这些技能的最佳途径就是坐下来研究《正则表达式精髓（第三版）》，然后练习所学的技巧。我可以诚实地说，这是我读过的最有用的书。（它甚至很有趣！）

希望这对你有帮助！8^)