O que é uma
Expressão Regular Gulosa
?O que diferencia ela da
Expressão Regular Não-Gulosa
?Expressões regulares Gulosas
consomem mais recurso do que asNão-Gulosas
?
-
1Agora, quanto as expressões regulares, já que você esta estudando sobre, recomendo a leitura deste artigo– Guilherme LautertCommented 23/10/2015 às 10:59
-
1Valeu @GuilhermeLautert– Wallace VizerraCommented 23/10/2015 às 10:59
-
3"Expressão Regular Gulosa" é o jeito que os gordinhos regularmente se expressam sobre sua própria gula.– utluizCommented 27/10/2015 às 6:19
5 Respostas
Quantificadores
Especificam quantas vezes a instancia anterior deve ser capturada
Quantificador Guloso
Em geral quando se fala de quantificador guloso se refere ao *
, pois ele representa 0 ou infinitas vezes, ou seja ele tentara capturar o máximo possível, mas caso não haja o que capturar esta ok
também.
Entretanto um quantificador guloso também pode ser {0,}
que tem o mesmo efeito.
Mais alguns :
+ // captura o máximo possível, mas deve ocorrer ao menos uma vez
{1,} // tem o mesmo efeito
Pensamentos
1. {1,5} // é um quantificador que vai de 1 a 5
2. {1,80} // é um quantificador que vai de 1 a 80
3. {60,80} // é um quantificador que deve ter no mínimo 60 e vai ate 80
O 2.
seria mais guloso que o 1.
pois ele casa com ate 80 enquanto o 1.
apenas com 5, já o 3.
ele diz que deve ter ao menos 60
podendo ir ate 80
, o que seria mais guloso ainda pois especifica um mínimo.
Analogia
Pense em um pessoa comendo:
- a
1.
diz que come de 1 a 5 kg. - a
2.
diz que come de 1 a 80 kg. - a
3.
diz que quer comer de 60 a 80 kg.
Quantificadores não-guloso
Para fazer o efeito contrario no quantificador guloso se acrescenta o ?
, assim em vez de capturar o máximo ele tenta capturar o mínimo.
Em geral se referencia o *?
, que casa com o máximo, mas tenta capturar o mínimo, neste caso o mínimo é 0.
Um erro comum
`teste .*?` // não faz sentido ter o `.*?`, pois ele não vai capturar nada.
Exemplo de mínimo
`teste`.macth(/.*?t/) // enquanto o `.*` iria capturar `test`, o mínimo captura apenas `t`
Performance
O quantificador guloso é mais rápido, pois ele vai comendo ate não dar mais, enquanto o não-guloso é mais lento pois verifica sempre se é o mínimo possível.
Analogia
Pensando novamente em pessoas comendo:
O guloso come ate não ter mais comida.
O não-guloso come um pouco verifica se é suficiente, então come mais um pouco e verifica se já é suficiente, e assim vai.
Guloso: busca até o final da string a ultima ocorrência, ou seja, pega o máximo possível.
Ex.:
Regex: maça .*
Input: maça melancia laranja
O que a regex irá pegar é: maça melancia laranja
Não Guloso busca até a primeira ocorrência, ou seja, pega o minimo possível, exemplos: ?
, {1}
Ex.:
Regex: maça .*?
Input: maça melancia laranja
O que a regex irá pegar é: maça
Expressões regulares Gulosas
consomem mais recurso do que asNão-Gulosas?
Analisando a rapida explicação acima, podemos concluir que a utilização de uma expressão regular gulosa em textos extensos irá consumir mais processamento e memoria.
Uma Regex gulosa (greedy) tenta combinar o maior número de vezes possível o padrão especificado, utiliza-se o asterisco para definir isso *
.
Uma expressão não gulosa combina o texto o minimo possível, ao encontrar a primeira ocorrência do padrão ela para.
Algumas expressões gulosas tendem a consumir mais recursos devido a elas analisarem o texto do contrario das não gulosas que analisam parte dele.
As outras respostas já explicaram o que é, mas acho que vale explicar como a regex trata internamente os quantificadores gulosos e não-gulosos, até mesmo para esclarecer o que foi dito em uma das respostas, que afirma que "o quantificador guloso é mais rápido" (só que isso não é sempre verdade, pois depende da expressão e da string sendo verificada).
E para entender melhor o motivo, vale explicar em detalhes como funcionam os quantificadores "gulosos" (ou "gananciosos" - tanto que em inglês costumam-se chamar greedy) e suas versões não-gulosas (ou "preguiçosos" - lazy).
Por exemplo, se tivermos esta string:
a,b,c,123,def,ghi,jkl,mno,pqr,stu,vxw,yz
E esta regex: ,.*,\d
(vírgula, zero ou mais caracteres, outra vírgula e um dígito). De acordo com o regex101.com, esta regex precisa de 48 passos para encontrar um match (a quantidade exata pode variar de uma engine para outra, mas em geral, para este exemplo específico, veremos que o quantificador greedy demora mais que o lazy).
Já se usarmos o quantificador não-guloso/lazy (ou seja, se mudarmos para ,.*?,\d
), a regex precisa de apenas 9 passos para encontrar um match.
Essa diferença se dá não porque o quantificador guloso tenta pegar a maior quantidade possível de caracteres, mas sim por causa da forma como isso é feito. E como ele faz isso? No regex101.com é possível debugar todos os passos da engine, mas basicamente ela faz o seguinte:
A regex vai avançando na string até encontrar a primeira vírgula (no caso, é a que está logo depois do "a")
O
.*
é guloso/greedy, então ele vai até o final da string (já que o ponto corresponde a qualquer caractere, e como o*
é guloso, então ele pega tudo de uma vez, avançando até o final da string). No regex101 (no link já citado) você pode ver esta ação no passo 3Depois a regex verifica a segunda vírgula da expressão (a que está depois do
.*
). Mas como a regex foi até o final da string, não há vírgula posterior, então ela faz o backtracking, ou seja, ela volta uma posição e tenta novamente. No caso, ela volta uma posição antes do fim (ou seja, para o "z"), e vê se depois dele tem uma vírgula. Como não tem, ela volta mais uma posição (para o "y"), vê se depois tem uma vírgula, e como não tem, volta mais uma posição e encontra a vírgula que está antes doy
Apenas para lembrar, até aqui, a regex pegou tudo da primeira vírgula (depois do "a") até a última vírgula (antes do "y"), e isso tudo corresponde ao trecho
,.*,
. Ou seja, ainda falta verificar o\d
:,.*,\d ↑ regex verificou até aqui (a segunda vírgula) a,b,c,123,def,ghi,jkl,mno,pqr,stu,vxw,yz ↑ ela já consumiu a string até este ponto
Mas como depois da vírgula tem o "y", que não corresponde a
\d
, então ela precisa voltar novamenteEntão ela volta para o "w", depois para o "x", para o "v", e encontra outra vírgula (a que está antes do "v") - no link de debug do regex101.com, este é o passo 12
Aí ela vê se depois desta vírgula tem um dígito. Mas como tem a letra "v" (que não corresponde a
\d
), ela volta novamente (para o "u", "t", "s", encontra outra vírgula, verifica se depois tem\d
, etc...)
Este vai e vem é repetido várias vezes, até que ela finalmente encontra a vírgula antes do "1", e vê que depois dela tem o 1
, que corresponde a \d
, e finalmente encontra o match, que é ,b,c,1
.
Já se debugarmos a regex com o quantificador lazy, veremos porque ela faz em menos passos:
- A regex vai avançando na string até encontrar a primeira vírgula (no caso, é a que está logo depois do "a")
- Como
.*?
é preguiçoso/não-guloso, primeiro ele tenta a menor quantidade possível, que no caso é zero (pois o quantificador*
significa "zero ou mais ocorrências"). Ou seja, ele vê se depois da primeira vírgula tem "zero caracteres seguido de vírgula". Mas como depois da primeira vírgula tem um "b", então ela consome esse "b" (ou seja, ele passa a "fazer parte" do.*?
) e vê o que tem depois - Depois do "b" tem uma vírgula, então a regex verifica se depois tem um
\d
. Mas como não tem, o.*?
passa a considerar todo o trecho "b,c". Então a regex vê que depois disso tem uma vírgula e um\d
e encontra o match,b,c,1
Fazendo um teste básico em Python, com o módulo timeit
:
from timeit import timeit
import re
# executa 1 milhão de vezes cada teste
params = { 'number': 1000000, 'globals': globals() }
s = 'a,b,c,123,def,ghi,jkl,mno,pqr,stu,vxw,yz'
greedy = re.compile(r',.*,\d')
lazy = re.compile(r',.*?,\d')
print(timeit('greedy.search(s)', **params))
print(timeit('lazy.search(s)', **params))
O tempo exato pode variar dependendo do hardware, etc, mas de forma geral, a regex gulosa demorou mais (na minha máquina, foi entre 60% a 70% mais demorada), e no IdeOne.com e no Repl.it os resultados foram similares.
Com JavaScript, a regex lazy também se mostrou mais rápida.
Enfim, "ser mais rápido" não tem nada a ver com a regex ser gulosa ou não, e sim com a expressão e a string sendo verificada.
Basta mudar a string do exemplo acima para, por exemplo, a,b,c,x23,def,ghi,jkl,mno,pqr,stu,vxw,1z
, que a regex gulosa se torna mais rápida. Isso acontece por causa da forma como o match é feito: na regex gulosa, já vimos que ela vai até o fim da string, e depois começa a voltar até encontrar um match, enquanto a lazy parte do início da string e vai avançando aos poucos até encontrar um match.
Então se o match estiver mais próximo do início da string, a regex lazy encontrará mais rápido, mas se o match estiver mais próximo do final da string, a regex gulosa é que será mais rápida (veja aqui e aqui como a situação se inverte se mudarmos a string).
Enfim, é importante entender as diferenças de funcionamento, em vez de confiar cegamente que o quantificador guloso sempre será mais rápido. Há casos e casos, e como já explicaram nas outras respostas, até mesmo o match encontrado pode ser diferente.
Dependendo da engine/linguagem/ferramenta, também podem ser feitas otimizações internas que dependem das circunstâncias (tanto da expressão quanto da string sendo verificada), que pode ou não influenciar na quantidade de passos necessários.
Embora essa pergunta foi feita há vários anos atrás, existem alguns equívocos que precisam ser corrigidos.
O *
não é o único quantificador guloso.
Os quantificadores gulosos são: ?
+
{}
*
Por exemplo, o opcional ?
casa 0 ou 1 vez o elemento anterior.
Texto ER Casou aa ...? aa aaa ...? aaaVeja que no segundo texto a ER casou com aaa em vez de aa.
Quantificadores gulosos sempre casarão com o máximo que ele puder.
No primeiro texto a ER casou com aa apenas porque não havia um terceiro caractere.
Já o {}
só não é guloso se você o usar na forma {numero}
.
Como em {3}
. Nesse caso ele é exato.
Nas outra formas ele também é guloso.
Os quantificadores não-gulosos são: ??
*?
+?
{}?
Ou seja, os quantificadores gulosos "colados" com uma ?
à sua direita.
Ao contrário dos gulosos, eles sempre casam com o mínimo possível.
Texto ER Casou aa ...?? aa aaa ...?? aa
Observe que embora o segundo texto seja maior, a ER ainda casou com aa.
Porquê? Porque o ??
não é guloso. Ele casou com o mínimo possível.
Um quantificador não-guloso mostra sua verdadeira utilidade quando há um elemento à sua direita. ele vai casando com os caracteres do texto, respeitando a quantidade máxima, até encontrar um caractere que também casa com o elemento à sua direita. nesse caso, ele, como um metacaractere cavalheiro, cede o caractere para seu vizinho, que então casa com esse caractere.
Já o guloso vai casando com tudo que ele pode, respeitando a quantidade máxima, até ele não ter mais nada para casar. Então o fominha olha para sua direita, só para ver seu vizinho o encarando feio. Sob livre e espontânea pressão, ele vai descasando caracteres, um por um, da direita para esquerda, até encontrar o caractere que o seu vizinho ranzinza quer casar, cedendo esse caractere para ele.
Embora a descrição diz "caractere" no singular, o elemento vizinho não necessariamente precisa casar com só um caractere. Ele poderia ser o metacaractere grupo ()
, agrupando vários metacaracteres representantes e caracteres literais e/ou ele ser seguido de um quantificador, podendo assim, representar mais de um caractere.
Para demonstrar, veja duas ER aplicadas no código html abaixo:
<b>negrito</b>
<p>parágrafo</p>
<strong>importante</strong>
<h1>título</h1>
Com a ER <.*>
:
<b>negrito</b>
<p>parágrafo</p>
<strong>importante</strong>
<h1>título</h1>
E com a ER <.*?>
:
<b>
negrito</b>
<p>
parágrafo</p>
<strong>
importante</strong>
<h1>
título</h1>
A parte destacada e em negrito é o que a ER casou.
Observe como a ER com o quantificador *
casou tudo do primeiro sinal de menor(<) até o último sinal de maior(>).
Enquanto a ER com o *?
só casou com as tags html.