正則表達式掛起程序（100％CPU使用率）

當我使用下面的字符串作爲正則表達式的輸入時，Java以100％的CPU使用率掛起。正則表達式掛起程序（100％CPU使用率）

使用正則表達式：

下面是用於在我的應用程序說明字段的正則表達式。用於測試

^([A-Za-z0-9\\-\\_\\.\\&\\,]+[\\s]*)+

字符串：

SaaS服務VLAN從Provider_One
與迪迪埃SPT第2次嘗試，因爲第一次他給了我錯了:-(

當我用不同的組合分割相同的字符串時，它正常工作，比如「來自Provider_One的SaaS服務VLAN」，「他給我的第一個錯誤:-(」，等等。Java是hangi只適用於上面給定的字符串。

我也嘗試過優化正則表達式，如下所示。

^([\\w\\-\\.\\&\\,]+[\\s]*)+

即使這是行不通的。

來源

2012-07-17 user1531484

你想匹配或從該字符串中提取什麼？你的正則表達式似乎基本上匹配任何句子。 – nickb 2012-07-17 13:02:48

@ user1531484 - 可以發佈整個代碼，即Pattern，Matcher和代碼以獲取。 – Saurabh 2012-07-17 13:04:12

當您從字符串中刪除笑臉和數字時它工作嗎？ – amon 2012-07-17 13:05:06

首先，你需要認識到你的regexes不能匹配提供的輸入字符串。這些字符串包含不是「單詞」字符的數字字符（'<' '>' '/' ':'和')'）。

那爲什麼要這麼長時間？

基本上是「災難性的回溯」。更具體地說，正則表達式的重複結構給出指數正則表達式回溯算法的替代方案的數量！

這是你的正則表達式這樣說：

一個或多個單詞字符
後跟零個或多個空格字符
重複前面的2種模式多次，只要你喜歡。

問題出在「零個或多個空格字符」部分。第一次，匹配器會匹配第一個意想不到的字符（即'<'）。然後，它會退後一步，用另一種替代方法再次嘗試......在最後一個字母之前涉及「零空格」，然後在失敗時將「零空格」移回一個位置。

問題是，對於字符串N非空格字符，有N不同的地方，「零空格」可以匹配，並且這使得2^N不同的組合。隨着N的增長，這會迅速變成一個很大的數字，最終的結果很難與無限循環區分開來。

來源

2012-07-17 13:11:18

catastrophic backtracking的另一個經典案例。

你嵌套，導致排列的巨大數量的量詞進行檢查時，正則表達式中，是不是你的性格類的一部分（您使用的.matches()方法假設）您輸入的字符串到達:。

讓我們簡化問題，這個正則表達式：

^([^:]+)+$

與此字符串：

1234:

正則表達式引擎需要檢查

1234 # no repetition of the capturing group 
123 4 # first repetition of the group: 123; second repetition: 4 
12 34 # etc. 
12 3 4 
1 234 
1 23 4 
1 2 34 
1 2 3 4

...這只是爲了四個字符。在你的示例字符串上，RegexBuddy在100萬次嘗試後中止。 Java會高興地繼續徘徊...在最終承認這些組合中沒有一個允許以下:匹配。

你如何解決這個問題？

您可以通過使用possessive quantifiers回溯禁止正則表達式：

^([A-Za-z0-9_.&,-]++\\s*+)+

將允許正則表達式失敗得更快。順便說一下，我刪除了所有不必要的反斜槓。

編輯：

幾個測量：

關於字符串"was wrong :-)"，它需要使用RegexBuddy 862個步驟，找出不匹配。
對於"me was wrong :-)"，它是1,742步。
對於"gave me was wrong :-)",14204步驟。
對於"he gave me was wrong :-)",28,046步驟。
對於"one he gave me was wrong :-)",112,222步驟。
對於"first one he gave me was wrong :-)"，> 1,000,000步。

來源

2012-07-17 13:11:46

您需要保留'.'的反斜槓。 – Thor84no 2012-07-17 13:25:22

+24

@ Thor84no：不。在一個角色類中，一個點代表一個點。 – 2012-07-17 13:26:46

感謝您的回答。是。我正在使用.matches（）方法。更新後的正則表達式工作正常。你能否解釋一下反斜槓是如何影響性能的？在上面的正則表達式中++有什麼意義？謝謝 – user1531484 2012-07-18 06:09:29

爲什麼你將whitespace與其他字符分開匹配？你爲什麼要在比賽開始時固定比賽，但不是最後？如果你想確保字符串不啓動或空格結束，你應該做這樣的事情：

^[A-Za-z0-9_.&,-]+(?:\s+[A-Za-z0-9_.&,-]+)*$

現在只有一個「路徑」正則表達式引擎可以通過串。如果在達到結尾之前用完與[A-Za-z0-9_.&,-]匹配的字符，並且下一個字符與\s不匹配，則立即失敗。如果在仍然匹配空白字符的情況下達到最後，則會失敗，因爲在每次運行空白後需要至少匹配一個非空白字符。

如果你想確保有隻有一個空格字符分隔非空白的運行，只是從\s+刪除量詞：

^[A-Za-z0-9_.&,-]+(?:\s[A-Za-z0-9_.&,-]+)*$

如果你不關心空格是相對於非空白，只是比賽他們都具有相同的字符類：

^[A-Za-z0-9_.&,\s-]+$

我假設你知道你的正則表達式不會給定的輸入匹配，因爲在SMI的:和(的萊伊，你只是想知道爲什麼要失敗這麼長時間。

和當然，因爲你創造了一個Java字符串字面形式的正則表達式，你可以這樣寫：

"^[A-Za-z0-9_.&,-]+(?:\\s+[A-Za-z0-9_.&,-]+)*$"

或

"^[A-Za-z0-9_.&,-]+(?:\\s[A-Za-z0-9_.&,-]+)*$"

或

"^[A-Za-z0-9_.&,\\s-]+$"

（我知道你在原始問題中有雙反斜槓，但這可能只是爲了讓他們展示適當的因爲你沒有使用SO的優秀代碼格式化功能。）

來源

2012-07-17 15:34:43

「^ [A-Za-z0-9 _。＆， - ] +（？：\\ s [A-Za-z0-9 _。＆， - ] +）* $」與原始字符不匹配，因爲它不會與具有兩個連續空格的字符串匹配。但你的正則表達式「^ [A-Za-z0-9 _。＆， - ] +（？：\\ s + [A-Za-z0-9 _。＆， - ] +）* $」並且我更喜歡它比Tim Pietzcker的掌握量詞解決方案 - 後者太聰明瞭。 :-) – 2012-07-21 19:59:49

正則表達式掛起程序（100％CPU使用率）

回答

相關問題