Expresión regular cuelga el programa (100% de uso de la CPU)

Question

Java se cuelga con el uso de la CPU al 100% cuando uso la siguiente cadena como entrada para una expresión regular.

RegEx usados:

Aquí es la expresión regular utilizada para el campo de descripción en mi solicitud.

^([A-Za-z0-9\\-\\_\\.\\&\\,]+[\\s]*)+ 

cadena que se utiliza para la prueba:

SaaS Servicio de VLAN Provider_One
segundo intento con Didier SPT porque el primero que me dio fue mal :-(

Funciona correctamente cuando divido la misma cadena en diferentes combinaciones. Al igual que "Servicio de SaaS VLAN de Provider_One", "el primero que me dio fue incorrecto :-(", etc. Java es Hangi ng solo para la cadena dada anteriormente.

También intenté optimizar la expresión regular como a continuación.

^([\\w\\-\\.\\&\\,]+[\\s]*)+ 

Incluso con esto no está funcionando.

Answer 1

En primer lugar, debe tener en cuenta que sus expresiones regulares NO PUEDEN coincidir con la cadena de entrada suministrada. Las cadenas contienen un número de caracteres ('<' '>' '/' ':' y ')') que no son caracteres de "palabra".

Entonces, ¿por qué tarda tanto?

Básicamente "retroceso catastrófico". Más específicamente, las estructuras repetitivas de su expresión regular dan un exponencial número de alternativas para el algoritmo de retroceso regex.

Esto es lo que dice su expresión regular:

1. Uno o más caracteres de palabra
2. seguido de cero o más caracteres de espacio
3. Repetir los 2 patrones anteriores tantas veces como desee.

El problema es con la parte "cero o más caracteres de espacio". La primera vez, el emparejador hará coincidir todo hasta el primer carácter inesperado (es decir, el '<'). Luego retrocederá un poco y volverá a intentarlo con una alternativa diferente ... que implica "cero espacios" antes de la última letra, y cuando eso falle, moverá los "espacios cero" a una posición.

El problema es que para la secuencia con N caracteres no espacio, no como N lugares diferentes que "cero espacios" pueden ser emparejados, y que hace que 2^N combinaciones diferentes. Eso se convierte rápidamente en un número ENORME como N crece, y el resultado final es difícil de distinguir de un ciclo infinito.

Answer 2

Otro caso clásico de catastrophic backtracking.

Has anidado cuantificadores que causan un número gigantesco de permutaciones para comprobar la expresión regular cuando llega a la : en su cadena de entrada que no es parte de su clase de caracteres (asumiendo que usted está utilizando el método .matches()).

Vamos a simplificar el problema a esta expresión regular:

^([^:]+)+$ 

y esta cadena:

1234: 

El motor de expresiones regulares tiene que comprobar

1234 # no repetition of the capturing group 
123 4 # first repetition of the group: 123; second repetition: 4 
12 34 # etc. 
12 3 4 
1 234 
1 23 4 
1 2 34 
1 2 3 4 

... y eso es sólo para cuatro personajes. En su cadena de muestra, RegexBuddy aborta después de 1 millón de intentos. Java seguirá felizmente ... antes de admitir finalmente que ninguna de estas combinaciones permite que coincida el siguiente :.

¿Cómo se puede resolver esto?

Usted puede prohibir la expresión regular de dar marcha atrás mediante el uso de possessive quantifiers:

^([A-Za-z0-9_.&,-]++\\s*+)+ 

permitirá la expresión regular a fallar más rápido. Por cierto, eliminé todas esas barras invertidas innecesarias.

Editar:

Unas mediciones:

En la cadena "was wrong :-)", se necesita RegexBuddy 862 pasos para encontrar una no coincidencia.
Para "me was wrong :-)", son 1.742 pasos.
Para "gave me was wrong :-)", 14,014 pasos.
Para "he gave me was wrong :-)", 28,046 pasos.
Para "one he gave me was wrong :-)", 112,222 pasos.
Para "first one he gave me was wrong :-)",> 1,000,000 pasos.

Answer 3

¿Por qué haces coincidir los espacios en blanco por separado de los otros caracteres? ¿Y por qué anclan el partido al principio, pero no al final? Si desea asegurarse de que la cadena no se inicia o termina con un espacio en blanco, usted debe hacer algo como esto:

^[A-Za-z0-9_.&,-]+(?:\s+[A-Za-z0-9_.&,-]+)*$ 

Ahora sólo hay un motor de expresiones regulares "camino" puede tomar a través de la cadena. Si se agota el número de caracteres que coinciden con [A-Za-z0-9_.&,-] antes de llegar al final y el siguiente carácter no coincide con \s, falla inmediatamente. Si llega al final sin dejar de coincidir con los espacios en blanco, falla porque es necesario que coincida con al menos un carácter que no sea de espacios en blanco después de cada ejecución de espacios en blanco.

Si desea asegurarse de que no es exactamente un carácter de espacio en blanco que separa las carreras de no está en blanco, basta con retirar el cuantificador de \s+:

^[A-Za-z0-9_.&,-]+(?:\s[A-Za-z0-9_.&,-]+)*$ 

Si no les importa donde el espacio en blanco es en relación con el no está en blanco, al igual que coincida con todos ellos con la misma clase de caracteres:

^[A-Za-z0-9_.&,\s-]+$ 

Asumo que sabe que su expresión regular no coincidirá con la entrada dada por la : y ( en el SMI ley, y solo quieres saber por qué tardas tanto en fallar.

Y, por supuesto, ya que va a crear la expresión regular en la forma de una cadena literal de Java, podría escribir:

"^[A-Za-z0-9_.&,-]+(?:\\s+[A-Za-z0-9_.&,-]+)*$" 

o

"^[A-Za-z0-9_.&,-]+(?:\\s[A-Za-z0-9_.&,-]+)*$" 

o

"^[A-Za-z0-9_.&,\\s-]+$" 

(Sé que tuviste barras invertidas dobles en la pregunta original, pero eso fue probablemente solo para mostrarlas correctamente ya que no estaba usando la excelente función de formato de código de SO.)