防止RegEx在大型火柴上掛起

Question

這是日期的一個很好的正則表達式...然而它無限期地掛在這一頁上我試過了......我想嘗試這個頁面（http://pleac.sourceforge.net/pleac_python/datesandtimes.html），因爲它確實有很多的日期，我想抓住他們所有人。我不明白爲什麼它不掛在其他頁面上時爲什麼會掛起...爲什麼我的正則表達式掛起和/或我如何清理它以使其更好/更高效？

Python代碼：

monthnames = "(?:Jan\w*|Feb\w*|Mar\w*|Apr\w*|May|Jun\w?|Jul\w?|Aug\w*|Sep\w*|Oct\w*|Nov(?:ember)?|Dec\w*)" 

pattern1 = re.compile(r"(\d{1,4}[\/\\\-]+\d{1,2}[\/\\\-]+\d{2,4})") 

pattern4 = re.compile(r"(?:[\d]*[\,\.\ \-]+)*%s(?:[\,\.\ \-]+[\d]+[stndrh]*)+[:\d]*[\ ]?(PM)?(AM)?([\ \-\+\d]{4,7}|[UTCESTGMT\ ]{2,4})*"%monthnames, re.I) 

patterns = [pattern4, pattern1] 

for pattern in patterns: 
    print re.findall(pattern, s) 

BTW ...當我說我嘗試它反對這個網站..我想這對網頁源。

Answer 1

您應該閱讀Mastering Regular Expressions。問題是：

(?:[\d]*[\,\.\ \-]+)* 

需要指數時間。嘗試使用：

(?:[\d,. \-]*[,. \-])? 

它應該匹配相同的東西，但需要線性時間。通過檢查你的例子，這確實會加快速度。

您也似乎在某些時候意外地將捕獲組引入了您的模式：更改例如（AM）到（？：AM）來解決這個問題。這得到了以下輸出從你上面的例子：

[' Aug 6 20:43:20 2003', ' Mar 14 06:02:55 1973', ' March 14 06:02:55 AM 1973', ' Jun 16 20:18:03 1981'] 
['2003-08-06', '2003-08-07', '2003-07-23', '1973-01-18', '3/14/1973', '16/6/1981', '16/6/1981', '16/6/1981', '16/6/1981', '08/08/2003'] 

要進入細節（這是我引用這本書是很不錯的），*和+工作（在NFA的像Python的重），而像一個循環。原始模式的內部循環將匹配一長串數字，但當後續模式不匹配時，它將一次「放棄」一個。然後外層循環將重新運行剩餘模式的內層循環，當然它會立即再次獲取數字。每次內循環的一個實例放棄一個數字時，將會召喚一個新副本以再次抓取它。最終，一旦引擎經歷了所有可能的分裂該數字串的可能性（指數數量的可能性），它會將起始點向前移動一個字符......然後再試一次。

在另一方面，你的模式看起來有點瘋狂;）

Answer 2

Python正則表達式計算器可能需要很長時間。不幸的是，它運行在最壞的情況下指數時間。

我假設您的「s」包含整個頁面的副本。如果是這樣，那麼在正則表達式評估器中可能會導致很長的回溯。也許你應該把頁面分成更小的塊，然後通過正則表達式單獨運行它們。你可以使用像美麗的HTML解析器，並在每個文本節點上分別運行正則表達式。這可能會減少運行時間。

Answer 3

寫入正則表達式的方式將導致批次的回溯。除了關於在較小的文本塊上運行的技巧之外，還可以使用更簡單（因此更快）的正則表達式來過濾掉不匹配的文本。

Answer 4

首先，你應該在什麼一個r""字符串意味着讀了起來：你只需要投入反斜線，你真的想反斜槓，所以你的正則表達式真的應該僅僅是：

monthnames = "(?:Jan\w*|Feb\w*|Mar\w*|Apr\w*|May|Jun\w?|Jul\w?|Aug\w*|Sep\w*|Oct\w*|Nov(?:ember)?|Dec\w*)" 

pattern1 = re.compile(r"(\d{1,4}[-/]+\d{1,2}[-/]+\d{2,4})") 

pattern4 = re.compile(r"(?:\d*[,. -]+)*%s(?:[,. -]+\d+[stndrh]*)+[:\d]*[ ]?(PM)?(AM)?([ -+\d]{4,7}|[UTCESTGMT ]{2,4})*"%monthnames, re.I) 

至於你真正的問題，Python與嵌套在*內的*不匹配。更改pattern4這個（第一\d*變成\d+）：

pattern4 = re.compile(r"(?:\d+[,. -]+)*%s(?:[,. -]+\d+[stndrh]*)+[:\d]*[ ]?(PM)?(AM)?([ -+\d]{4,7}|[UTCESTGMT ]{2,4})*"%monthnames, re.I) 

和正則表達式回報快，打印這樣的：

[('', '', '2003'), ('', '', '1973'), ('', 'AM', ' 1973'), ('', '', '1981"')] 
['2003-08-06', '2003-08-07', '2003-07-23', '1973-01-18', '3/14/1973', '16/6/1981', '16/6/1981', '16/6/1981', '16/6/1981' 
, '08/08/2003'] 

雖然我不知道這是你想要什麼。