Java正則表達式運行速度非常慢

Question

我正嘗試在Java中使用Daring Fireball Regular Expression for matching URLs，並且我找到了一個導致評估持續進行的URL。我修改了原來的正則表達式以使用Java語法。

private final static String pattern = 
"\\b" + 
"(" +       // Capture 1: entire matched URL 
    "(?:" + 
    "[a-z][\\w-]+:" +    // URL protocol and colon 
    "(?:" + 
     "/{1,3}" +      // 1-3 slashes 
     "|" +        // or 
     "[a-z0-9%]" +      // Single letter or digit or '%' 
             // (Trying not to match e.g. "URI::Escape") 
    ")" + 
    "|" +       // or 
    "www\\d{0,3}[.]" +    // "www.", "www1.", "www2." … "www999." 
    "|" +       // or 
    "[a-z0-9.\\-]+[.][a-z]{2,4}/" + // looks like domain name followed by a slash 
    ")" + 
    "(?:" +       // One or more: 
    "[^\\s()<>]+" +      // Run of non-space, non-()<> 
    "|" +        // or 
    "\\((?:[^\\s()<>]+|(?:\\([^\\s()<>]+\\)))*\\)" + // balanced parens, up to 2 levels 
    ")+" + 
    "(?:" +       // End with: 
    "\\((?:[^\\s()<>]+|(?:\\([^\\s()<>]+\\)))*\\)" + // balanced parens, up to 2 levels 
    "|" +         // or 
    "[^\\s`!\\-()\\[\\]{};:'\".,<>?«»「」‘’]" +  // not a space or one of these punct chars (updated to add a 'dash' 
    ")" + 
")"; 

// @see http://daringfireball.net/2010/07/improved_regex_for_matching_urls 
private static final Pattern DARING_FIREBALL_PATTERN = Pattern.compile(pattern, Pattern.CASE_INSENSITIVE | Pattern.UNICODE_CASE); 

如果我嘗試運行以下操作，則需要花費很長時間。我已經縮小到平衡的parens匹配（我認爲）。如果你改變了parens中的文字，它可以正常工作，但是在大約15個字符處，它開始以指數方式減速。

final Matcher matcher = pattern.matcher("https://goo.gl/a(something_really_long_in_balanced_parens)"); 
boolean found = matcher.find(); 

是否有改善這種正則表達式，這樣對線不會永遠走一條？我在JUnit測試課中有大約100個不同的URL，我需要這些URL繼續工作。

Answer 1

的問題是在這裏：

"(?:" +       // One or more: 
"[^\\s()<>]+" +      // Run of non-space, non-()<> 
"|" +        // or 
"\\((?:[^\\s()<>]+|(?:\\([^\\s()<>]+\\)))*\\)" + // balanced parens, up to 2 levels 
")+" 

你現在看到什麼是嵌套量詞。這嚴重破壞任何回溯算法 - 作爲一個例子，考慮對字符串

aaaaaaaaaab 

作爲第一個嘗試的正則表達式匹配/^(a+)+$/，內量詞會匹配所有a S的。然後，正則表達式失敗，所以它退出一個。然後外部量詞嘗試再次匹配，吞噬最後的a，然後正則表達式再次失敗。我們基本上會得到指數行爲，因爲量詞嘗試各種方式來分裂運行a s，而沒有真正取得任何進展。

的解決方案是佔有慾量詞（其中我們用一個套結到+量詞結束） - 我們建立內部量詞，這樣一旦他們有比賽，他們不會讓他走了 - 他們直到比賽失敗或之前的量詞退後，他們不得不重新開始在字符串中的其他位置。如果我們使用/^(a++)+$/作爲我們的正則表達式，那麼我們將立即在上面的非匹配字符串上失敗，而不是按照指數函數來匹配它。

試着讓這些內部量詞所有格，看看它是否有幫助。