Expresión regular de Java ejecutando muy lento

Question

Estoy tratando de usar el Daring Fireball Regular Expression for matching URLs en Java, y he encontrado una URL que hace que la evaluación dure para siempre. Modifiqué la expresión regular original para que funcione con la sintaxis de 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); 

Si intento ejecutar lo siguiente, lleva una eternidad. Lo he reducido a la comparación de parens balanceados (creo). Si cambia el texto dentro de los parens, funciona bien, pero con unos 15 caracteres, comienza a disminuir exponencialmente.

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

¿Hay alguna manera de mejorar esta expresión regular para que las líneas sobre no tarden para siempre? Tengo aproximadamente 100 URL diferentes en una clase de prueba JUnit, y las necesito para seguir trabajando también.

Answer 1

El problema es aquí:

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

Lo que tenemos aquí es cuantificadores anidados. Esto hace estragos en cualquier algoritmo de vuelta atrás - como un ejemplo, considere la expresión regular /^(a+)+$/ coincidente con la cadena

aaaaaaaaaab 

En un primer intento, el cuantificador interno coincidirá con todas las a s. Entonces la expresión regular falla, por lo que retrocede una. Entonces el cuantificador externo intenta emparejar nuevamente, tragando el último a, luego la expresión regular falla una vez más. Básicamente, obtenemos un comportamiento exponencial ya que los cuantificadores intentan todo tipo de formas de dividir la ejecución de a s, sin lograr ningún progreso.

La solución es cuantificadores posesivos (que denotamos por viradas una + en el extremo de un cuantificador) - establecimos los cuantificadores internos de manera que una vez que tengan una coincidencia, no dejarlo ir - se Lo mantendré hasta que la coincidencia falle o un cuantificador anterior retroceda y tengan que volver a comenzar desde otra parte de la cadena. Si en cambio usamos /^(a++)+$/ como nuestra expresión regular, fallaremos inmediatamente en la cadena que no coincide arriba, en lugar de ir exponencial tratando de hacer coincidir.

Intente hacer que esos cuantificadores internos sean posesivos y vea si esto ayuda.