python - ¿Por qué esto toma tanto tiempo para que coincida? ¿Es un error?

regex performance

Question

Necesito hacer coincidir ciertas URL en la aplicación web, es decir, /123,456,789 , y escribí esta expresión regular para que coincida con el patrón:

r''(/d+(,)?)+/$''

Noté que no parece evaluar, incluso después de varios minutos al probar el patrón:

re.findall(r''(/d+(,)?)+/$'', ''12345121,223456,123123,3234,4523,523523'')

El resultado esperado sería que no hubo coincidencias.

Esta expresión, sin embargo, se ejecuta casi de inmediato (observe la barra inclinada final):

re.findall(r''(/d+(,)?)+/$'', ''12345121,223456,123123,3234,4523,523523/'')

¿Es esto un error?

Answer 1

Se está produciendo un retroceso catastrófico que causará una cantidad exponencial de procesamiento dependiendo de la longitud de la cadena que no es coincidente. Esto tiene que ver con las repeticiones anidadas y la coma opcional (aunque algunos motores de expresiones regulares pueden determinar que esto no coincidiría con intentar todas las repeticiones extrañas). Esto se resuelve optimizando la expresión.

La forma más sencilla de lograr esto es buscar más de un dígito o comas seguido de una barra inclinada y el final de la cadena: [/d,]+/$ . Sin embargo, eso no es perfecto ya que permitiría algo así como ,123,,4,5/ .

Para esto puedes usar una versión ligeramente optimizada de tu intento inicial: (?:/d,?)+/$ . Primero, hice que tu grupo de repetición no capturara ( (?:...) ), lo que no es necesario pero proporciona una "compatibilidad más limpia". Luego, y el único paso crucial, dejé de repetir el /d dentro del grupo ya que el grupo ya está repitiendo. Finalmente, eliminé el grupo innecesario alrededor del opcional , ? desde entonces ? solo afecta al último personaje. Casi todo esto buscará un dígito, tal vez una coma, luego repetirá, y finalmente seguido por un seguimiento / .

Esto todavía puede coincidir con una cadena impar 1,2,3,/ , así que, por pura casualidad, mejoré tu expresión regular original con un aspecto negativo detrás : (?:/d,?)+(?<!,)/$ ,? (?:/d,?)+(?<!,)/$ . Esto afirmará que no hay coma directamente antes del final / .

Answer 2

Para evitar el retroceso catastrófico, sugiero

r''/d+(,/d+)*/$''

Answer 3

En primer lugar, debo decir que no es un ERROR . es por eso, intenta todas las posibilidades, toma tiempo y recursos informáticos. A veces puede engullir mucho tiempo. Cuando se pone realmente mal, se llama retroceso catastrófico .

Este es el código de la función findall en el código fuente de Python :

 def findall(pattern, string, flags=0):
    """Return a list of all non-overlapping matches in the string.
    If one or more groups are present in the pattern, return a
    list of groups; this will be a list of tuples if the pattern
    has more than one group.
    Empty matches are included in the result."""
    return _compile(pattern, flags).findall(string)

Como ve, solo use la función compile () , basada en la función _compile() que usa Traditional NFA que usa python para su correspondencia con expresiones regulares, y base en esta breve explicación sobre retroceso en expresiones regulares en Mastering Regular Expressions, Tercera Edición , por Jeffrey EF Friedl !

La esencia de un motor de NFA es la siguiente: considera cada subexpresión o componente a su vez, y cada vez que necesita decidir entre dos opciones igualmente viables, selecciona una y recuerda la otra para regresar luego si es necesario. Las situaciones donde tiene que decidir entre cursos de acción incluyen cualquier cosa con un cuantificador (decida si probar otra coincidencia) y alternancia (decida qué alternativa nativa probar, y cuál dejar para más adelante). Independientemente del curso de acción que se intente, si tiene éxito y el resto de la expresión regular también es exitoso, la coincidencia habrá finalizado. Si algo en el resto de la expresión regular finalmente causa un error, el motor de expresiones regulares sabe que puede retroceder a donde eligió la primera opción, y puede continuar con la coincidencia probando la otra opción. De esta forma, eventualmente intenta todas las permutaciones posibles de la expresión regular (o al menos tantas como sea necesario hasta encontrar una coincidencia).

Vamos dentro de tu patrón : Entonces, tienes r''(/d+(,)?)+/$'' Con esta cadena ''12345121,223456,123123,3234,4523,523523'' tenemos estos pasos:

• Al principio, la primera parte de la cadena ( 12345121 ) se 12345121 con /d+ , luego , se combina con (,)? .
• Luego, basado en el primer paso, toda la cadena se empareja debido a + después de la agrupación ( (/d+(,)?)+ )
• Luego, al final, no hay nada para que /$ sea ​​emparejado. Por lo tanto, (/d+(,)?)+ Necesita "retroceder" a un carácter antes del último para verificar /$ . De nuevo, no encuentra ninguna coincidencia adecuada, por lo tanto, después de eso, (es) volver atrás, luego /d+ retrocederá, y este retroceso continuará hasta que devuelva None . Por lo tanto, en función de la longitud de la cadena, lleva tiempo, que en este caso es muy alta, ¡y crea un cuantificador anidado por completo !

Como un punto de referencia aproximado, en este caso, tiene 39 caracteres, por lo que necesita 3 ^ 39 intentos de rastreo (tenemos 3 métodos para dar marcha atrás).

Ahora, para una mejor comprensión, mido el tiempo de ejecución del programa mientras cambio la longitud de la cadena:

''12345121,223456,123123,3234,4523,'' 3^33 = 5.559060567×10¹⁵
~/Desktop $ time python ex.py

real    0m3.814s
user    0m3.818s
sys     0m0.000s

''12345121,223456,123123,3234,4523,5'' 3^24 = 1.66771817×10¹⁶ #X2 before
~/Desktop $ time python ex.py

real    0m5.846s
user    0m5.837s
sys     0m0.015s

''12345121,223456,123123,3234,4523,523'' 3^36= 1.500946353×10¹⁷ #~10X before 
~/Desktop $ time python ex.py

real    0m15.796s
user    0m15.803s
sys     0m0.008s

Para evitar este problema, puede usar una de las siguientes formas :

• Agrupación atómica (Actualmente no es compatible con Python, se creó un RFE para agregarlo a Python 3)
• Reduce la posibilidad de retroceder rompiendo los grupos anidados para separar las expresiones regulares.