在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。你可以非常快速地交集集合，如果集合匹配，那麼你可以做昂貴的正則表達式測試。