Por que a correspondência regular é tão lenta [fechada]?

Question

Eu aprendi com este artigo sobre ripgrep que os mecanismos de expressão regular que implementam o retrocesso podem ser muito lentos em alguns casos, mas eu não entendo o porque. Alguém poderia explicar em termos simples por que o seguinte trecho de python, dado como um exemplo no artigo vinculado, é muito lento?

>>> import re
>>> re.search('(a*)*c', 'a' * 30)

    

Answer 1

Basicamente, o problema é com a repetição duplicada do a no padrão. A parte a* permite qualquer número de a , enquanto o (·)* também permite qualquer número do padrão contido.

Isso permite um grande número de maneiras possíveis de combinar o padrão com uma string de a . Ignorando o b por enquanto, uma string como aaaaa (cinco a ) pode ser correspondida como (aaaaa) , (aaaa)(a) , (aaa)(aa) , (aaa)(a)(a) , (aa)(aaa) , (aa)(aa)(a) . .. Há um número exponencial de maneiras de combinar com a string.

Com o b no final, um mecanismo de backtracking tentará uma maneira de corresponder a a , percebe que não encontra o b , retrocede um passo, tenta de outra forma, percebe Não é possível encontrar o b , ... e leva muito tempo para esgotar todos os arranjos possíveis, após o que ele falha.

Existem textos muito melhores sobre esse assunto on-line do que eu jamais poderia escrever. Vá ler estes:

• Expressões regulares em fuga: Backtracking catastrófico de Jan Goyvaerts descreve o problema e algumas maneiras de evitá-lo .

• A correspondência de expressões regulares pode ser simples e rápida (mas ...) por Russ Cox também descreve a questão, assim como implementa regexes como autômatos finitos, sem usar retrocessos e, portanto, imune a esse problema. Também tem fotos.

Na prática, se puder, evite padrões que permitam várias maneiras de corresponder a uma string. O exemplo aqui, (a*)*c , é obviamente tolo, já que é equivalente a a*c , que não tem a repetição aninhada.