💬 NLP

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

Este artigo estabelece a complexidade computacional de granularidade fina da correspondência de expressões regulares com referências retroativas, provando limites inferiores condicionais sob as suposições de SETH e detecção de triângulos, ao mesmo tempo que apresenta um algoritmo aprimorado de $O(n \log^2 n)$ para referências retroativas de uso único.

Autores originais: Soh Kumabe, Yuya Uezato

Publicado 2026-05-11

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Soh Kumabe, Yuya Uezato

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

O Panorama Geral: O Engarrafamento do "Regex"

Imagine que você é um guarda de segurança em um clube (o sistema de computador). Você tem uma lista de regras (uma Expressão Regular) sobre quem pode entrar.

Regras Simples: "Apenas pessoas usando camisas vermelhas." Isso é fácil de verificar. Você olha para a camisa, diz "Vermelha? Sim, entre." Leva a mesma quantidade de tempo, seja a fila de 10 pessoas ou 10.000.
O Problema (ReDoS): Às vezes, hackers criam uma fila específica de pessoas que engana o guarda, fazendo-o realizar uma quantidade massiva de trabalho desnecessário. Em vez de verificar uma pessoa e seguir em frente, o guarda começa a verificar a Pessoa A, depois a Pessoa B, depois a Pessoa A novamente, depois a Pessoa C, depois a Pessoa A novamente... até que o guarda colapse de exaustão. Isso é chamado de ataque de Negação de Serviço (ReDoS).

No mundo real, isso causou a queda de grandes sites como Stack Overflow e Cloudflare. O artigo observa que até mesmo uma lentidão "quadrática" (onde verificar 100 pessoas leva 10.000 passos) é suficiente para derrubar um sistema.

O Vilão: "Backreferences" (Referências Traseiras)

Regras padrão são simples. Mas os motores modernos de "Regex" têm um recurso superpoderoso chamado Backreferences.

A Analogia:
Imagine uma regra que diz: "Encontre uma palavra, lembre-se dela e, em seguida, garanta que a exata mesma palavra apareça novamente mais tarde."

Exemplo: "Encontre uma palavra, chame-a de 'X'. Depois, encontre 'X' novamente."
Se a entrada for maçã ... maçã, funciona.
Se a entrada for maçã ... banana, falha.

Esse recurso é incrivelmente útil para programadores, mas torna o trabalho do "guarda" muito mais difícil. O guarda precisa lembrar o que viu anteriormente e comparar constantemente com o que está vendo agora. O artigo pergunta: Podemos construir um guarda que seja rápido o suficiente para lidar com essas regras complexas sem ficar cansado?

As Descobertas do Artigo: O Bom, o Mau e o Feio

Os autores investigaram exatamente quão difícil é resolver esses problemas de correspondência. Eles dividiram em dois lados: Dificuldade (Por que é difícil) e Algoritmos (Como resolver).

1. A Má Notícia: Algumas Regras são Impossíveis de Acelerar

O artigo prova que, para certos tipos de regras complexas, não há "bala de prata" para torná-las rápidas.

O Problema do "Triângulo": Eles mostraram que, se você tiver uma regra que usa duas variáveis (como lembrar duas palavras diferentes e verificá-las mais tarde), resolvê-la é tão difícil quanto encontrar um triângulo em um gráfico gigante de rede social. Se você pudesse resolver a regra rapidamente, poderia resolver o problema do gráfico rapidamente. Como especialistas em gráficos acreditam que o problema do gráfico é inerentemente lento, o problema da regra também deve ser lento.
O Problema dos "Vetores Ortogonais": Para regras com ainda mais variáveis, eles provaram que o tempo necessário cresce exponencialmente com o número de variáveis. É como tentar encontrar uma combinação específica de chaves em uma fechadura; quanto mais chaves você tem, mais impossível se torna forçá-la rapidamente.

Conclusão: Se sua regra for muito complexa (usando muitos recursos de "lembre-se disto"), você não poderá construir um motor rápido para ela. Você sempre encontrará um muro.

