在Python中找到一个字符串是否匹配单词，短语和布尔逻辑与列表中的任何术语的最快方法是什么？

Question

我试图找到在Python快速的方法来检查，如果条件的列表可以对字符串从50到50000个字符大小不等的匹配。

一个术语可以是：

• 一个字，例如。 “苹果”
• 的短语，如： “樱桃派”
• 单词和短语，例如布尔与操作。 “甜馅饼和咸味馅饼和酥皮”

一场比赛就是围绕字边界存在一个词或短语，所以：

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

我没有兴趣在短期（一个或多个）的字符串匹配，或在字符串中匹配，我只是需要一个真/假值对每个串的匹配 - 这是更可能是没有条件将匹配的字符串，因此对于1 500，其中它的比赛，我可以存储以便进一步处理的字符串。

速度是最重要的标准，我想利用那些比我聪明现有的代码，而不是试图实现一个白色的纸。 :)

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

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

因此，所有的条款一起进行或操作，忽略大小写：

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) 

正则表达式作为卷起，单词/短语被包装在\ b中用于单词边界，布尔ANDs使用超前，以便所有术语都匹配，但不必按特定顺序匹配。

Timeit结果：

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

没有向前看符号（即布尔与运算）。这实在是快，但一旦他们投入速度减慢显着。

是否有人对如何可以改善的想法？有没有一种方法来优化lookahead，或者可能是一种完全不同的方法？我不认为词干会起作用，因为它与匹配的词会有点贪婪。

Answer 1

布尔值和与多模式断言正则表达式可以通过将其固定到字符串的开头显着地加快。或者更好的是，使用两个正则表达式：一个使用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正则表达式“引擎”是如何工作的。 （请注意，以下的说明关于这一主题的经典之作得出：由杰弗里·弗里德尔（MRE3），这也解释了这一切的效率东西很详细Mastering Regular Expressions (3rd Edition) - 高度推荐）假设你有一个包含一个字一个目标字符串你需要一个正则表达式来看看这个单词是否是："apple"。这里有两个正则表达式一个可能构成做的工作：

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

如果你的目标字符串是：apple（或applesauce或apple-pie等），那么这两个正则表达式将成功匹配得非常快。但是，如果你的目标字符串是说：orange，情况是不同的。一个NFA正则表达式引擎必须设法目标串正则表达式的所有可能的排列，才可以宣布比赛的失败。正则表达式“引擎”的工作方式是，它保持一个指向目标字符串内的当前位置的内部指针，以及指向正则表达式模式内的位置的第二个指针，并在这些指针进行其业务时推进这些指针。请注意，这些指针指向位置的字符之间并与其目标字符串指针，如果目标字符串的第一个字母之前设置的位置开始。

re1：正则表达式中的第一个标记是^字符串定位的开始。这个“锚”是指在目标字符串相匹配的位置，并不实际匹配任何字符，特殊的“断言”的表现之一。 （Lookahead和lookbehind，\b字边界表达式也是与位置匹配并且不会“消耗”任何字符的断言。）好吧，目​​标字符串指针初始化为单词orange的第一个字母前的位置，正则表达式引擎检查^锚点是否匹配，并且它确实（因为这个位置实际上是字符串的开始）。所以模式指针前进到正则表达式中的下一个标记，即字母a。 （目标字符串指针不提前）。然后，它检查是否正则表达式字面a目标串字符o匹配。它不匹配。在这一点上，正则表达式引擎足够聪明，知道正则表达式在目标字符串内的任何其他位置永远不会成功（因为^在开始时无法匹配任何位置）。因此它可以声明匹配失败。

re2：在这种情况下，引擎首先检查char a是否与第一个目标字符'o'匹配。再一次，它没有。但是，在这种情况下，正则表达式引擎没有完成！它已确定该模式在第一个位置不匹配，但它必须在目标字符串位于所有位置尝试（并失败），然后才能声明匹配失败。因此，引擎将目标字符串指针前进到下一个位置（Friedl将此称为传输“碰撞”）。对于每个“碰撞”，它将模式指针重置回开始。因此它检查模式a中的第一个标记与字符串中的第二个字符：r。这也不匹配，所以传输会再次碰到字符串中的下一个位置。在这一点上，它测试模式a的第一个字符对目标的第三个字符：a，其中确实与匹配。引擎使两个指针前进，并检查正则表达式p中的第二个字符与目标n中的第四个字符。这失败了。此时，发动机宣布在a,orange之前的位置发生故障，然后再次碰到n。它继续如此，直到它在目标字符串中的每个位置都失败，此时它可以声明整体匹配失败。

对于较长的主题字符串，这种额外的不必要的工作可能需要很长时间。精确和高效的正则表达式就是平等的艺术和科学。为了制作一个非常棒的正则表达式，人们必须确切地理解引擎在引擎盖下的工作原理。获得这种知识需要时间和精力，但花费的时间（以我的经验）会为自己付出很多时间。实际上，只有一个地方可以有效地学习这些技能，那就是坐下来学习Mastering Regular Expressions (3rd Edition)，然后练习所学的技巧。我可以诚实地说，这是我读过的最有用的一本书。 （它甚至好笑！）

希望这有助于！ 8 ^）

Answer 2

，我要在这里给出了部分答案，但你为什么不拆的字边界测试和匹配的字符串，并建立一个set。你可以非常快速地交集集合，如果集合匹配，那么你可以做昂贵的正则表达式测试。