💬 NLP

On the Complexity of the Matching Problem of Regular Expressions with Backreferences

Este artículo establece la complejidad computacional detallada de la coincidencia de expresiones regulares con referencias hacia atrás demostrando cotas inferiores condicionales bajo las hipótesis de SETH y detección de triángulos, al tiempo que presenta un algoritmo mejorado de $O(n \log^2 n)$ para referencias hacia atrás de un solo uso.

Autores originales: Soh Kumabe, Yuya Uezato

Publicado 2026-05-11

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Soh Kumabe, Yuya Uezato

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

La Gran Imagen: El Atasco de Tráfico de las "Regex"

Imagina que eres un guardia de seguridad en un club (el sistema informático). Tienes una lista de reglas (una Expresión Regular) sobre quién puede entrar.

Reglas Simples: "Solo personas con camisas rojas". Esto es fácil de verificar. Miras una camisa, dices "¿Roja? Sí, pasa". Toma la misma cantidad de tiempo si la fila tiene 10 personas o 10,000.
El Problema (ReDoS): A veces, los hackers diseñan una fila específica de personas que engaña al guardia para que realice una cantidad masiva de trabajo innecesario. En lugar de revisar a una persona y pasar a la siguiente, el guardia empieza revisando a la Persona A, luego a la Persona B, luego a la Persona A de nuevo, luego a la Persona C, luego a la Persona A otra vez... hasta que el guardia colapsa por agotamiento. Esto se llama un ataque de Denegación de Servicio (ReDoS).

En el mundo real, esto ha provocado que sitios web masivos como Stack Overflow y Cloudflare se caigan. El artículo señala que incluso una lentitud "cuadrática" (donde revisar 100 personas toma 10,000 pasos) es suficiente para colapsar un sistema.

El Villano: "Referencias hacia atrás"

Las reglas estándar son simples. Pero los motores modernos de "Regex" tienen una característica súper poderosa llamada Referencias hacia atrás.

La Analogía:
Imagina una regla que dice: "Encuentra una palabra, recuérdala y luego asegúrate de que la misma palabra exacta aparezca de nuevo más adelante".

Ejemplo: "Encuentra una palabra, llámala 'X'. Luego, encuentra 'X' de nuevo."
Si la entrada es manzana ... manzana, funciona.
Si la entrada es manzana ... plátano, falla.

Esta característica es increíblemente útil para los programadores, pero hace que el trabajo del "guardia" sea mucho más difícil. El guardia tiene que recordar lo que vio antes y compararlo constantemente con lo que está viendo ahora. El artículo pregunta: ¿Podemos construir un guardia que sea lo suficientemente rápido para manejar estas reglas complejas sin cansarse?

Los Hallazgos del Artículo: Lo Bueno, Lo Malo y Lo Feo

Los autores investigaron exactamente qué tan difícil es resolver estos problemas de emparejamiento. Lo desglosaron en dos lados: Dificultad (Por qué es difícil) y Algoritmos (Cómo solucionarlo).

1. Las Malas Noticias: Algunas Reglas son Imposibles de Acelerar

El artículo demuestra que para ciertos tipos de reglas complejas, no hay "bala mágica" para hacerlas rápidas.

El Problema del "Triángulo": Mostraron que si tienes una regla que usa dos variables (como recordar dos palabras diferentes y verificarlas más adelante), resolverlo es tan difícil como encontrar un triángulo en un gráfico gigante de una red social. Si pudieras resolver la regla rápidamente, podrías resolver el problema del gráfico rápidamente. Dado que los expertos en gráficos creen que el problema del gráfico es inherentemente lento, el problema de la regla también debe ser lento.
El Problema de los "Vectores Ortogonales": Para reglas con aún más variables, demostraron que el tiempo requerido crece exponencialmente con el número de variables. Es como intentar encontrar una combinación específica de llaves en una cerradura; cuantas más llaves tengas, más imposible se vuelve forzarlo rápidamente.

Conclusión: Si tu regla es demasiado compleja (usando muchas características de "recuerda esto"), no puedes construir un motor rápido para ella. Siempre te darás contra un muro.