2. A Boa Notícia: Uma Solução "Quase Linear" para Casos Simples

No entanto, o artigo encontrou um ponto ideal. Eles focaram em um tipo específico e comum de regra:

O Padrão "ABCBD": "Encontre uma palavra (A), depois uma palavra (B), depois uma palavra (C), depois a exata mesma palavra B novamente, depois uma palavra (D)."
- Exemplo do mundo real: "Encontre um nome de usuário, depois uma senha, depois uma mensagem, depois o mesmo nome de usuário novamente, depois uma assinatura."

Os autores descobriram que, embora isso pareça complicado, pode ser resolvido com muita eficiência.

O Jeito Antigo: Métodos anteriores eram como verificar todas as combinações possíveis em uma biblioteca, o que levava tempo $O(n^2)$ (quadrático). Se o livro tivesse 1.000 páginas, levaria 1.000.000 de passos.
O Novo Jeito: Os autores construíram um novo algoritmo que leva aproximadamente $O(n \log^2 n)$ $O (n lo g^{2} n)$ tempo.
- A Analogia: Imagine que a biblioteca está organizada com um sistema de índice mágico (usando Árvores de Sufixo e Florestas de Fatoração). Em vez de ler cada página, o guarda pode pular diretamente para as seções relevantes. Se o livro tiver 1.000 páginas, o novo método leva aproximadamente 10.000 passos (ou até menos), o que é uma melhoria massiva.

Como o Novo Algoritmo Funciona (Os "Truques de Mágica")

Para alcançar essa velocidade, os autores usaram várias técnicas inteligentes, que eles descrevem no artigo:

A Árvore de Sufixo (O Mapa): Eles construíram um mapa gigante da string de entrada. Este mapa mostra todas as terminações possíveis da string. Ajuda o guarda a ver instantaneamente: "Ah, esta palavra 'B' aparece aqui, e também aparece ali."
Decomposição Pesada-Leve (O Chapéu Seletor): Eles dividiram o mapa em caminhos "pesados" (caminhos muito comuns) e caminhos "leves" (caminhos raros). Eles só fazem o trabalho pesado nos caminhos raros, economizando tempo.
Periodicidade (O Ritmo): Eles notaram que, quando uma palavra se repete (como "B...B"), a string frequentemente tem um ritmo ou um padrão. Eles usaram matemática para prever esses padrões em vez de verificar cada letra individualmente.
Florestas de Fatoração (O Índice): Esta é uma estrutura de dados que atua como um índice super-rápido, permitindo que o guarda verifique se um trecho de texto corresponde a uma regra em tempo constante, não importa o tamanho do texto.

Resumo da Conclusão

Podemos parar todos os ataques ReDoS? Não. Se uma regra for muito complexa (demasiadas variáveis de "lembre-se disto"), está matematicamente provado que será lenta.
Podemos consertar as regras complexas mais comuns? Sim! Para o caso específico em que uma regra lembra uma palavra e a verifica uma vez mais tarde (o padrão "ABCBD"), os autores criaram um novo motor que é quase tão rápido quanto as regras simples.
Por que isso importa? Isso diz aos engenheiros de software: "Não use muitos backreferences, ou você ficará lento. Mas se você os usar dessa maneira específica e comum, agora pode usar nosso novo método para manter seu sistema seguro e rápido."

O artigo essencialmente traça uma linha na areia: Aqui é onde o limite de velocidade é inquebrável, e aqui é onde encontramos uma maneira de dirigir mais rápido.

Resumo Técnico: Sobre a Complexidade do Problema de Correspondência de Expressões Regulares com Referências Atrás

1. Definição do Problema e Motivação

