El desafío del Backtracker: codicioso, perezoso y posesivo

Por la mañana hay un sobre negro encajado en la rendija de la puerta. Dentro, una sola tarjeta. La directora la levanta a contraluz y luego la deja sobre el escritorio. «Por fin se presenta. Con una firma en lugar de una cara».

^(a|aa)+$

이 패턴은 정답을 맞힌다. 그런데 왜 이렇게 느린가?
답은 패턴으로 보내라.
                                        (a+)+$

La tarjeta está escrita en coreano: «Este patrón acierta. Entonces, ¿por qué es tan lento? Responde con un patrón».

«Para resolverlo hay que saber cómo piensa un motor de regex», dice la directora. «Hoy vamos a asomarnos a su cabeza».

8-1. El motor prueba desde el principio y, si se atasca, retrocede (10 min)

El motor de regex va encajando el patrón en la cadena pieza a pieza, de izquierda a derecha. Si algo no encaja, no se rinde enseguida: deshace la última decisión que tomó y prueba otro camino. A esto se le llama retroceso (backtracking).

En la lección 3 vimos que los cuantificadores, por defecto, «comen todo lo que pueden» (son codiciosos). Veamos qué pasa al extraer etiquetas de un HTML.

html = "<b>bold</b> and <i>it</i>"
re.findall(r"<.+>", html)   # ['<b>bold</b> and <i>it</i>']

En lugar de cuatro etiquetas, se capturó toda la línea de una vez. Si seguimos lo que hizo el motor, queda así:

1. < encaja con el primer <.
2. .+ es codicioso y se come hasta el final de la línea.
3. Ahora toca encajar el > del patrón, pero no queda ningún carácter. Fallo.
4. .+ va devolviendo los caracteres de uno en uno y vuelve a intentarlo. En cuanto recupera el último >, lo consigue.

El resultado va «desde el < más exterior hasta el último >». El que se equivoca no es el motor, sino el patrón.

8-2. Cuantificadores perezosos: *? +? ?? {m,n}? (8 min)

Si añades ? detrás de un cuantificador, se convierte en un cuantificador perezoso (lazy), que come lo menos posible. Primero toma lo mínimo y solo come un carácter más cuando lo que sigue no encaja.

re.findall(r"<.+?>", html)          # ['<b>', '</b>', '<i>', '</i>']
re.findall(r"a+?", "aaa")           # ['a', 'a', 'a']
re.findall(r"a??", "a")             # ['', 'a', '']
re.search(r"\d{2,4}?", "12345").group()   # '12'

Un cuantificador perezoso cambia «dónde se detiene». Por eso viene bien para capturar en corto cosas con un final bien marcado, como las etiquetas.

8-3. El mismo problema, tres respuestas (4 min)

Pongamos lado a lado las formas de extraer etiquetas.

<[^>]+> usa la clase negada de la lección 2 y solo come «caracteres que no son >». Casi nunca tiene que retroceder, así que es la más rápida y la más clara. La directora lo resume así: «Mejor exacto que perezoso».

8-4. La respuesta al desafío: demasiados caminos de vuelta (8 min)

Ahora miremos el patrón de la tarjeta, ^(a|aa)+$. Busca «una cadena formada entera por una o más a seguidas». Significa lo mismo que ^a+$.

bool(re.fullmatch(r"^(a|aa)+$", "aaaa"))   # True
bool(re.fullmatch(r"^a+$", "aaaa"))        # True

El problema aparece cuando se encuentra con una cadena que no encaja. Si al final hay una b, como en aaaa…ab, el motor prueba todas las maneras de repartir las a entre a y aa antes de admitir el fallo. Y el número de repartos crece de forma explosiva con cada a que se añade.

Estos son los tiempos medidos en la computadora de la agencia (Python 3.14):

Cada 4 a más, es unas 7 veces más lento. A ese ritmo, con 40 a pasa con creces de los 10 segundos. Una repetición con opciones que se solapan es la forma típica que hace explotar el retroceso. Las repeticiones dentro de repeticiones, como (a+)+, son de la misma familia.

8-5. Cuantificadores que no devuelven nada: *+ ++ ?+ {m,n}+ (6 min)

Desde Python 3.11, si añades + detrás de un cuantificador obtienes un cuantificador posesivo. Lo que se ha comido no lo devuelve aunque lo que sigue falle. Elimina de raíz los caminos de vuelta.

re.fullmatch(r"a*a", "aaa")    # <re.Match object; span=(0, 3), match='aaa'>
re.fullmatch(r"a*+a", "aaa")   # None

a*+a no coincide con ninguna cadena. a*+ se queda con todas las a y no las devuelve, así que a la a final no le queda nada con que encajar. Pero justamente esa propiedad permite arreglar el patrón de la tarjeta.

re.search(r"^(?:a|aa)++$", "a" * 28 + "b")   # None (termina al instante)

++ hace posesiva la repetición del grupo: si falla, no prueba otros repartos y se rinde enseguida.

8-6. Grupos que no devuelven nada: (?>...) (4 min)

El grupo atómico (atomic group) (?>...) también existe desde la 3.11. Cuando lo de dentro del grupo coincide una vez, ese resultado queda fijado en bloque y el motor ya no vuelve a entrar. De hecho, un cuantificador posesivo es una abreviatura de un grupo atómico: a++ equivale a (?>a+).

re.fullmatch(r"(?>a+)b", "aab")   # <re.Match object; span=(0, 3), match='aab'>
re.fullmatch(r"(?>a+)a", "aaa")   # None

Caso resuelto (10 min)

Preparas la respuesta con la directora. Hay tres maneras de arreglar un patrón lento.

1. Reescribirlo sin solapamientos. Que el mismo texto no se pueda repartir de varias maneras: ^a+$ en vez de ^(a|aa)+$.
2. Eliminar los caminos de vuelta. Con un cuantificador posesivo, ^(?:a|aa)++$, o un grupo atómico, ^(?>(?:a|aa)+)$.
3. Ponerle freno desde fuera. Limitar la longitud de la entrada y ejecutar los patrones ajenos solo donde haya un límite de tiempo. Eso es lo que hace este laboratorio al ejecutar el patrón en un proceso aparte y detenerlo si pasa de 0,3 s. (El paquete de terceros regex tiene un argumento timeout.)

import time
text = "a" * 40 + "b"
start = time.perf_counter()
print(re.search(r"^a+$", text))             # None
print(time.perf_counter() - start < 0.01)   # True

Escribes ^a+$ en el reverso de la tarjeta y la metes en el sobre. La directora asiente. «Corta, legible y rápida. Buena respuesta».

Ejercicios

1. Predice el resultado de re.findall(r'".+"', 'say "hi" and "yo"') y corrígelo de dos maneras (cuantificador perezoso y clase negada) para que capture cada cita entre comillas por separado.
2. Explica por qué (\d+)+$ tiene una forma peligrosa y escribe un patrón seguro que signifique lo mismo.
3. Si ejecutas findall con a{2,4}? y con a{2,4}+ sobre "aaaaa", ¿qué sale en cada caso? Compruébalo en el laboratorio.