solo - extraer cadenas con expresiones regulares java

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

Question

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

RegEx utilizado:

Aquí está la expresión regular utilizada para el campo de descripción en mi aplicación.

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

Cadena utilizada para la prueba:

SaaS Service VLAN de Provider_One
Segundo intento con Didier SPT porque el primero que me dio estaba mal :-(

Funciona correctamente cuando divido la misma cadena en diferentes combinaciones. Como "SaaS Service VLAN from Provider_One", "el primero que me dio estaba equivocado :-(", etc. Java solo se cuelga para la cadena dada arriba.

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

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

Incluso con esto no funciona.

Answer 1

¿Por qué coinciden los espacios en blanco por separado de los otros personajes? ¿Y por qué estás anclando el partido al principio, pero no al final? Si desea asegurarse de que la cadena no comience o termine con espacios en blanco, debe hacer algo como esto:

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

Ahora solo hay una "ruta" que el motor de expresiones regulares puede tomar a través de la cadena. Si se queda sin caracteres que coincidan con [A-Za-z0-9_.&,-] antes de llegar al final, y el siguiente carácter no coincide con /s , falla de inmediato. Si llega al final mientras aún coinciden los caracteres de espacio en blanco, falla porque es necesario que coincida con al menos un carácter que no sea de espacio en blanco después de cada ejecución de espacio en blanco.

Si desea asegurarse de que exista exactamente un carácter de espacio en blanco que separa las ejecuciones de espacio no en blanco, simplemente elimine el cuantificador de /s+ :

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

Si no te importa dónde está el espacio en blanco en relación con el espacio no en blanco, solo haz que coincidan con la misma clase de caracteres:

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

Supongo que sabe que su expresión regular no coincidirá con la entrada dada debido a : y ( en el emoticono, y solo quiere saber por qué demora tanto en fallar).

Y, por supuesto, ya que está creando la expresión regular en forma de un literal de cadena Java, escribiría:

"^[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 tenía doble barra diagonal inversa en la pregunta original, pero probablemente fue solo para que se muestren correctamente, ya que no estaba usando la excelente función de formato de código de SO).

Answer 2

Otro caso clásico de retroceso catastrófico .

Tiene cuantificadores anidados que hacen que se verifique un número gigantesco de permutaciones cuando llegue la expresión regular a : en la cadena de entrada que no forma parte de su clase de caracteres (suponiendo que esté usando el método .matches() ).

Simplifiquemos el problema a esta expresión regular:

^([^:]+)+$

y esta cadena:

1234:

El motor regex necesita 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 solo para cuatro personajes. En su cadena de muestra, RegexBuddy se cancela después de 1 millón de intentos. Java se mantendrá feliz de chugging ... antes de finalmente admitir que ninguna de estas combinaciones permite lo siguiente : coincidir.

¿Cómo puedes resolver esto?

Puede prohibir el regex de retroceso mediante el uso de cuantificadores posesivos :

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

permitirá que la expresión regular falle más rápido. Por cierto, quité todas esas barras invertidas innecesarias.

Editar:

Algunas medidas:

En la cadena "was wrong :-)" , se necesitan pasos de RegexBuddy 862 para descubrir una no coincidencia.
Para "me was wrong :-)" , son 1,742 pasos.
Para "gave me was wrong :-)" , 14,014 pasos.
Por "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

Primero, debe darse cuenta de 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é está tomando tanto tiempo?

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

Esto es lo que dice su expresión regular:

1. Uno o más caracteres de palabras
2. Seguido por cero o más caracteres de espacio
3. Repite los 2 patrones anteriores tantas veces como quieras.

El problema es con la parte de "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 involucra "cero espacios" antes de la última letra, luego, cuando eso falla, moverá los "cero espacios" una posición.

El problema es que para la cadena con N sin espacio, hay N lugares diferentes en los que se pueden hacer coincidir los "espacios cero", y eso hace que 2^N combinaciones diferentes. Eso se convierte rápidamente en un número ENORME a medida que N crece, y el resultado final es difícil de distinguir de un bucle infinito.