O artigo investiga a complexidade computacional de alta precisão do Problema de Correspondência de Expressões Regulares com Referências Atrás (REWB). Enquanto as expressões regulares clássicas (Regex) podem ser correspondidas em tempo linear em relação ao comprimento da string de entrada $|w|$ usando a construção de Thompson, motores práticos suportam referências atrás (por exemplo, (E)x para capturar uma substring e \x para reutilizá-la). Essa característica estende estritamente o poder expressivo das Regex (permitindo o reconhecimento de linguagens não regulares como $\{ww \mid w \in \Sigma^*\}$ ), mas introduz riscos algorítmicos significativos.

A motivação decorre de ataques de Negação de Serviço por Expressão Regular (ReDoS), onde adversários criam entradas para desencadear comportamentos de pior caso em motores de correspondência. Incidentes notáveis na Stack Overflow (2016) e na Cloudflare (2019) demonstraram que mesmo um comportamento de tempo quadrático ( $O(|w|^2)$ ) em motores baseados em retrocesso pode causar interrupções catastróficas de serviço. Os autores levantam a questão fundamental: É possível construir motores seguros contra ReDoS para REWB que executem em tempo linear ou quase linear?

O artigo foca em $r$ -uso $k$ -REWBs, definidos como expressões com $k$ variáveis distintas onde o número total de execuções de referência atrás em qualquer computação é limitado por $r$ .

2. Metodologia e Abordagem Técnica

O artigo emprega uma abordagem dual: estabelecer limites inferiores condicionais (dificuldade) e projetar algoritmos eficientes para subclasses específicas.

2.1 Resultados de Dificuldade

Os autores reforçam resultados anteriores de complexidade reduzindo problemas conhecidos como difíceis à correspondência de REWB:

Dificuldade W[2]: Ao reduzir o problema do $k$ -Conjunto Dominante, eles provam que a correspondência de REWB é W[2]-difícil quando parametrizada pelo tamanho da expressão $|E|$ . Isso reforça o resultado conhecido de dificuldade W[1].
Limites Inferiores Condicionais (Detecção de Triângulo): Assumindo a "Hipótese de Não-Tempo-Quase-Linear" para Detecção de Triângulo, eles mostram que mesmo o problema altamente restrito de 2-uso 2-REWB não pode ser resolvido em tempo $O(|w|^{1+\delta})$ para qualquer $\delta > 0$ .
Limites Inferiores Condicionais (k-OV): Sob a hipótese de Vetores Ortogonais $k$ (k-OV) (mais fraca que a SETH), eles provam que a correspondência de $k$ -REWB não pode ser resolvida em tempo $O(|w|^{2k-\epsilon})$ . Isso implica que, para $k$ geral, tempo quase linear é improvável.

2.2 Resultados Algorítmicos

A principal contribuição algorítmica foca em 1-uso REWBs (expressões com uma variável referenciada exatamente uma vez).

Transformação para Forma Canônica: Os autores provam que qualquer 1-uso REWB pode ser transformado em uma forma canônica envolvendo uma soma de termos como $A (B)_x C \backslash x D$ , onde $A, B, C, D$ são Regex clássicas. Isso é denominado o problema ABCBD.
Estratégia de Decomposição: O problema ABCBD é decomposto em dois subproblemas:
1. Problema XYYZ: O caso onde as duas ocorrências de $B$ são adjacentes ( $w = w_A w_B w_B w_D$ ). Isso é resolvido usando a enumeração de potência local máxima de Crochemore e propriedades de conjuntos ultimamente periódicos derivados de monoides de transição.
2. Problema ABCBD Ramificado: O caso onde as duas ocorrências de $B$ são separadas por um $C$ não vazio, e os caracteres imediatamente seguintes às duas ocorrências de $B$ diferem.
Árvore de Sufixos e Decomposição Pesada-Leve: Para o caso Ramificado, o algoritmo utiliza a árvore de sufixos da string de entrada $w$ . Emprega decomposição pesada-leve para particionar o espaço de busca.
Estruturas de Dados:
- Florestas de Fatorização: Usadas para avaliar a pertinência a Regex em substrings em tempo constante após processamento linear.
- Monoides de Transição: Aproveitados para rastrear o estado das Regex $A, B, C, D$ eficientemente.
- Enumeradores Personalizados: Os autores projetam estruturas de dados especializadas (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) para lidar com a enumeração de transições. Essas estruturas usam atualizações preguiçosas e estratégias de união-busca disjunta (DSU) para gerenciar restrições que variam com o comprimento da substring $w_B$ .

