Após a interrupção do StackOverflow de ontem - a correspondência de expressões regulares é realmente difícil ou a implementação é simplesmente ineficiente?

Ontem, o StackOverflow ficou inoperante por meia hora. Mais tarde, eles escreveram um post sobre o assunto , detalhando que o problema surgiu da inesperadamente alta complexidade da correspondência de expressões regulares.

Em resumo, a expressão regular a+b, quando executada na string aaaaaaaaaaaaaac, é executada em$O(n^2)$ hora em que $n$é o número de acaracteres, porque usa retrocesso.

Você pode reproduzir o problema com o seguinte código Python, que no meu computador leva mais de 4 segundos para ser executado:

import re, time
start = time.time()
re.findall(r'\s+$', ' '*20000 + 'x')
print(time.time() - start)

Isso foi muito surpreendente para mim; Eu pensaria que um par de regex funciona de maneira mais eficiente, por exemplo, construindo um DFA a partir do regex e executando a string desejada através dele, o que eu pensaria que seria$O(n)$ (não incluindo a construção do DFA).

(Por exemplo, o livro Introdução aos algoritmos de Cormen, Leiserson, Rivest passa por um algoritmo semelhante no caminho da introdução do algoritmo de Knuth-Morris-Pratt).

Minha pergunta: Existe algo inerentemente difícil na correspondência de expressões regulares que não permita uma$O(n)$algoritmo , ou estamos simplesmente falando de uma implementação ineficiente (em Python, em qualquer que seja o StackOverflow, etc.)?

Se você apenas quisesse analisar expressões regulares, não teria esses problemas (a menos que fosse um programador realmente incompetente, eu acho). Advertências incluem o tempo necessário para construir um autômato; um algoritmo assintoticamente pior pode superar a abordagem do autômato em muitos casos na prática.

O problema real é provavelmente que eles usam funções de biblioteca que lidam com regexps, que são muito mais poderosos do que expressões regulares comuns. Além disso, recursos como grupos correspondentes introduzem mais complexidade.

Nesse caso, surgiram problemas porque esses mecanismos correspondem a substrings (com expressões regulares simples, normalmente correspondemos apenas a entradas inteiras) e usamos retrocesso ; correspondências parciais longas que, eventualmente, não correspondem, causam retornos longos. Em essência, esse é o pior caso para a correspondência ingênua de seqüência de caracteres em tempo quadrático.

Isso pode ser melhorado? Talvez. Usando as idéias dos autômatos de correspondência de cadeias , voltaríamos não para o segundo símbolo, mas para o início do sufixo mais longo que corresponde a um prefixo do padrão. Mas como o padrão não é mais fixo, certamente não é trivial estender as idéias.