正則表達式的用戶名增加了CPU消耗

用戶名可以包含字母數字字符
用戶名可以有下劃線，連字符或一段
現在假設用戶名是在ASCII
用戶名不能啓動或以句點結束
用戶名不能啓動，結束或任何空格

我們有相同的正則表達式如下：

^(([a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*)([\\.]*[a-zA-Z0-9])*)+$

現在試圖以匹配特定字符串，CPU使用率呈指數增長。例如：

[email protected]

顯然，匹配上面的字符串應該會立即失敗，但我想知道爲什麼需要這麼多的CPU週期。最終代碼：

import java.util.regex.*; 
public class R { 
    static final Pattern namePattern = Pattern.compile("^(([a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*)([\\.]*[a-zA-Z0-9])*)+$"); 

    public static void main(String... args) { 
     final String userName = "[email protected]"; 
     Matcher matcher = namePattern.matcher(userName); 
     System.out.println(matcher.matches()); 
    } 
}

在不同的線路，我重寫了正則表達式如下圖所示，它交易會得好：

^[\\w]+[\\w-_\\.]*[\\w]+$

來源

2013-04-29 user320599

它可能是由一個或多個量詞（'+'）封裝整個正則表達式引起的，導致回溯導致您觀察到大量的CPU週期。 – Vulcan 2013-04-29 20:23:41

+10

這聽起來像是[災難性的回溯]（http://www.regular-expressions.info/catastrophic.html）的案例... – 2013-04-29 20:26:42

@Vulcan - 感謝您帶來全球的'（+）'量詞，還取決於用戶名的長度？就像_username @ _一樣簡單，即時失敗。 – user320599 2013-04-29 20:31:24

當正則表達式引擎使用回溯了很多，匹配的過程變得非常緩慢。當您讓表達式的不同部分與輸入的重疊部分相匹配時，特別是在沒有匹配時，回溯會發生很多情況：引擎嘗試在正則表達式各部分之間分割輸入的不同可能性。

從您的正則表達式考慮一個簡單的例子：讓我們用[a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*匹配M45766235H.注意，有兩個子表達式，可以覆蓋先從第二個所有字符：發動機必須考慮所有這些可能性：

[a-zA-Z0-9]+ [a-zA-Z0-9]* 
------------ ------------ 
M45766235H <nothing> 
M45766235 H 
M4576623  5H 
M457662  35H 
M45766  235H 
M4576  6235H 
M457   66235H 
M45   766235H 
M4   5766235H 
M   45766235H

鑑於沒有匹配，那就是10個無用的重複。但這不是結束！如果組合中還有其他子表達式可能會產生模糊的覆蓋範圍，則會針對字符串中的每個可能匹配嘗試這十個可能的匹配項。

要說回溯效應加起來很快就會是輕描淡寫：它們會以幾何級數遞增，最終會消耗大量的CPU。

這個故事的寓意是試圖減少回溯量。例如，你的第二表達

^[\\w]+[\\w-_\\.]*[\\w]+$

可以改寫如下：

^\\w[\\w-_\\.]*\\w$

兩個表達式將匹配同一組輸入，但是當存在匹配時，第二表達將具有唯一匹配，而原始表達式大致具有在匹配單詞字符的三個子表達式之間拆分匹配的字符串的不同方式。

以下是關於相關主題的更多閱讀：Performance of Greedy vs. Lazy Quantifiers。

來源

2013-04-29 21:03:29 dasblinkenlight

感謝您的解釋。完全合理。 – user320599 2013-04-29 22:20:39

正則表達式的用戶名增加了CPU消耗

回答

相關問題