使用正則表達式的100％CPU使用率取決於輸入長度

Question

我試圖想出一個Python中的正則表達式，它必須匹配任何字符，但避免三個或更多個連續的逗號或分號。換句話說，只允許連續使用兩個逗號或分號。

原來這就是我目前有：

^(,|;){,2}([^,;]+(,|;){,2})*$ 

而且似乎按預期方式工作：

>>> r.match('') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, a') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, ,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, ,,a') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, ,,,') 
>>> r.match('foo, ,,,;') 
>>> r.match('foo, ,, ;;') 
<_sre.SRE_Match object at 0x7f23af840750> 

但正如我開始增加輸入文本的長度，正則表達式似乎需要更多的時間來回應。

>>> r.match('foo, bar, baz,, foo') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,') 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,,') 
>>> r.match('foo, bar, baz,, fooooo, baaaaar, baaaaaaz,,,,') 

最後，它完全停留在這個階段，CPU使用率高達100％。

我不確定是否可以對正則表達式進行優化，或者還有其他內容涉及到任何幫助。

Answer 1

您正遇到catastrophic backtracking。

原因是您已將分隔符設置爲可選，因此您的正則表達式的[^,;]+部分（它本身處於重複組中）將在最終必須承認失敗之前嘗試裝入大量排列（baaaaaaaz）面對兩個以上的逗號。

RegexBuddy使用最後一個測試字符串中止正則表達式引擎的1.000.000步之後的匹配嘗試。 Python將繼續嘗試。

想象字符串baaz,,,：

嘗試您正則表達式，正則表達式引擎必須檢查所有這些：

1. baaz,,<failure>
2. baa + z,,<failure>
3. ba + az,,<failure>
4. ba + a + z,,<failure>
5. b + aaz,,<failure>
6. b + aa + z,,<failure>
7. b + a + az,,<failure>
8. b + a + a + z,,<failure>

前宣佈全面失敗。看看它如何與每個額外的角色成指數增長？

類似這樣的行爲可以用佔有量詞或原子組來避免，而這兩者都不被Python當前的正則表達式引擎所支持。但是你可以輕鬆地進行反向檢查：

if ",,," in mystring or ";;;" in mystring: 
    fail() 

根本不需要正則表達式。如果,;,等也可能發生，應該排除，然後使用安德魯的解決方案。

Answer 2

嘗試此正則表達式：

^([^,;]|,($|[^,]|,[^,])|;($|[^;]|;[^;]))*$ 

它重複地匹配：

• 一個單個字符既不是,也不;，或
• 一個,即要麼沒有後跟另一個,或,,之後不是另一個,或
• 一個;即要麼沒有後跟另一個;或;;未後跟另一個;

，直到達到終點。這是非常有效的，因爲它沒有做太多的回溯就會失敗。

Answer 3

我認爲有以下應該做你想要什麼：

^(?!.*[,;]{3}) 

如果字符串包含在一排三個或更多,或;這將失敗。如果你真的希望它匹配一個字符，最後添加一個.。

這利用negative lookahead，這將導致整個匹配失敗，如果正則表達式匹配.*[,;]{3}。

Answer 4

這個想法如何匹配那些你不想要的模式 ".+,,," 在Python中只保留那些不匹配的。 應該很快