Java Regular Expression运行速度很慢
我正在尝试使用Daring Fireball正则表达式来匹配 Java中的URL ，并且我找到了一个导致评估永远需要的URL。 我修改了原始的正则表达式以使用Java语法。
private final static String pattern = "\\b" + "(" + // Capture 1: entire matched URL "(?:" + "[az][\\w-]+:" + // URL protocol and colon "(?:" + "/{1,3}" + // 1-3 slashes "|" + // or "[a-z0-9%]" + // Single letter or digit or '%' // (Trying not to match eg "URI::Escape") ")" + "|" + // or "www\\d{0,3}[.]" + // "www.", "www1.", "www2." … "www999." "|" + // or "[a-z0-9.\\-]+[.][az]{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，我还需要它们继续工作。
问题出在这里：
"(?:" + // One or more: "[^\\s()<>]+" + // Run of non-space, non-()<> "|" + // or "\\((?:[^\\s()<>]+|(?:\\([^\\s()<>]+\\)))*\\)" + // balanced parens, up to 2 levels ")+"
你在这里得到的是嵌套量词 。 这会对任何回溯算法造成严重破坏 – 例如，考虑正则表达式/^(a+)+$/匹配字符串
aaaaaaaaaab
作为第一次尝试，内部量词将匹配所有的s。 然后正则表达式失败，所以它退出一个。 然后外部量词再次尝试匹配，吞下最后a ，然后正则表达式再次失败。 我们基本上得到了指数行为，因为量词会尝试各种方式来分割s的运行，而不会实际取得任何进展。
解决方案是占有量词 （我们通过在量词的末尾添加+表示） – 我们设置内部量词，这样一旦它们匹配，它们就不会让它继续 – 它们会坚持到匹配失败或早期的量词后退，他们必须从字符串中的其他位置开始重新匹配。 如果我们改为使用/^(a++)+$/作为我们的正则表达式，我们将立即在上面的非匹配字符串上失败，而不是试图匹配它的指数。
尝试使那些内部量词占有欲，看看它是否有帮助。