Jaka jest różnica pomiędzy .*? i. * wyrażenia regularne?

142

Próbuję podzielić ciąg na dwie części za pomocą wyrażenia regularnego. Ciąg jest sformatowany w następujący sposób:

text to extract<number>

Używałem (.*?)<i <(.*?)>które działają dobrze, ale po lekkim przeczytaniu do wyrażenia regularnego zacząłem się zastanawiać, dlaczego potrzebuję ?wyrażeń. Zrobiłem to dopiero po znalezieniu ich na tej stronie, więc nie jestem do końca pewien, na czym polega różnica.

Doug
źródło
1
zobacz także stackoverflow.com/questions/2301285/…
Cemafor,

Odpowiedzi:

172

To jest różnica między chciwymi i niechciwymi kwantyfikatorami.

Rozważ dane wejściowe 101000000000100.

Korzystanie 1.*1, *jest chciwy - będzie on pasował do końca do końca, a potem wracać, dopóki można go dopasować 1, pozostawiając Państwu 1010000000001.
.*?nie jest chciwy. *niczego nie dopasuje, ale spróbuje dopasować dodatkowe znaki, aż do dopasowania 1, ostatecznie dopasowując 101.

Wszystkie kwantyfikatory posiada tryb non-chciwy: .*?, .+?, .{2,6}?, a nawet .??.

W twoim przypadku podobny wzorzec mógłby wyglądać <([^>]*)>- dopasowywanie czegokolwiek poza znakiem większości (ściśle rzecz biorąc, dopasowuje zero lub więcej znaków innych niż >między <i >).

Zobacz ściągawkę Quantifier .

Kobi
źródło
Ach, super, podoba mi się ten ostatni z wszystkiego oprócz znaku>!
Doug
1
Czy możesz wyjaśnić lub pokazać przykład, jak chciwy ?różni się od niechciwego ???
AdrianHHH
4
Pewnie. W przypadku łańcucha "abc"wyrażenie regularne /\w\w?\w/będzie pasowało do pełnego ciągu "abc"- ponieważ ?jest chciwe. /\w\w??\w/jest leniwy - będzie tylko pasował "ab". Wróci i dopasuje tylko "abc"wtedy, gdy później zawiedzie.
Kobi
184

O chciwym kontra niechciwym

Powtórzenia w wyrażeniu regularnym są domyślnie zachłanne : starają się dopasować jak najwięcej powtórzeń, a kiedy to nie działa i muszą się cofać, próbują dopasować o jedno powtórzenie mniej na raz, aż dopasowanie całego wzorca jest znaleziony. W rezultacie, gdy w końcu dojdzie do meczu, chciwe powtórzenie będzie pasowało do jak największej liczby powtórzeń.

?Jako powtórzenie kwantyfikator zmienia to zachowanie się nie chciwy , zwany też niechętnie ( w np Java ) (a czasem „leniwy”). W przeciwieństwie do tego powtórzenie najpierw spróbuje dopasować jak najmniejszą liczbę powtórzeń, a kiedy to nie zadziała i będą musieli się cofnąć, zaczną dopasowywać jeszcze jeden powtórzenie raz. W rezultacie, gdy w końcu dojdzie do meczu, niechętne powtórzenie będzie pasowało do jak najmniejszej liczby powtórzeń.

Bibliografia


Przykład 1: od A do Z

Porównajmy te dwa wzorce: A.*Zi A.*?Z.

Biorąc pod uwagę następujące dane wejściowe:

eeeAiiZuuuuAoooZeeee

Wzorce dają następujące dopasowania:

Najpierw skupmy się na tym, co A.*Zrobi. Kiedy pasował do pierwszego A, .*będąc chciwym, najpierw próbuje dopasować jak najwięcej ..

eeeAiiZuuuuAoooZeeee
   \_______________/
    A.* matched, Z can't match

Ponieważ Znie pasuje, silnik cofa się, a .*następnie musi dopasować o jeden mniej .:

eeeAiiZuuuuAoooZeeee
   \______________/
    A.* matched, Z still can't match

Dzieje się to jeszcze kilka razy, aż w końcu dojdziemy do tego:

eeeAiiZuuuuAoooZeeee
   \__________/
    A.* matched, Z can now match

Teraz Zmożna dopasować, więc ogólny wzorzec pasuje:

