100% de uso de CPU con una expresión regular dependiendo de la longitud de entrada

Question

Estoy tratando de encontrar una expresión regular en Python que tenga que coincidir con cualquier carácter pero evitando tres o más comas consecutivas o puntos y comas. En otras palabras, solo se permiten hasta dos comas o puntos y coma consecutivos.

Así que esto es lo que tengo actualmente:

^(,|;){,2}([^,;]+(,|;){,2})*$ 

Y parece que funciona como se esperaba:

>>> r.match('') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, a') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, ,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, ,,a') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, ,,,') 
>>> r.match('foo, ,,,;') 
>>> r.match('foo, ,, ;;') 
<_sre.SRE_Match object at 0x7f23af840750> 

Pero cuando me preparo para aumentar la longitud del texto de entrada, la expresión regular parece necesitar mucho más tiempo para dar una respuesta.

>>> r.match('foo, bar, baz,, foo') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,') 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,,') 
>>> r.match('foo, bar, baz,, fooooo, baaaaar, baaaaaaz,,,,') 

Y, finalmente, se queda completamente atascado en esta etapa y el uso de la CPU aumenta al 100%.

No estoy seguro si la expresión regular podría ser optimizada o hay algo más involucrado, cualquier ayuda apreciada.

Answer 1

Te encuentras con catastrophic backtracking.

La razón de esto es que se han hecho los separadores opcional, y por lo tanto la parte [^,;]+ (que es en sí mismo en un grupo de repetición) de su expresión regular va a tratar cargas de permutaciones (de baaaaaaaz) antes de finalmente tener que admitir el fracaso cuando enfrentado con más de dos comas.

RegexBuddy aborta el intento de coincidencia después de 1.000.000 de pasos del motor de expresiones regulares con su última cadena de prueba. Python seguirá intentándolo.

Imagínese la cadena baaz,,,:

Tratando su expresión regular, el motor de expresiones regulares que verificar todas estas cosas:

1. baaz,,<failure>
2. baa + z,,<failure>
3. ba + az,,<failure>
4. ba + a + z,,<failure>
5. b + aaz,,<failure>
6. b + aa + z,,<failure>
7. b + a + az,,<failure>
8. b + a + a + z,,<failure>

antes de declarar el fracaso general. ¿Ves cómo esto crece exponencialmente con cada personaje adicional?

Comportamiento como este se puede evitar con cuantificadores posesivos o grupos atómicos, los cuales lamentablemente no son compatibles con el motor de expresiones regulares de Python. Pero puede hacer una comprobación inversa fácilmente:

if ",,," in mystring or ";;;" in mystring: 
    fail() 

sin necesidad de una expresión regular en absoluto. Si ,;, y los "me gusta" también pueden ocurrir y deben ser excluidos, entonces use la solución de Andrew.

Answer 2

Prueba esta expresión regular:

^([^,;]|,($|[^,]|,[^,])|;($|[^;]|;[^;]))*$ 

Coincide con repetitivamente:

• un único personaje que no es ni , ni ; o
• un , que o bien no está seguido por otro , o un ,, que no es seguido por otro ,, o
• un ; que está o bien no seguido por otro ; o una ;; que no está seguido por otro ;

hasta que se alcanza el final. Es muy eficiente ya que falla temprano sin hacer mucho retroceso.

Answer 3

creo que el siguiente debe hacer lo que quiera:

^(?!.*[,;]{3}) 

Esto se producirá un error si la cadena contiene tres o más , o ; en una fila. Si realmente desea que coincida con un personaje, agregue un . al final.

Esto utiliza negative lookahead, lo que hará que la coincidencia completa falle si la expresión regular .*[,;]{3} coincidiría.

Answer 4

¿Qué tal esta idea coinciden con las que tienen el patrón que no desea ".+,,," En Python solo guarde las que no coincidan. Debe ser rápido