¿Por qué esto tarda tanto en emparejar? ¿Es un error?

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 hubiera partidos.

Esta expresión, sin embargo, se ejecuta casi inmediatamente (note la barra diagonal final):

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

¿Es esto un error?

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


    La forma más fácil de lograr esto es simplemente buscar 1+ dígitos o comas seguidos de una barra y el final de la cadena: [\d,]+/$ . Sin embargo, eso no es perfecto, ya que permitiría algo como ,123,,4,5/ .

    Para esto puedes usar una versión ligeramente optimizada de tu bash inicial: (?:\d,?)+/$ . Primero, hice que tu grupo de repetición no capturara ( (?:...) ) que no es necesario pero proporciona una “coincidencia más limpia”. A continuación, y como único paso crucial, dejé de repetir el \d dentro del grupo porque el grupo ya se está repitiendo. Finalmente, eliminé el grupo innecesario alrededor del opcional , ya que ? Solo afecta al último personaje. Más o menos, esto buscará un dígito, tal vez una coma, luego se repetirá, y finalmente se seguirá con un final / .


    Esto aún puede coincidir con una cadena impar 1,2,3,/ , por lo que mejoré su regex original con un aspecto negativo detrás de : (?:\d,?)+(? ,? (?:\d,?)+(? . Esto afirmará que no hay una coma directamente antes del final / .

    En primer lugar, debo decir que no es un error . Es por eso que intenta todas las posibilidades, toma tiempo y recursos informáticos. A veces se puede engullir mucho tiempo. Cuando se pone muy 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 puede ver, solo use la función compile () , así que se basa en la función _compile() que en realidad usa Traditional NFA que Python usa para su coincidencia de expresiones regulares, y se basa en esta breve explicación sobre el retroceso en expresiones regulares en Mastering Regular Expressions, tercera edición , por Jeffrey EF Friedl !

    La esencia de un motor 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 volver más tarde si es necesario. Las situaciones en las que tiene que decidir entre cursos de acción incluyen cualquier cosa con un cuantificador (decidir si probar otra coincidencia) y alternancia (decidir qué alternativa nativa probar y cuáles dejar para más adelante). Cualquiera que sea el curso de acción que se intente, si tiene éxito y el rest de la expresión regular también tiene éxito, el emparejamiento habrá finalizado. Si algo en el rest de la expresión regular finalmente falla, el motor de la expresión regular sabe que puede retroceder hasta donde eligió la primera opción, y puede continuar con la coincidencia probando la otra opción. De esta manera, eventualmente intenta todas las posibles permutaciones de la expresión regular (o al menos tantas como sea necesario hasta que se encuentre una coincidencia).

    Vayamos 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 su cadena ( 12345121 ) coincide con \d+ , luego , ¿coincide con (,)? .
    • Luego, basado en el primer paso, toda la cadena coincide con + después de la agrupación ( (\d+(,)?)+ )
    • Luego, al final, no hay nada para /$ para igualar. Por lo tanto, (\d+(,)?)+ Necesita “retroceder” a un carácter antes del último para la comprobación de /$ . Nuevamente, no encuentra ninguna coincidencia adecuada, por lo tanto, después de eso , es el turno de ( , ) de retroceder, luego \d+ retrocederá, y esta retroceso continuará hasta que devuelva None . Por lo tanto, en función de la longitud de la cadena, lleva tiempo, lo que en este caso es muy alto, ¡y crea un cuantificador totalmente nested !

    Como una evaluación comparativa aproximada, en este caso, tiene 39 caracteres, por lo que necesita 3 ^ 39 bashs de retroceso (tenemos 3 métodos para retroceder).

    Ahora para una mejor comprensión, mido el tiempo de ejecución del progtwig 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 

    Entonces, para evitar este problema, puede utilizar una de las siguientes formas :

    • Agrupación atómica (actualmente no se admite en Python, se creó una RFE para agregarla a Python 3)
    • Reduzca la posibilidad de retroceso al dividir los grupos nesteds en expresiones regulares separadas.

    Para evitar el retroceso catastrófico sugiero

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