La búsqueda de todas las coincidencias de expresiones regulares (regex) es un problema sorprendentemente complejo y, a menudo, malentendido. Aunque la mayoría de los motores de regex prometen un rendimiento lineal para una sola coincidencia, encontrar todas las coincidencias invariablemente resulta en una complejidad de tiempo O(n²), donde 'n' es la longitud de la cadena de entrada. Esto significa que el tiempo de ejecución aumenta cuadráticamente con el tamaño de la entrada, lo que puede llevar a tiempos de procesamiento inaceptablemente largos, incluso con patrones aparentemente simples.
¿Por qué ocurre esto? El problema radica en la iteración necesaria para encontrar todas las coincidencias. Cuando se solicita 'todas' las coincidencias, el motor debe escanear la cadena de entrada repetidamente, intentando diferentes puntos de partida para el patrón. Un ejemplo simple ilustra esto: buscar el patrón “.a|b” en una cadena compuesta por 'n' caracteres 'b'. El motor primero intenta “.a” en cada posición, lo que implica escanear el resto de la cadena y fallar. Luego, intenta la rama “b”, que solo avanza un carácter. Este proceso se repite 'n' veces, resultando en una complejidad O(n²).
¿Quién se ve afectado? Prácticamente todos los lenguajes de programación y herramientas que utilizan regex, incluyendo Go, Rust, .NET y JavaScript, sufren de este problema. Incluso motores que se promocionan como de 'tiempo lineal' (como RE2) fallan al solicitar todas las coincidencias. La honestidad de la documentación de la crate de regex de Rust es notable: admite explícitamente la complejidad O(m * n²) para iteradores.
¿Qué soluciones existen? Aunque la solución O(n²) es inherente a la búsqueda de todas las coincidencias con regex tradicionales, existen alternativas. El algoritmo de Aho-Corasick, diseñado originalmente para encontrar múltiples cadenas fijas en una sola pasada, ofrece una solución lineal, pero solo funciona con patrones literales, no con expresiones regulares complejas. Hyperscan/Vectorscan ofrecen una solución lineal utilizando 'earliest match' semantics, pero esto cambia el comportamiento esperado de la búsqueda (en lugar de encontrar la coincidencia más larga, encuentra la más corta). RE# (el motor de regex desarrollado por Ian Erik Varatalu) es el primero que, según sus creadores, logra encontrar todas las coincidencias en dos pasadas, manteniendo la semántica original sin la penalización cuadrática.
Consideraciones importantes: El problema de la complejidad cuadrática es sutil pero significativo. Puede pasar desapercibido hasta que se procesan grandes cantidades de datos, donde el tiempo de ejecución se vuelve inaceptable. Además, el uso de regex con entrada de usuario sin validación puede llevar a ataques de Denegación de Servicio (ReDoS), donde un patrón malicioso puede hacer que el motor de regex consuma una cantidad excesiva de recursos. La elección del motor de regex y la forma en que se utiliza debe considerar cuidadosamente estas limitaciones y posibles riesgos.