Klarheit der Atomgruppen

8

Betrachten Sie diese Regex.

%Vor%

Dies wird bei aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

fehlschlagen

Dies erfordert 67 Schritte im Debugger zum Fehlschlagen.

Betrachten Sie nun diese Regex.

%Vor%

Dies wird im Fall von aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

fehlschlagen

Dies erfordert 133 Schritte im Debugger zum Fehlschlagen.

Und schließlich diese Regex:

%Vor%

Dies wird im Fall von aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

fehlschlagen

Dies erfordert 67 Schritte im Debugger zum Fehlschlagen.

Wenn ich den Benchmark atomic group (?>a*)b performes 179% schneller überprüfe.

Jetzt deaktivieren Atomgruppen das Zurückverfolgen. Leistung in Übereinstimmung ist also gut.

  1. Aber warum ist die Anzahl der Schritte mehr? Kann jemand das erklären?

  2. Warum gibt es einen Unterschied? in Schritten zwischen zwei Atomgruppen (?>a*)b und a*+b .

Arbeiten sie anders?

    
vks 29.09.2014, 06:10
quelle

3 Antworten

5
  

Anmerkung des Autors:

   Diese Antwort zielt auf Frage 1 ab, die durch den Bounty-Text geliefert wird. "Ich freue mich auf den genauen Grund, warum der Debugger mehr Schritte benötigt. Ich brauche keine Antworten, die erklären, wie atomare Gruppen funktionieren." ; < br> Jerrys Antwort spricht die anderen Bedenken sehr gut an, während meine andere Antwort nimmt eine Fahrt durch die erwähnten Konstrukte, wie sie funktionieren und warum sie wichtig sind. Für das volle Wissen reicht es nicht einfach diesen Beitrag zu lesen!

Jede Gruppe in einem regulären Ausdruck führt einen Schritt aus, um in die Gruppe zu gelangen.

WAS?!
Ja, ich meine es ernst, lesen Sie weiter ...

Zunächst möchte ich Ihnen quantifizierte Gruppen vorstellen, die nicht gefangen sind, ohne die Gruppe:

%Vor%

Also, was genau passiert hier? Wir werden die Muster mit der Testzeichenfolge "concat" auf einer Regex-Engine mit deaktivierten Optimierungen abgleichen:

Während wir dabei sind, präsentiere ich Ihnen einige weitere Gruppen:

Oh nein! Ich werde vermeiden, Gruppen zu verwenden!

Aber warten Sie! Beachten Sie, dass die Anzahl der Schritte, die zur Übereinstimmung mit unternommen wurden, keine Korrelation mit der Leistung der Übereinstimmung aufweist. pcre Suchmaschinen optimiert entfernt die meisten der "unnötigen Schritte", wie ich bereits erwähnt habe . Atomare Gruppen sind immer noch die effizientesten, obwohl mehr Schritte für eine Engine mit deaktivierten Optimierungen unternommen wurden.

Vielleicht relevant:

Unihedron 01.10.2014, 12:59
quelle
8

Was ist Backtracking?

Die Engine kommt zu Quantifizierern , die standardmäßig gierig sind. Gierige Modifikatoren passen zu allen möglichen und Backtracks nach Bedarf , was effiziente Treffer ermöglicht,

  

wie von Gierig vs. widerstrebend vs. Possessive Quantifier verwiesen:

     
    

Ein gieriger Quantifizierer passt zuerst so gut wie möglich zusammen. Also stimmt .* mit der gesamten Zeichenfolge überein. Dann versucht der Matcher, den folgenden f anzupassen, aber es sind keine Charaktere mehr übrig. Es "backtracks" also, so dass der gierige Quantifizierer mit einem Ding weniger übereinstimmt (das "o" am Ende des Strings bleibt unberücksichtigt). Das stimmt immer noch nicht mit dem f in der Regex überein, so dass es einen weiteren Schritt "zurückverfolgt", wodurch der gierige Quantifizierer erneut zu einem less thing passt (das "oo" am Ende der Zeichenkette bleibt unberücksichtigt). Das still stimmt nicht mit der f in der Regex überein, so dass es einen weiteren Schritt zurückverfolgt (wobei "foo" am Ende der Zeichenkette nicht zugeordnet bleibt). Jetzt stimmt der Matcher schließlich mit der f in der Regex überein, und die o und die nächste o werden ebenfalls abgeglichen. Erfolg! [...]

  

Was hat das mit a*+b ?

zu tun?

In /a*+b/ :

  • a Das Literalzeichen "a" .
  • *+ Null oder mehr, Possessiv .
  • b Das Literalzeichen "b" .
  

Wie von Gierig vs. widerstrebend im Vergleich zu Possessiv-Quantifizierern verwiesen:

     
    

Ein possessiver Quantifizierer ist genau wie der gierige Quantifizierer, aber er geht nicht zurück. Es beginnt also damit, dass .* mit der gesamten Zeichenfolge übereinstimmt und nichts unübertroffen bleibt. Dann ist nichts mehr übrig für die Übereinstimmung mit f in der Regex. Da der Possessiv-Quantor nicht zurückverfolgt wird, schlägt die Übereinstimmung fehl.

  