2. Las Buenas Noticias: Una Solución "Casi Lineal" para Casos Simples

Sin embargo, el artículo encontró un punto dulce. Se centraron en un tipo específico y común de regla:

El Patrón "ABCBD": "Encuentra una palabra (A), luego una palabra (B), luego una palabra (C), luego la misma palabra B exacta de nuevo, luego una palabra (D)".
- Ejemplo del mundo real: "Encuentra un nombre de usuario, luego una contraseña, luego un mensaje, luego el mismo nombre de usuario de nuevo, luego una firma."

Los autores descubrieron que, aunque esto parece complicado, se puede resolver muy eficientemente.

La Vieja Forma: Los métodos anteriores eran como revisar cada combinación posible en una biblioteca, lo que tomaba un tiempo $O(n^2)$ (cuadrático). Si el libro tenía 1,000 páginas, tomaba 1,000,000 de pasos.
La Nueva Forma: Los autores construyeron un nuevo algoritmo que toma aproximadamente $O(n \log^2 n)$ $O (n lo g^{2} n)$ de tiempo.
- La Analogía: Imagina que la biblioteca está organizada con un sistema de índice mágico (usando Árboles de Sufijos y Bosques de Factorización). En lugar de leer cada página, el guardia puede saltar directamente a las secciones relevantes. Si el libro tiene 1,000 páginas, el nuevo método toma aproximadamente 10,000 pasos (o incluso menos), lo cual es una mejora masiva.

Cómo Funciona el Nuevo Algoritmo (Los "Trucos de Magia")

Para lograr esta velocidad, los autores utilizaron varias técnicas ingeniosas, que describen en el artículo:

El Árbol de Sufijos (El Mapa): Construyeron un mapa gigante de la cadena de entrada. Este mapa muestra cada posible final de la cadena. Ayuda al guardia a ver instantáneamente: "Oh, esta palabra 'B' aparece aquí, y también aparece allá".
Descomposición Pesada-Ligera (El Sombrero de Selección): Dividieron el mapa en caminos "pesados" (caminos muy comunes) y caminos "ligeros" (caminos raros). Solo realizan el trabajo pesado en los caminos raros, ahorrando tiempo.
Periodicidad (El Ritmo): Notaron que cuando una palabra se repite (como "B...B"), la cadena a menudo tiene un ritmo o un patrón. Usaron matemáticas para predecir estos patrones en lugar de revisar cada letra individual.
Bosques de Factorización (El Índice): Esta es una estructura de datos que actúa como un índice súper rápido, permitiendo al guardia verificar si un fragmento de texto coincide con una regla en tiempo constante, sin importar cuán largo sea el texto.

Resumen de la Conclusión

¿Podemos detener todos los ataques ReDoS? No. Si una regla es demasiado compleja (demasiadas variables de "recuerda esto"), está matemáticamente probado que será lenta.
¿Podemos arreglar las reglas complejas más comunes? ¡Sí! Para el caso específico donde una regla recuerda una palabra y la verifica una vez más tarde (el patrón "ABCBD"), los autores crearon un nuevo motor que es casi tan rápido como las reglas simples.
¿Por qué importa esto? Le dice a los ingenieros de software: "No uses demasiadas referencias hacia atrás, o serás lento. Pero si las usas de esta manera específica y común, ahora puedes usar nuestro nuevo método para mantener tu sistema seguro y rápido".

El artículo esencialmente traza una línea en la arena: Aquí es donde el límite de velocidad es inquebrantable, y aquí es donde encontramos una forma de conducir más rápido.

Resumen Técnico: Sobre la Complejidad del Problema de Coincidencia de Expresiones Regulares con Referencias Atrás

1. Definición del Problema y Motivación

