Complexidade da substituição Regex

Question

Não obtive resposta para isso em lugar nenhum.Qual é a complexidade do tempo de execução de uma correspondência e substituição de Regex?

Editar:Eu trabalho em python.Mas gostaria de saber em geral sobre as linguagens/ferramentas mais populares (java, perl, sed).

Answer 1

De uma postura puramente teórica:

A implementação com a qual estou familiarizado seria construir um Autômato Finito Determinístico para reconhecer o regex.Isso é feito em O(2^m), sendo m o tamanho da regex, usando um algoritmo padrão.Uma vez construído, passar uma string por ele é linear no comprimento da string - O(n), sendo n o comprimento da string.Uma substituição em uma correspondência encontrada na string deve ser de tempo constante.

Então, no geral, suponho O(2^m + n).

Answer 2

Outras informações teóricas de possível interesse.

Para maior clareza, assuma a definição padrão para uma expressão regular

http://en.wikipedia.org/wiki/Regular_idioma

da teoria da linguagem formal.Praticamente, isso significa que o único material de construção são símbolos de alfabeto, operadores de concatenação, alternância e fechamento de Kleene, juntamente com a unidade e as constantes zero (que aparecem por razões teóricas de grupo).Geralmente, é uma boa idéia não sobrecarregar esse termo, apesar da prática cotidiana em idiomas de script, o que leva a ambiguidades.

Há uma construção da NFA que resolve o problema correspondente para uma expressão regular r e um texto de entrada t em o (| r | | t |) tempo e o (| r |) espaço, onde |-| é a função de comprimento.Este algoritmo foi melhorado por Myers

http://doi.acm.org/10.1145/128749.128755

à complexidade de tempo e espaço O(|r| |t| / log |t|) usando listagens de nós de autômatos e o paradigma dos Quatro Russos.Esse paradigma parece ter o nome de quatro caras russos que escreveram um artigo inovador que não está online.No entanto, o paradigma é ilustrado nessas notas de aula de biologia computacional

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

Acho hilário nomear um paradigma pelo número e pela nacionalidade dos autores, em vez de seus sobrenomes.

O problema correspondente para expressões regulares com referência adicional é NP-complete, o que foi comprovado por Aho

http://portal.acm.org/citation.cfm?id=114877

por uma redução do problema de cobertura de vértices que é um problema NP-completo clássico.

Para corresponder às expressões regulares com as backreferências deterministicamente, poderíamos empregar retrocesso (não muito diferente do mecanismo Perl Regex) para acompanhar as subbordas possíveis do texto de entrada t que pode ser atribuído às variáveis ​​em r.Existem apenas sub -palavras O (| t |^2) que podem ser atribuídas a qualquer variável em r.Se houver n variáveis ​​em r, existem as atribuições O (| t |^2n).Depois que uma atribuição de substringas a variáveis ​​é corrigida, o problema é reduzido à correspondência de expressão regular simples.Portanto, a pior complexidade para a correspondência de expressões regulares com referências é O (| t |^2n).

Observe que, no entanto, expressões regulares com referências de fundo ainda não são regexen completas.

Tomemos, por exemplo, o símbolo "Não se importe", além de outros operadores.Existem vários algoritmos polinomiais que decidem se um conjunto de padrões corresponde a um texto de entrada.Por exemplo, Kucherov e Rusinowitch

http://dx.doi.org/10.1007/3-540-60044-2_46

defina um padrão como uma palavra w_1@w_2@...@w_n onde cada w_i é uma palavra (não uma expressão regular) e "@" é um símbolo "não me importo" de comprimento variável não contido em nenhum dos w_i.Eles derivam um algoritmo O ((| t | + | p |) | p |) para corresponder a um conjunto de padrões P com um texto de entrada t, onde | t | é o comprimento do texto e | p | é a duração de todas as palavras em P.

Seria interessante saber como essas medidas de complexidade se combinam e qual é a medida da complexidade do problema correspondente para expressões regulares com referências de fundo, "Não se importe" e outras características interessantes das expressões regulares práticas.

Infelizmente, não disse uma palavra sobre Python ...:)

Answer 3

Depende do que você define por regex.Se você permitir operadores de concatenação, alternativa e estrela de Kleene, o tempo pode realmente ser O(m*n+m), onde m é o tamanho de uma regex e n é o comprimento da string.Você faz isso construindo um NFA (que é linear em m) e, em seguida, simulá-lo, mantendo o conjunto de estados em que você está e atualizando-o (em O(m)) para cada letra de entrada.

Coisas que dificultam a análise de regex:

• parênteses e referências anteriores:a captura ainda está OK com o algoritmo mencionado acima, embora a complexidade aumentasse, por isso pode ser inviável.As referências anteriores aumentam o poder de reconhecimento da regex, e sua dificuldade é bem
• perspectiva positiva:é apenas outro nome para interseção, o que aumenta a complexidade do algoritmo mencionado para O(m^2+n)
• antecipação negativa:um desastre para a construção do autômato (O(2^m), possivelmente PSPACE completo).Mas ainda deve ser possível lidar com o algoritmo dinâmico em algo como O(n^2*m)

Observe que com uma implementação concreta, as coisas podem melhorar ou piorar.Como regra geral, recursos simples devem ser rápidos o suficiente e inequívocos (por exemplo,não parece a*a*) regexes são melhores.

Answer 4

Para aprofundar a resposta do theprise, para a construção do autômato, O(2^m) é o pior caso, embora realmente dependa da forma da expressão regular (para uma expressão muito simples que corresponde a uma palavra, está em O( m), usando por exemplo o Algoritmo Knuth-Morris-Pratt).

Answer 5

Depende da implementação.Qual idioma/biblioteca/classe?Pode haver um melhor caso, mas seria muito específico para o número de recursos na implementação.

Answer 6

Você pode trocar espaço por velocidade construindo um autômato finito não determinístico em vez de um DFA.Isso pode ser percorrido em tempo linear.É claro que, na pior das hipóteses, isso pode precisar de espaço O(2^m).Eu esperaria que a troca valesse a pena.

Answer 7

Se você deseja correspondência e substituição, isso implica agrupamento e referências anteriores.

Aqui está um exemplo Perl onde agrupamento e referências anteriores podem ser usados ​​para resolver um problema NP completo: http://perl.plover.com/NPC/NPC-3SAT.html

Isso (juntamente com alguns outros detalhes teóricos) significa que o uso de expressões regulares para correspondência e substituição é NP-completo.

Observe que isso é diferente da definição formal de uma expressão regular - que não possui a noção de agrupamento - e corresponde em tempo polinomial conforme descrito pelas outras respostas.