eeeAiiZuuuuAoooZeeee
   \___________/
    A.*Z matched

Z drugiej strony niechętne powtarzanie w A.*?Zpierwszych meczach .jak najmniej, a następnie biorąc więcej .w razie potrzeby. To wyjaśnia, dlaczego znajduje dwa dopasowania w danych wejściowych.

Oto wizualna reprezentacja dopasowania dwóch wzorców:

eeeAiiZuuuuAoooZeeee
   \__/r   \___/r      r = reluctant
    \____g____/        g = greedy

Przykład: alternatywa

W wielu zastosowaniach dwa dopasowania w powyższym wejściu są pożądane, dlatego niechętny .*?jest używany zamiast chciwego, .*aby zapobiec nadmiernemu dopasowaniu. Jednak dla tego konkretnego wzorca istnieje lepsza alternatywa, używając klasy znaków zanegowanych.

Wzorzec A[^Z]*Zznajduje również te same dwa dopasowania, co A.*?Zwzorzec dla powyższego wejścia ( jak widać na ideone.com ). [^Z]jest klasą znaków zanegowanych : pasuje do wszystkiego oprócz Z.

Główna różnica między tymi dwoma wzorcami polega na wydajności: będąc bardziej rygorystycznym, klasa znaków zanegowanych może pasować tylko w jeden sposób dla danego wejścia. Nie ma znaczenia, czy użyjesz chciwego lub niechętnego modyfikatora dla tego wzorca. W rzeczywistości w niektórych smakach można zrobić jeszcze lepiej i użyć tak zwanego kwantyfikatora zaborczego, który w ogóle się nie cofa.

Bibliografia


Przykład 2: od A do ZZ

Ten przykład powinien być ilustracyjny: pokazuje, w jaki sposób zachłanne, niechętne i zanegowane wzorce klas znaków różnie pasują do tych samych danych wejściowych.

eeAiiZooAuuZZeeeZZfff

Oto dopasowania dla powyższego wejścia:

Oto wizualna reprezentacja tego, co dopasowali:

         ___n
        /   \              n = negated character class
eeAiiZooAuuZZeeeZZfff      r = reluctant
  \_________/r   /         g = greedy
   \____________/g

powiązane tematy

Są to linki do pytań i odpowiedzi na temat stackoverflow, które obejmują niektóre interesujące tematy.

Jedno chciwe powtórzenie może przewyższyć inne

smary wielogenowe
źródło
1
Miałem na myśli rubular.com, a nie ideone.com. Dla innych: nie poprawiaj tego wpisu za mnie, zrobię to sam przy następnej wersji, wraz z innymi przykładami. Zapraszam do przekazywania opinii, sugestii itp. W komentarzach, abym mógł je również uwzględnić.
polygenelubricants
2
Zobacz też: stackoverflow.com/questions/3145023/…
polygenelubricants
4
Ta odpowiedź została dodana do często zadawanych pytań dotyczących wyrażeń regularnych przepełnienia stosu , w sekcji „Kwantyfikatory> Więcej o różnicach ...”
aliteralmind
Ta odpowiedź naprawdę zasługuje na to, aby być wybraną odpowiedzią! Dziękuję bardzo za szczegółowe wyjaśnienie.
masky007
Dodałem tag non-chciwy . Dlaczego, ponieważ pytanie tego wymagało, ale także dlatego, że skieruje więcej użytkowników do tej wspaniałej odpowiedzi. Innymi słowy, jeśli podasz świetną odpowiedź, a odpowiedź używa tagu, którego nie ma w pytaniu, dodaj tag, ponieważ OP nie wiedział, że tag był rewelacyjny.
Guy Coder
20

Powiedzmy, że masz:

<a></a>

<(.*)>pasowałaby a></atam, gdzie <(.*?)>pasowałaby a. Ten ostatni zatrzymuje się po pierwszym meczu >. Sprawdza, czy występuje jedno lub 0 dopasowań, .*po którym następuje następne wyrażenie.

Pierwsze wyrażenie <(.*)>nie kończy się na dopasowaniu do pierwszego >. Będzie trwać do ostatniego meczu >.

Szymon
źródło
jest to łatwiejsze do zrozumienia niż powyższe wyjaśnienie.
Prometeusz