¿Mal rendimiento de las expresiones regulares?

Publicado por Eyal Schneider el 21 de mayo de 2009 El paquete java.util.regex se agregó a Java en la versión 1.4. Es una herramienta muy poderosa y es necesario convertirse en un maestro para utilizarla correctamente. Incluso cuando una expresión regular es verdadera, puede resultar muy lenta si no se escribe de forma inteligente. Continúe leyendo si desea comprender la causa de los problemas o desplácese hasta el final de la página donde encontrará 10 consejos útiles para mejorar el rendimiento de las expresiones regulares en Java.

¿Es realmente tan lento?

Digamos que queremos seleccionar sólo líneas que contengan la secuencia de caracteres "a" y "b". La solución correcta podría ser: (a*b*)* Sin embargo, si ejecuta la expresión con, por ejemplo, la cadena “aaaaaaaaaaaaaaaaaaaaaaaaaaaaax”, pasarán varios minutos antes de que finalice y no informe coincidencias. Por supuesto, la mejor expresión regular en este caso sería: (a|b)* Esto toma menos de un milisegundo en mi máquina con la misma cadena. Claramente hay un problema de rendimiento aquí.

¿Por qué está pasando esto?

Como la mayoría de los motores de expresiones regulares, Java utiliza un enfoque NFA (autómatas finitos no deterministas). El motor escanea los componentes de expresiones regulares uno por uno y avanza a través de la cadena de entrada en consecuencia. Y puede volver al principio para encontrar alternativas apropiadas si llega a un “callejón sin salida”. Se obtienen resultados alternativos utilizando estructuras regulares como cuantificadores ( *, +, ? ) y alternancias (por ejemplo, a|b|c|d ). Esta técnica de investigación se llama retroceso. En el terrible ejemplo anterior, el motor revisará TODAS las descomposiciones en serie del símbolo "a" en series más pequeñas hasta que se dé cuenta de que no hay coincidencias. Este ejemplo muestra cómo el algoritmo de retroceso puede dar como resultado una estimación de tiempo exponencial (dependiendo de la longitud de la cadena de entrada). Esto también muestra una propiedad importante de la NFA: siempre habrá peores casos que casi coincidan con el patrón. Si se encuentra una coincidencia, la búsqueda se detiene. El otro enfoque principal para su uso en expresiones regulares es DFA (autómata finito determinista). En este enfoque, la expresión regular en realidad construye un autómata que se utiliza para recorrer las cadenas de entrada carácter por carácter sin retroceder. Esto le da tiempo lineal a toda la entrada, independientemente de la complejidad de la expresión regular. En lugar de escanear secuencialmente una cadena en busca de coincidencias (como en NFA), DFA simula el escaneo paralelo. Entonces, ¿por qué Java (y .NET, Perl, Python, Ruby, PHP, etc.) usan NKA y no DKA, que tiene un comportamiento mucho mejor? La razón es que la NKA tiene una serie de ventajas importantes:

Compila más rápido y requiere mucha menos memoria
Permite algunas funciones útiles (consulte el tutorial de Sun para obtener más detalles ):

Captura de grupo y vínculos de retroceso
control posicional
Cuantificadores extendidos (codiciosos y perezosos)

Es importante señalar que los términos populares NKA y DKA son imprecisos cuando se usan en el contexto de expresiones regulares. En teoría, estos dos modelos tienen la misma potencia informática. Esto significa que no se puede escribir una expresión regular en un modelo de autómata que sería imposible expresar en otro. En la práctica, se necesitan más capacidades para que los dos tipos de implementación diverjan en semántica. Los motores NKA brindan más flexibilidad, lo que los hace superiores a DKA en potencia informática. Debido a la velocidad de DFA y las características únicas de NFA, existen dos formas más "prefabricadas" de implementar expresiones regulares. Algunas implementaciones utilizan ambos tipos (por ejemplo, GNU egrep, que selecciona un motor específico en tiempo de ejecución), y algunas han logrado implementar una versión verdaderamente híbrida (por ejemplo, Tcl regexps) con todos los beneficios.

Consejos

Los siguientes son algunos consejos sobre cómo evitar problemas de eficiencia de expresiones regulares en Java. Muchos de ellos tienen como objetivo reducir los retornos.

1) Pre-compilación

Trillado, pero digno de mención. Si usa la expresión regular más de una vez, asegúrese de compilarla con anticipación:

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) Cuantificadores perezosos versus cuantificadores codiciosos

