Como expressões regulares realmente funcionam?

30

Digamos que você tenha um documento com um ensaio escrito. Você deseja analisar este ensaio para selecionar apenas determinadas palavras. Legal.

O uso de uma expressão regular é mais rápido do que analisar o arquivo linha por linha e palavra por palavra, procurando uma correspondência? se sim, como isso funciona? Como você pode ir mais rápido do que olhar para cada palavra?

lazer
fonte
5
Você supõe (implicando zero evidência) que uma expressão regular será mais rápida, mas você não sabe por que é? Talvez você deva reconsiderar sua suposição.
Pd #
3
assim, a suposição. se eu tivesse provas, não seria uma, certo?
Lazer
4
Essa não é a questão. A questão é o que o levou a essa suposição ... Você não precisa de evidências para suas perguntas, mas precisa de um raciocínio para suas suposições.
usar o seguinte
11
err, nem todos os caracteres da string de entrada estão apenas movendo uma máquina de estado para o próximo estado. Eu não vejo como alguém poderia obter essa operação lenta ...
tp1
2
Não tenho certeza sobre a rapidez, mas meu principal motivo para usar expressões regulares é devido à elegância de padrões complexos de correspondência. Você simplesmente não encontrará uma maneira melhor de articulá-la em um ambiente de codificação.
Mantorok

Respostas:

47

Como funciona?

Dê uma olhada na teoria dos autômatos

Em resumo, cada expressão regular possui um autômato finito equivalente e pode ser compilado e otimizado para um autômato finito. Os algoritmos envolvidos podem ser encontrados em muitos livros do compilador. Esses algoritmos são usados ​​por programas unix como awk e grep.