El artículo investiga la complejidad computacional de grano fino del problema de coincidencia de Expresiones Regulares con Referencias Atrás (REWB). Mientras que las expresiones regulares clásicas (Regex) pueden coincidir en tiempo lineal respecto a la longitud de la cadena de entrada $|w|$ utilizando la construcción de Thompson, los motores prácticos admiten referencias atrás (por ejemplo, (E)x para capturar una subcadena y \x para reutilizarla). Esta característica extiende estrictamente el poder expresivo de las Regex (permitiendo el reconocimiento de lenguajes no regulares como $\{ww \mid w \in \Sigma^*\}$ ), pero introduce riesgos algorítmicos significativos.

La motivación surge de los ataques de Denegación de Servicio por Expresiones Regulares (ReDoS), donde adversarios diseñan entradas para desencadenar el comportamiento del peor caso en motores de coincidencia. Incidentes notables en Stack Overflow (2016) y Cloudflare (2019) demostraron que incluso un comportamiento de tiempo cuadrático ( $O(|w|^2)$ ) en motores basados en retroceso puede causar interrupciones catastróficas del servicio. Los autores plantean la pregunta fundamental: ¿Es posible construir motores seguros frente a ReDoS para REWB que se ejecuten en tiempo lineal o casi lineal?

El artículo se centra en $r$ -uso $k$ -REWB, definidos como expresiones con $k$ variables distintas donde el número total de ejecuciones de referencias atrás en cualquier cálculo está acotado por $r$ .

2. Metodología y Enfoque Técnico

El artículo emplea un enfoque dual: establecer cotas inferiores condicionales (dureza) y diseñar algoritmos eficientes para subclases específicas.

2.1 Resultados de Dureza

Los autores fortalecen resultados previos de complejidad reduciendo problemas conocidos difíciles a la coincidencia de REWB:

Dureza W[2]: Mediante la reducción del problema del $k$ -Conjunto Dominante, prueban que la coincidencia de REWB es W[2]-dura cuando se parametriza por el tamaño de la expresión $|E|$ . Esto fortalece el resultado conocido de dureza W[1].
Cotas Inferiores Condicionales (Detección de Triángulos): Asumiendo la "Hipótesis de No-Tiempo-Casi-Lineal" para la Detección de Triángulos, muestran que incluso el problema altamente restringido de 2-uso 2-REWB no puede resolverse en tiempo $O(|w|^{1+\delta})$ para cualquier $\delta > 0$ .
Cotas Inferiores Condicionales (k-OV): Bajo la hipótesis de $k$ -Vectores Ortogonales (k-OV) (más débil que SETH), prueban que la coincidencia de $k$ -REWB no puede resolverse en tiempo $O(|w|^{2k-\epsilon})$ . Esto implica que, para $k$ general, un tiempo casi lineal es improbable.

2.2 Resultados Algorítmicos

La contribución algorítmica principal se centra en 1-uso REWB (expresiones con una variable referenciada exactamente una vez).

Transformación a Forma Canónica: Los autores prueban que cualquier 1-uso REWB puede transformarse en una forma canónica que involucra una suma de términos como $A (B)_x C \backslash x D$ , donde $A, B, C, D$ son Regex clásicas. Esto se denomina el problema ABCBD.
Estrategia de Descomposición: El problema ABCBD se descompone en dos subproblemas:
1. Problema XYYZ: El caso donde las dos ocurrencias de $B$ son adyacentes ( $w = w_A w_B w_B w_D$ ). Esto se resuelve utilizando la enumeración de potencia local máxima de Crochemore y propiedades de conjuntos finalmente periódicos derivadas de monoides de transición.
2. Problema ABCBD Ramificado: El caso donde las dos ocurrencias de $B$ están separadas por una $C$ no vacía, y los caracteres que siguen inmediatamente a las dos ocurrencias de $B$ difieren.
Árbol de Sufijos y Descomposición Pesada-Ligera: Para el caso Ramificado, el algoritmo utiliza el árbol de sufijos de la cadena de entrada $w$ . Emplea descomposición pesada-ligera para particionar el espacio de búsqueda.
Estructuras de Datos:
- Bosques de Factorización: Se utilizan para evaluar la pertenencia a Regex en subcadenas en tiempo constante tras un preprocesamiento lineal.
- Monoides de Transición: Se aprovechan para rastrear el estado de las Regex $A, B, C, D$ de manera eficiente.
- Enumeradores Personalizados: Los autores diseñan estructuras de datos especializadas (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) para manejar la enumeración de transiciones. Estas estructuras utilizan actualizaciones perezosas y estrategias de unión de conjuntos disjuntos (DSU) para gestionar restricciones que varían con la longitud de la subcadena $w_B$ .