De forma predeterminada, los cuantificadores ( * + ? ) son codiciosos. Esto significa que comienzan a emparejar con la secuencia más larga posible y luego retroceden gradualmente si es necesario. Si sabe de antemano que las coincidencias normalmente serán cortas, debe utilizar cuantificadores diferidos. Comienzan con la cerilla más pequeña y avanzan más si es necesario. Digamos que queremos encontrar sólo líneas que coincidan con la secuencia "hola". El .*hello.* normal hará todo bien, pero si sabemos que "hello" suele aparecer más cerca del principio del texto, entonces .*?hello.* funcionará más rápido en promedio.

3) Utilice cuantificadores súper codiciosos siempre que sea posible

A diferencia de los cuantificadores perezosos, que afectan el rendimiento pero no el comportamiento normal, los cuantificadores súper codiciosos pueden en realidad cambiar el significado de una expresión regular. Cuando se usa *+ en lugar de * , la primera coincidencia será codiciosa (es decir, la más grande posible como si fuera solo *), pero no habrá respaldo si falla, incluso si esto hace que falle toda la búsqueda. ¿Cuándo podría resultar útil? Digamos que necesitamos encontrar texto entre comillas. El \"[^\"]*\" normal funcionará bien. Sin embargo, hará sangrías innecesarias en casos negativos (por ejemplo, “bla bla bla). El uso de \"[^\"]*+\" eliminará retrocede sin cambiar el significado de la expresión. La agrupación independiente logra el mismo efecto y brinda aún más control (consulte el tutorial de Sun ).

4) Evite la captura grupal

Cualquier expresión entre paréntesis se considera un grupo de forma predeterminada. Esto tiene un pequeño impacto en el rendimiento. Haga que sus grupos sean "inatrapables" siempre que sea posible iniciándolos con (?: en lugar de ( .

5) Utilice el intercalado con prudencia

Cuando se utiliza el intercalado (por ejemplo, Paul|Jane|Chris ), el orden en el que el motor intenta hacer coincidir las opciones es el mismo que el orden en que aparecen. Puede aprovechar esta función y colocar las opciones más comunes más cerca del principio. Esto mejorará el tiempo promedio de respuesta positiva.

6) Evite la ambigüedad

Escriba expresiones regulares de tal manera que minimice el número de coincidencias diferentes en la cadena de entrada. Por ejemplo: la expresión regular (a*b*)* dada al principio del artículo permite que la cadena "aabb" se interprete de muchas maneras: (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)*, por otro lado, solo interpreta expresiones únicas combinaciones positivamente. Esto es muy importante para reducir los retornos en casos casi coincidentes.

7) Vista previa

La vista previa le permite agregar restricciones en secuencias a la izquierda/derecha de la posición actual. En particular, con una búsqueda anticipada negativa, puedes buscar líneas que no contengan alguna secuencia (¡qué haríamos sin esto!). ¿Cómo puede esto ayudar a aumentar la productividad? Digamos que queremos tomar la URL de la etiqueta del enlace. Considere la siguiente expresión regular: a .* href=(\S*).*/ para etiquetas normales, esta expresión solo coincidirá con la dirección si el texto contiene el atributo "href" (\S se usa para todos los caracteres excepto los delimitadores). Pero en algunas etiquetas inusuales, por ejemplo, se producirá una reversión. Por ejemplo: “a href= href=href=…. href=algo.” La siguiente expresión regular evitará que esto suceda al reemplazar “.*” en una expresión con algo que no coincida con “href”: a ((?!href).)* href=(\S*)((?!href).)*/

8) Especifique la longitud

Java contiene un optimizador de expresiones regulares que compara la longitud de la cadena de entrada con las longitudes mínima y máxima obtenidas de la expresión regular. Esto le permite dejar de buscar inmediatamente en algunos casos. Para ayudar a este mecanismo, se debe especificar el número de repeticiones siempre que sea posible (por ejemplo, [01]{6} coincide con todas las cadenas binarias de seis caracteres de longitud).

9) Seleccione líneas idénticas

A veces, cadenas que son iguales están ocultas dentro de grupos o alternativas: (hello|hell|heel) Esta expresión se puede simplificar a: he(llo|ll|el) Al hacer esto, le damos más información al optimizador de expresiones regulares.

10) Prueba tu expresión regular

Puede ser conveniente probar primero la expresión regular cuando se vaya a utilizar en una aplicación de rendimiento crítico. Escriba un micro punto de referencia que pruebe su expresión en varios datos de entrada. Asegúrese de realizar pruebas con datos de diferentes longitudes y también con datos que coincidan estrechamente con su muestra.

Enlaces:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -de-procesamiento-de-expresión/