finditer在匹配長字符串時掛起

我有一個有點複雜的正則表達式，我試圖匹配長字符串（65,535個字符）。我正在尋找字符串中re的多次出現，所以我使用finditer。它可以工作，但由於某種原因，它會在識別出前幾次事件後掛起。有誰知道這可能是爲什麼？這裏的代碼片段：finditer在匹配長字符串時掛起

pattern = "(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)" 

matches = re.finditer(pattern, string) 
for match in matches: 
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())

它打印出前四次出現，但然後它掛起。當我使用Ctrl-C殺死它，它告訴我它在迭代器喪生：

Traceback (most recent call last): 
    File "code.py", line 133, in <module> 
    main(sys.argv[1:]) 
    File "code.py", line 106, in main 
    for match in matches: 
KeyboardInterrupt

如果我用一個簡單的重新嘗試，它工作正常。

我在運行在Windows XP上的Cygwin上的python 2.5.4上運行它。

我設法讓它掛上一個非常短的字符串。

ddddddeddbedddbddddddddddddddddddddddddddddddddddd

有了它，花了大約15秒返回（並顯示沒有比賽）這個39字符串：

ddddddeddbedddbdddddddddddddddddddddddd

而與此有了這個50字符串，它從來沒有約5分鐘後返回字符串它立即返回：

ddddddeddbedddbdddddddddddddd

來源

2009-04-16 Ben

絕對指數行爲。你有這麼多d*部分的正則表達式，它會回溯像瘋了似的，當它到達D的長字符串，但不能匹配前面的東西。您需要重新考慮正則表達式，因此它嘗試的路徑可能更少。

我特別想：

([ef]d\*b|d\*)*</pre></code> and <code><pre>([ef]|([gh]d\*(ad\*[gh]d)\*b))d\*b

可能需要重新考慮，因爲他們會迫使備用比賽的重試。另外，它們在它們的匹配方面也是重疊的。例如，它們都與edb匹配，但如果其中一個失敗並嘗試回溯其他部分，則可能會有相同的行爲。

因此，在短期儘量不要使用|如果可以的話，儘量確保圖案不重疊在可能的情況。

來源

2009-04-16 09:35:45

謝謝 - 這很有幫助。我可以消除|只是有幾個單獨的正則表達式。我可能會問一個關於刪除d *的新問題 - 我基本上希望正則表達式在任何位置都接受'd'。 – Ben 2009-04-16 09:42:29

@Ben：那只是測試模式之前從字符串D的。 – Gumbo 2009-04-16 09:48:20

難道你的表達式會觸發Python RE引擎中的指數行爲嗎？

This article處理該問題。如果你有時間，你可能想嘗試在使用這些想法開發的RE引擎中運行你的表情。

來源

2009-04-16 09:22:12 unwind

哇 - 什麼有很大的聯繫。很有意思。謝謝。 – Ben 2009-04-16 09:31:31

你已經給了你自己的答案：正則表達式是複雜和模糊的。

您應該嘗試找到一個更簡單，更加明確的表達式，該表達式更易於處理。或告訴我們你想完成什麼，我們可以嘗試幫助你找到一個。

編輯如果你只想讓d S IN的每個位置，你到John Montgomery’s answer評論說，你應該測試圖案之前將其刪除：

import re 

string = "ddddddeddbedddbddddddddddddddddddddddddddddddddddd" 
pattern = "(([ef]|([gh](a[gh])*b))b([ef]b)*c)" 
matches = re.finditer(pattern, re.sub("d+", "", string)) 
for match in matches: 
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())

來源

2009-04-16 09:24:38 Gumbo

我想你體驗所謂的「災難性回溯」。

你的正則表達式有許多可選/替代部分，所有這些部分仍然嘗試匹配，所以以前的子表達式在本地失敗時將以下表達式返回字符。這導致正則表達式中的迴歸 - 第四行爲和執行時間呈指數級增長。

Python（2.7+ ?,我不確定）支持原子分組和佔有量詞，你可以檢查你的正則表達式來識別應該匹配或者整體失敗的部分。不必要的回溯可以被控制。

來源

2009-04-16 09:28:34 Tomalak

災難性的回溯！

正則表達式是非常昂貴的。某些（無意和意圖的）字符串可能會導致RegExes呈現指數行爲。我們已經爲此採取了幾個修補程序。 RegExes非常方便，但開發人員真的需要了解他們的工作方式;我們被他們咬了。

例子和調試器：

http://www.codinghorror.com/blog/archives/000488.html

來源

2009-04-16 09:31:19

感謝所有的反應，這是非常有益的。最後，令人驚訝的是，它很容易加速。這裏是原來的正則表達式：

(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)

我注意到| d *臨近年底是不是真的，我需要什麼，所以我修改，如下所示：

(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*bd*)*c)

現在，它的作品幾乎在瞬間就65,536個字符串。現在我想我只需要確保正則表達式是真正符合我需要它來匹配字符串...

來源

2009-04-16 09:56:54 Ben

finditer在匹配長字符串時掛起

回答

相關問題