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++)+$/作为我们的正则表达式，那么我们将立即在上面的非匹配字符串上失败，而不是按照指数函数来匹配它。

试着让这些内部量词所有格，看看它是否有帮助。