3. Resultados Clave

Dureza

Teorema 3: La coincidencia de REWB es W[2]-dura parametrizada por el tamaño de la expresión.
Teorema 4: Asumiendo la hipótesis de Detección de Triángulos, la coincidencia de 2-uso 2-REWB requiere tiempo superlineal (específicamente, no $O(|w|^{1+\delta})$ ).
Teorema 5: Bajo la hipótesis $k$ -OV, la coincidencia de $k$ -REWB requiere tiempo $\Omega(|w|^{2k-\epsilon})$ .

Algoritmos

Teorema 7 (Resultado Principal): El problema ABCBD admite un algoritmo de tiempo $O(|w| \log^2 |w|)$ . La constante oculta depende exponencialmente de los tamaños de las Regex $A, B, C, D$ ( $2^{O((|A|+|B|+|C|+|D|)^2)}$ ).
Teorema 8: En consecuencia, el problema de coincidencia de 1-uso REWB admite un algoritmo de tiempo $O(|w| \log^2 |w|)$ .
Teorema 9: El problema XY $\alpha$ Z (generalizando XYYZ a $\alpha$ repeticiones) admite un algoritmo de tiempo $O(|w| \log |w|)$ .

Estos resultados representan una mejora significativa sobre el algoritmo anterior de mejor conocimiento $O(|w|^2)$ para el problema ABCBD de Nogami y Terauchi (MFCS 2025).

4. Significado y Afirmaciones

El artículo afirma proporcionar una comprensión fundamental del panorama de complejidad para la coincidencia de REWB:

Seguridad ReDoS: Establece que, aunque la coincidencia general de REWB es probablemente intratable para tiempos casi lineales, una subclase relevante en la práctica (1-uso REWB) puede coincidir en tiempo casi lineal. Esto sugiere que los motores que soportan referencias atrás de un solo uso podrían teóricamente hacerse seguros frente a ReDoS.
Complejidad de Grano Fino: El trabajo delimita la frontera entre casos tratables e intratables. Muestra que aumentar el número de usos de referencias atrás de 1 a 2 (incluso con solo 2 variables) probablemente empuja el problema fuera del régimen casi lineal.
Innovación Algorítmica: El artículo introduce un marco algorítmico complejo pero altamente no trivial que combina árboles de sufijos, bosques de factorización y monoides de transición para resolver un problema que anteriormente se pensaba que requería tiempo cuadrático.

Los autores declaran explícitamente que su algoritmo es uniforme, lo que significa que procesa la expresión y la cadena de entrada juntos sin consejos no uniformes dependientes de la expresión fija. Reconocen que la dependencia exponencial del tamaño de la expresión $|E|$ sigue siendo una limitación para expresiones muy grandes, y dejan abierta la cuestión de si existe un algoritmo verdaderamente de tiempo lineal ( $O(|w|)$ ) o si los factores logarítmicos pueden eliminarse.

5. Limitaciones y Problemas Abiertos

El artículo identifica varias direcciones abiertas:

Complejidad de $r$ -uso 1-REWB: La complejidad para $r$ -uso 1-REWB donde $r \ge 2$ permanece abierta.
Tiempo Lineal: Si el límite $O(|w| \log^2 |w|)$ puede mejorarse a $O(|w|)$ .
Dependencia de la Expresión: Reducir la dependencia exponencial de $|E|$ a polinómica manteniendo una dependencia casi lineal de $|w|$ .
Características Más Amplias: Extender estos resultados a otras características prácticas de regex como miradas (lookarounds), agrupación atómica y estrellas codiciosas/perezosas.