Eclesiastes

Ícone

Sobre o que é este blog? O.o

Catastrophic Backtracking

Voltando a falar em Backtracking, acompanhe uma análise de como ele pode se comportar de maneira bem catastrófica.

O texto abaixo é uma tradução minha da página http://www.regular-expressions.info/atomic.html.

A necessidade apresentada é a de fazer uma expressão que combine com 11 trechos delimitados por vírgula, onde o 12º inicia com a letra P. A expressão a ser usada, é a seguinte: ^(.*?,){11}P.

A princípio, a expressão trabalhará da seguinte forma: O ponto combinará de forma não gulosa (ungreedy), ou seja, não casará com vírgulas, casando assim, somente os 11 trechos delimitados, finalizando com a combinação do P. Se de fato, iniciar com P, o 12º trecho.

O problema todo é quando o 12º trecho não começa com P! Por exemplo, na string “1,2,3,4,5,6,7,8,9,10,11,12,13”. Sendo assim, a engine fará uso de backtrack. Voltando assim para o ponto “1,2,3,4,5,6,7,8,9,10,11”, iniciando então antes da última vírgula anteriormente combinada. Então a engine segue a 11º iteração, e agora o ponto não guloso casará com uma vírgula – já que a tentativa anterior não obteve êxito – e combina com “11,12,”. Como você deve ter notado, o problema é originado pelo ponto não guloso casar também o delimitador utilizado (a vírgula). Porque as 11 repetições indicadas conduz a uma quantidade catastrófica de backtracking.

A engine agora irá verificar se o 13º trecho inicia com P, mas falha novamente. Visto que não há nenhuma vírgula após o 13º campo, a engine não combina a 11ª iteração de .*?. Mas não acaba por aqui! O backtrack é feito novamente, agora voltando para a 10ª iteração, expandindo-a para “10,11,”. Que ao verificar que não casará com P é novamente expandida à “10,11,12,”. Chegando ao final da string outra vez, repetindo a mesma história a 9ª iteração, expandindo para “9,10,”. “9,10,11”. “9,10,11,12,”. Mas entre cada expansão, a mais possibilidades para tentar. Quando a 9ª iteração tenta combinar com “9,10,” a 10ª tenta somente com “11,” assim com “11,12,”. Continuamente falhando, a engine fará backtrack para 8ª iteração, denovo tentando todas as possibilidades de combinação para 9ª, 10ª e 11ª iterações.

Conclusão: o número possível das combinações que a engine tentará para cada trecho onde o 12ª não começa com P é enorme. O debugger do RegexBuddy informa que é necessário 48.066 passos até que encerre as tentativas. O que faz com que fique lento, obviamente. Alguns programas podem até parar de responder, enquanto a engine está processando tentando gravar todas as posições do backtracking.

Uma solução para o caso, seria o uso de uma lista negada, onde não deveria faltar o delimitador usado (a vírgula). Impossibilitando assim, a catástrofe de backtracking. O que chegaria a 26 passos. O uso de grupo atômico e/ou quantificador possessivo também serviria para o caso, como você pode ver no link citado no início do post, pois ambos
evitam o uso de backtracking onde sem eles ocorre por falhar a tentativa de combinação.

Referência

Arquivado em:Regex

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: