Java Regular Expression работает очень медленно

Question

Я пытаюсь использовать регулярное выражение Daring Fireball для сопоставления URL в Java, и я нашел 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);

Если я попытаюсь выполнить следующее, это займет вечность.Я сузил это до соответствия сбалансированных паренов (я думаю).Если вы измените текст в скобках, он будет работать нормально, но при 15 символах он начнет экспоненциально замедляться.

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

Есть ли способ улучшить это регулярное выражение, чтобы строкивзять навсегда?У меня есть около 100 различных URL-адресов в тестовом классе JUnit, и они мне нужны, чтобы они также продолжали работать.

Answer 1

Проблема здесь:

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

Здесь у вас есть вложенные квантификаторы . Это приводит к хаосу с любым алгоритмом обратного отслеживания - в качестве примера рассмотрим регулярное выражение /^(a+)+$/, совпадающее со строкой

aaaaaaaaaab

В качестве первой попытки внутренний квантификатор будет соответствовать всем a с. Тогда регулярное выражение терпит неудачу, поэтому оно отступает от одного. Затем внешний квантификатор снова пытается найти соответствие, сглотнув последний a, затем регулярное выражение снова выходит из строя. Мы в основном получаем экспоненциальное поведение, так как квантификаторы пробуют всевозможные способы разделить серию a с, фактически не добиваясь прогресса.

Решением является притяжательные квантификаторы (которые мы обозначаем прикреплением + к концу квантификатора) - мы устанавливаем внутренние квантификаторы таким образом, чтобы после того, как у них есть совпадение, они не отпусти - они будут держаться до тех пор, пока совпадение не завершится или более ранний квантификатор не отступит, и им придется пересчитать, начиная где-то еще в строке. Если бы вместо этого мы использовали /^(a++)+$/ в качестве нашего регулярного выражения, мы немедленно потерпели бы неудачу в приведенной выше несоответствующей строке, а не стали экспоненциально пытаться сопоставить ее.

Попробуйте сделать эти внутренние квантификаторы притяжательными и посмотрите, поможет ли это.