3. Resultados Chave

Dificuldade

Teorema 3: A correspondência de REWB é W[2]-difícil parametrizada pelo tamanho da expressão.
Teorema 4: Assumindo a hipótese de Detecção de Triângulo, a correspondência de 2-uso 2-REWB requer tempo superlinear (especificamente, não $O(|w|^{1+\delta})$ ).
Teorema 5: Sob a hipótese $k$ -OV, a correspondência de $k$ -REWB requer tempo $\Omega(|w|^{2k-\epsilon})$ .

Algoritmos

Teorema 7 (Resultado Principal): O problema ABCBD admite um algoritmo de tempo $O(|w| \log^2 |w|)$ . A constante oculta depende exponencialmente dos tamanhos das Regex $A, B, C, D$ ( $2^{O((|A|+|B|+|C|+|D|)^2)}$ ).
Teorema 8: Consequentemente, o problema de correspondência de 1-uso REWB admite um algoritmo de tempo $O(|w| \log^2 |w|)$ .
Teorema 9: O problema XY $\alpha$ Z (generalizando XYYZ para $\alpha$ repetições) admite um algoritmo de tempo $O(|w| \log |w|)$ .

Estes resultados representam uma melhoria significativa sobre o melhor algoritmo conhecido anteriormente de $O(|w|^2)$ para o problema ABCBD de Nogami e Terauchi (MFCS 2025).

4. Significado e Alegações

O artigo afirma fornecer uma compreensão fundamental da paisagem de complexidade para a correspondência de REWB:

Segurança ReDoS: Estabelece que, embora a correspondência geral de REWB seja provavelmente intratável para tempo quase linear, uma subclasses praticamente relevante (1-uso REWB) pode ser correspondida em tempo quase linear. Isso sugere que motores que suportam referências atrás de 1-uso poderiam teoricamente ser tornados seguros contra ReDoS.
Complexidade de Alta Precisão: O trabalho delimita a fronteira entre casos tratáveis e intratáveis. Mostra que aumentar o número de usos de referência atrás de 1 para 2 (mesmo com apenas 2 variáveis) provavelmente empurra o problema para fora do regime quase linear.
Inovação Algorítmica: O artigo introduz um framework algorítmico complexo, mas altamente não trivial, combinando árvores de sufixos, florestas de fatorização e monoides de transição para resolver um problema anteriormente pensado como exigindo tempo quadrático.

Os autores afirmam explicitamente que seu algoritmo é uniforme, ou seja, processa a expressão e a string de entrada juntos sem conselhos não uniformes dependentes da expressão fixa. Eles reconhecem que a dependência exponencial no tamanho da expressão $|E|$ permanece uma limitação para expressões muito grandes, e deixam em aberto a questão de se um algoritmo de tempo verdadeiramente linear ( $O(|w)|$ ) existe ou se os fatores logarítmicos podem ser removidos.

5. Limitações e Problemas Abertos

O artigo identifica várias direções abertas:

Complexidade de $r$ -uso 1-REWB: A complexidade para $r$ -uso 1-REWBs onde $r \ge 2$ permanece aberta.
Tempo Linear: Se o limite $O(|w| \log^2 |w|)$ pode ser melhorado para $O(|w|)$ .
Dependência da Expressão: Reduzir a dependência exponencial em $|E|$ para polinomial, mantendo a dependência quase linear em $|w|$ .
Recursos Mais Amplos: Estender esses resultados para outros recursos práticos de regex, como lookarounds, agrupamento atômico e estrelas gananciosas/preguiçosas.