Warum ist das wichtig?

Die Maschine wird nicht erkennen, ob sie alleine eine (in) effiziente Übereinstimmung erzielt. Sehen Sie sich hier ein anständiges Beispiel an: Programm wird für immer ausgeführt, wenn regulärer Ausdruck gefunden wird . In vielen Szenarios sind Regexes, die schnell geschrieben werden, möglicherweise nicht effizient und können in der Bereitstellung leicht problematisch sein.

Also, was ist eine Atomgruppe?

Nachdem das Muster in der Atomgruppe die Übereinstimmung beendet hat, wird es nicht mehr loslassen. Studiere dieses Beispiel:

%Vor%

Sieht vollkommen legitim aus, aber diese Übereinstimmung schlägt fehl . Die Schritte sind einfach: Der erste Wechsel der Atomgruppe stimmt perfekt überein - \d\w{2} verbraucht 12c . Die Gruppe schließt dann ihre Übereinstimmung ab - jetzt ist hier unsere Zeigerposition:

%Vor%

Das Muster wird fortgesetzt. Jetzt versuchen wir, c zu finden, aber es gibt keine c . Anstatt zu versuchen, die Zurückverfolgung durchzuführen (Freigabe von \d\w{2} und konsumieren von 12 ), schlägt die Übereinstimmung fehl.

Nun, das ist eine schlechte Idee! Warum sollten wir Backtracking verhindern, Unihedron?

Stellen Sie sich nun vor, wir manipulieren mit einem JSON-Objekt. Diese Datei ist nicht klein. Backtracking vom Ende wird eine schlechte Idee sein.

%Vor%

Oh oh ...

Verstehst du, was ich jetzt meine? : P

Ich werde Sie verlassen, um den Rest herauszufinden, und versuchen, mehr über Possessivquantifizierer und Atomgruppen herauszufinden; Ich schreibe nichts anderes in diesen Beitrag. Hier kam der JSON her, ich sah die Antwort vor ein paar Tagen sehr inspirierend: REGEX neuformatieren .

Lesen Sie auch

Unihedron 29.09.2014 07:07
quelle
4

Ich denke, etwas stimmt nicht ...

Ich weiß nicht, wie Sie Ihr Benchmarking durchgeführt haben, aber sowohl a*+b als auch (?>a*)b sollten gleich sein. Um regulary-expressions.info (Hervorhebung von mir) zu zitieren:

  

Im Grunde schreiben Sie anstelle von X*+ (?>X*) . Es ist wichtig zu beachten, dass sowohl das quantifizierte Token X als auch der Quantifizierer innerhalb der Atomgruppe liegen. Auch wenn X eine Gruppe ist, müssen Sie noch eine zusätzliche Atomgruppe um ihn herum platzieren, um denselben Effekt zu erzielen. (?:a|b)*+ entspricht (?>(?:a|b)*) , nicht jedoch (?>a|b)* . Letzteres ist ein gültiger regulärer Ausdruck, der jedoch nicht den gleichen Effekt hat, wenn er als Teil eines größeren regulären Ausdrucks verwendet wird.

Und um das oben genannte zu bestätigen, habe ich Folgendes auf ideone ausgeführt:

%Vor%

Erhalten dieses als die Ausgabe:

%Vor%

Nun, ich bin auf keinen Fall ein PHP-Experte, also weiß ich nicht, ob dies der richtige Weg ist, um Sachen zu bewerten, aber das ist, dass sie alle die gleiche Leistung haben, was angesichts der Einfachheit erwartet wird die Aufgabe.

Dennoch, einige Dinge, die ich aus dem oben genannten bemerke:

Weder (?>a)*b noch (?>a*)b sind 179% schneller als ein anderer Regex; die oben genannten sind alle innerhalb von 7% voneinander.

Zurück zur eigentlichen Frage

  

Aber warum ist die Anzahl der Schritte mehr? Kann jemand das erklären?

Es ist zu beachten, dass die Anzahl der Schritte keine direkte Darstellung der Leistung einer Regex ist. Es ist ein Faktor, aber nicht die entscheidende Determinante. Es gibt mehrere Schritte, da die Aufschlüsselung Schritte enthält, bevor Sie die Gruppe betreten, und nachdem Sie die Gruppe ...

eingegeben haben %Vor%

Das sind zwei weitere Schritte wegen der Gruppe als die drei Schritte ...

%Vor%

Hier können Sie sagen, dass a*b dasselbe ist wie (?:a*)b , aber das letztere hat mehr Schritte:

%Vor%

Hinweis: Auch dort sehen Sie, dass regex101 die Schritte für die Anzahl der Schritte in a*b etwas optimiert hat.

Fazit

Possessive Quantoren und atomare Gruppen arbeiten unterschiedlich, je nachdem, wie Sie sie verwenden. Wenn ich das Beispiel eines regulären Ausdrucks nehme und es ein wenig verfeinere:

(?>a|b)*ac Übereinstimmung aabaac

Aber

(?:a|b)*+ac und (?>(?:a|b)*)ac stimmen nicht mit aabaac überein.

    
Jerry 01.10.2014 08:08
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Alternative für Constexpr-Funktionen