No entanto, a maioria das linguagens de programação modernas (Perl, Python, Ruby, Java (e linguagens baseadas em JVM), C #) não usam essa abordagem. Eles usam uma abordagem de retorno recursivo, que compila uma expressão regular em uma árvore ou uma sequência de construções que representam vários sub-blocos da expressão regular. A maioria das sintaxes modernas de "expressão regular" oferece referências externas que estão fora do grupo de linguagens regulares (elas não têm representação em autômatos finitos), que são trivialmente implementáveis ​​na abordagem de retorno recursivo.

A otimização geralmente produz uma máquina de estado mais eficiente. Por exemplo: considere aaaab | aaaac | aaaad, um programador normal pode obter a implementação de pesquisa simples, mas menos eficiente (comparando três strings separadamente) em dez minutos; mas percebendo que é equivalente a aaaa [bcd], uma pesquisa melhor pode ser feita pesquisando os quatro primeiros 'a' e testando o quinto caractere contra [b, c, d]. O processo de otimização foi um dos meus trabalhos domésticos de compilador há muitos anos, portanto, presumo que ele também esteja nos mais modernos mecanismos de expressão regular.

Por outro lado, as máquinas de estado têm alguma vantagem quando aceitam cadeias porque usam mais espaço em comparação com uma "implementação trivial". Considere um programa para remover as aspas das seqüências de caracteres SQL, ou seja: 1) inicia e termina com aspas simples; 2) aspas simples são escapadas por duas aspas simples consecutivas. Portanto: input ['a' ''] deve produzir saída [a ']. Com uma máquina de estados, as aspas simples consecutivas são tratadas por dois estados. Esses dois estados servem ao propósito de lembrar o histórico de entrada, de modo que cada caractere de entrada seja processado exatamente apenas uma vez, conforme ilustrado a seguir:

...
S1->'->S2
S1->*->S1, output *, * can be any other character 
S2->'->S1, output '
S2->*->END, end the current string

Portanto, na minha opinião, a expressão regular pode ser mais lenta em alguns casos triviais, mas geralmente mais rápida do que um algoritmo de pesquisa criado manualmente, considerando o fato de que a otimização não pode ser feita com segurança por humanos.

(Mesmo em casos triviais, como pesquisar uma cadeia, um mecanismo inteligente pode reconhecer o caminho único no mapa de estados e reduzir essa parte a uma comparação simples de cadeias e evitar o gerenciamento de estados.)

Um mecanismo específico de uma estrutura / biblioteca pode ser lento porque o mecanismo faz várias outras coisas que um programador geralmente não precisa. Exemplo: a classe Regex no .NET cria vários objetos, incluindo Correspondência, Grupos e Capturas.

Codism
fonte
2
Eu não poderia ter dito melhor. A única coisa que eu acrescentaria: Expressões regulares também podem compensar programadores preguiçosos. No exemplo que você mencionou aaaab|aaaac|aaaadvs. aaaa[bcd]. Vale a pena declarar explicitamente que os dois são matematicamente equivalentes e produzem o mesmo DFA, dando assim aos programadores mais liberdade para representar uma expressão regular de uma maneira que faça sentido (não que isso seja uma prática comum, mas ... você sabe). ..
riwalk
Graças, neste sentido graças realmente feita para a classe de autômatos que eu levei
LAZER
É este um exemplo de um problema trivial onde regex é um exagero ?: stackoverflow.com/questions/18955099/...
Menelau Bakopoulos
17

Expressões regulares parecem rápidas porque você tem computadores rápidos.

Nos anos 80, quando o 1 MIPS era um computador veloz, as expressões regulares eram uma área bastante grande de preocupação, preocupação e pesquisa, porque eram lentas, feias e intensivas em computação. O desenvolvimento inteligente de algoritmos se seguiu e ajudou - mas, para todos os fins práticos, hoje em dia, você está vendo o milagre de máquinas rápidas encobrindo as fendas.

rapid_now
fonte
2
Se você está procurando apenas uma palavra, ambos os métodos são os mesmos (ou regexp é um pouco mais lento). Mas, dada uma expressão complexa (e texto de tamanho razoavelmente grande), a expressão regular provavelmente será mais rápida que uma pesquisa simples (supondo que você escreva a pesquisa simples (você sempre pode escrever uma pesquisa complexa com a mesma rapidez)). Agora, o tempo é significativo, é uma pergunta muito geral e você deverá analisá-la caso a caso.
Martin York
3
-1. A teoria da expressão regular remonta aos anos 50 e foi fundamental na criação de analisadores lexicais (e, por extensão, compiladores). Eles criam máquinas de estado muito eficientes que (comprovadamente) usam o menor número possível de estados. As máquinas de estado resultantes podem corresponder a padrões complexos muito mais rapidamente do que qualquer coisa que você possa escrever manualmente. Eles parecem rápidos porque são rápidos.
riwalk
Pode ter perdido um pouco o meu argumento. Eles podem ser "rápidos", mas isso é tudo relativo - ainda há muito trabalho a fazer. Algumas das outras respostas aqui também trazem leitura.
quickly_now
Esta resposta é relevante para a pergunta? e como 13 votos positivos?
precisa
7

Por que você acha que eles são mais rápidos do que pesquisar no documento?

Existem alguns truques que você pode fazer, por exemplo. se você estiver procurando por uma palavra de 10 letras que comece com A e termine com B, se você encontrar um A e o personagem 9 nas posições seguintes não for B, poderá pular alguns. veja o algoritmo de Knuth-Morris-Pratt

Martin Beckett
fonte
5

O que torna uma expressão regular rápida?

Na verdade, eles não são. Nem tanto. Só que eles não são lentos o suficiente para a maioria de nós perceber. Nos velhos tempos lentos, era muito mais perceptível.

Eles também não são a ferramenta certa para todos os trabalhos - o martelo .

Torre
fonte
1 Obrigado por me lembrar que o trabalho de arte em particular ...
yannis
5

Os RegEx são comparativamente mais rápidos em codificar que você pode escrever, porque a maioria das bibliotecas é o resultado de muitos desenvolvedores gastando muitos anos otimizando-os para obter todo o desempenho possível. É difícil para um único indivíduo duplicar isso em seu próprio código de pesquisa.

GrandmasterB
fonte
4
s / squeak / squeeze /?
Péter Török
4

Sua premissa básica está errada.

As expressões regulares nem sempre são mais rápidas que uma simples pesquisa. Tudo depende do contexto. Depende da complexidade da expressão, do comprimento do documento que está sendo pesquisado e de vários fatores.

O que acontece é que a expressão regular será compilada em um analisador simples (que leva tempo). Assim, se o documento for pequeno, esse tempo extra superará qualquer vantagem. Além disso, se a expressão for simples, a expressão regular não fornecerá nenhuma vantagem.

Se a expressão for complexa e o documento for grande o suficiente, você poderá obter alguns benefícios. Se isso é significativo o suficiente para considerar as expressões regulares mais rápidas, dependerá muito do esforço que você deseja colocar na pesquisa (também as expressões regulares podem ter algumas otimizações que uma biblioteca poderia fornecer e que você não pensaria em si mesmo).

O que estou tentando dizer é que não há uma resposta generalizada e generalizada. Se você tivesse uma expressão específica (e um tamanho de documento conhecido), seria possível obter uma resposta sim / não para determinar se a expressão será mais rápida que uma simples pesquisa (e por que).

A verdadeira vantagem das expressões regulares é que, depois de entender como escrevê-las, a capacidade de expressar uma pesquisa complexa de maneira concisa. Por ser uma forma generalizada, você pode criar ferramentas que permitam pesquisas de uma maneira útil no caso geral; geralmente é pelo menos tão rápido quanto uma pesquisa simples (em documentos de tamanho mínimo; em documentos menores que isso não importaria, pois, mesmo que seja mais lento, ainda é rápido o suficiente).

Martin York
fonte
1

É plausível que em algumas linguagens de alto nível (talvez javascript), o uso de uma biblioteca regex implementada em uma linguagem de baixo nível (talvez C) seja mais rápido do que escrever a lógica do analisador na linguagem de alto nível.

Plausível - não faço ideia se esse é realmente o caso.

Steve Bennett
fonte
Agradável! Isso é algo que eu também considerei. Mas com os processadores de hoje muito mais rápidos que seus antecessores, posso dizer com segurança que, se você escrever código com eficiência, raramente será capaz de diferenciar. Na verdade, eu não sou realmente gaga sobre a hipótese mais rápida da expressão regular inteira! ;-)
user3833732 11/10