Ein Regex, mit dem nichts mithalten kann

131

Das mag nach einer dummen Frage klingen, aber ich hatte ein langes Gespräch mit einigen meiner Entwicklerkollegen und es klang nach einer lustigen Sache.

So; Was denkst du - wie sieht ein Regex aus, der niemals von einer Saite übertroffen wird?

Edit : Warum will ich das? Nun, erstens, weil ich es interessant finde, an einen solchen Ausdruck zu denken, und zweitens, weil ich ihn für ein Skript brauche.

In diesem Skript definiere ich ein Wörterbuch als Dictionary<string, Regex>. Dies enthält, wie Sie sehen, eine Zeichenfolge und einen Ausdruck.

Basierend auf diesem Wörterbuch erstelle ich Methoden, die alle dieses Wörterbuch nur als Referenz dafür verwenden, wie sie ihre Arbeit erledigen sollen. Eine davon vergleicht die regulären Ausdrücke mit einer analysierten Protokolldatei.

Wenn ein Ausdruck übereinstimmt, Dictionary<string, long>wird einem anderen ein Wert hinzugefügt, der vom Ausdruck zurückgegeben wird. Um alle Protokollnachrichten abzufangen, die nicht mit einem Ausdruck im Wörterbuch übereinstimmen, habe ich eine neue Gruppe mit dem Namen "unbekannt" erstellt.

Zu dieser Gruppe wird alles hinzugefügt, was mit nichts anderem übereinstimmt. Aber um zu verhindern, dass der "unbekannte" Ausdruck (aus Versehen) einer Protokollnachricht nicht entspricht, musste ich einen Ausdruck erstellen, der mit Sicherheit nie übereinstimmt, egal welche Zeichenfolge ich ihm gebe.

Da haben Sie also meinen Grund für diese "keine wirkliche Frage" ...

Florian Peschka
quelle
1
Beachten Sie, dass es sehr schwer ist, ein Negativ zu beweisen.
Lasse V. Karlsen
5
Interessant. Wo würden Sie eine solche Regex verwenden?
Charlie Salts
1
Ich werde hier festhalten, dass viele der obigen Kommentare und Antworten auf diese Frage ursprünglich von stackoverflow.com/questions/1845078/… stammen, was ich gefragt habe. Marc Gravell hat sie zusammengeführt, was meiner Meinung nach viele dieser Antworten ohne den genauen ursprünglichen Kontext bizarr macht, bis zu dem Punkt, dass einige Kommentare keinen Sinn ergeben. (Wahrscheinlich stiehlt auch potenzielle zukünftige Wiederholungspunkte.) Ich würde vorschlagen, dass Fragen mit solch detaillierten Hintergründen niemals "exakte Duplikate" sein könnten. Was auch immer ...
Peter Hansen
2
Diese Frage wurde zu den häufig gestellten Fragen zu Stapelüberlauf-regulären Ausdrücken unter "Advanced Regex-Fu" hinzugefügt .
Aliteralmind
3
"Beachten Sie, dass es sehr schwer ist, ein Negativ zu beweisen" - dies wird allgemein angenommen, ist jedoch völlig und offensichtlich falsch ... wie wir zumindest seit Euklid bewiesen haben, dass es keine größte Primzahl gibt. Und jeder Beweis von P ist ein Beweis für die Negation von (nicht P). Was wahr ist, ist, dass es schwierig ist, ein empirisches universelles, positives oder negatives zu beweisen, z. B. "alle Raben sind schwarz" oder "kein Rabe ist weiß". Algorithmen sind analytisch und nicht empirisch, daher ist dies eine besonders schlimme Fehlanwendung der Scheinregel. Ein Beweis, dass das Muster 'a' nicht mit einer Zeichenfolge übereinstimmt, die mit 'b' beginnt, ist nicht "sehr schwer".
Jim Balter

Antworten:

66

Dies ist eigentlich recht einfach, obwohl es von der Implementierung / Flags * abhängt :

$a

Entspricht einem Zeichen anach dem Ende der Zeichenfolge. Viel Glück.

WARNUNG:
Dieser Ausdruck ist teuer - er scannt die gesamte Zeile, findet den Zeilenende-Anker und findet erst dann den nicht aund gibt eine negative Übereinstimmung zurück. (Siehe Kommentar unten für weitere Einzelheiten.)


* Ursprünglich habe ich nicht viel über Regexp im Multiline-Modus nachgedacht, bei dem $auch das Ende einer Zeile übereinstimmt. Tatsächlich würde es mit der leeren Zeichenfolge direkt vor der neuen Zeile übereinstimmen , sodass ein gewöhnliches Zeichen wie aniemals danach erscheinen kann $.

Ferdinand Beyer
quelle
50
Dieser Ausdruck ist teuer - er scannt die gesamte Zeile, findet den Zeilenende-Anker und findet erst dann nicht das "a" und gibt eine negative Übereinstimmung zurück. Ich sehe, dass das Scannen einer ~ 275k-Zeilendatei ~ 480 ms dauert. Die Umkehrung "a ^" dauert ungefähr die gleiche Zeit, auch wenn sie effizienter erscheint. Andererseits muss ein negativer Lookahead nichts scannen: "(?! X) x" (alles, dem kein x folgt, gefolgt von einem x, dh nichts) dauert ungefähr 30 ms oder weniger als 7% der Zeit. (Gemessen mit Gnu-Zeit und Egrep.)
Arantius
1
In Perl entspricht dies dem aktuellen Wert von $a. Das Perl-Äquivalent $(?:a)ist auch sehr langsam perl -Mre=debug -e'$_=a x 50; /$(?:a)/'.
Brad Gilbert
@arantius, bitte sehen Sie meine Antwort bezüglich des Timings , da ich das genaue Gegenteil gefunden habe, gemessen mit timeitund python3.
Nivk
Es ist nicht schockierend, dass sechs Jahre und eine Hauptversion von Python die Dinge ändern könnten.
Arantius
1
Entspricht in der POSIX BRE-Syntax $adem Literaltext $a, da er $als Anker in diesem Muster ungültig ist.
Phils
76

Hebelwirkung negative lookahead:

>>> import re
>>> x=r'(?!x)x'
>>> r=re.compile(x)
>>> r.match('')
>>> r.match('x')
>>> r.match('y')

Diese RE ist ein Widerspruch und wird daher niemals mit irgendetwas übereinstimmen.

HINWEIS:
In Python fügt re.match () implizit \Aam Anfang des regulären Ausdrucks einen Zeichenfolgenanfang ( ) an. Dieser Anker ist wichtig für die Leistung: Ohne ihn wird die gesamte Zeichenfolge gescannt. Diejenigen, die Python nicht verwenden, möchten den Anker explizit hinzufügen:

\A(?!x)x
Alex Martelli
quelle
@Chris, yep - also (?=x)(?!x)und so weiter (Verkettungen von widersprüchlichen Lookaheads und dasselbe für Lookbehinds), und viele davon funktionieren auch für beliebige Werte von x(Lookbehinds benötigen xs, die mit Zeichenfolgen fester Länge übereinstimmen).
Alex Martelli
1
Scheint gut zu funktionieren. Aber was ist stattdessen nur (?!)? Da () immer übereinstimmt, würde ((!)) Nicht garantiert nie übereinstimmen?
Peter Hansen
2
@Peter, ja, wenn Python diese Syntax akzeptiert (und die neuesten Versionen scheinen dies zu tun), wäre dies ebenfalls widersprüchlich. Eine andere Idee (nicht ganz so elegant, aber je mehr Ideen Sie bekommen, desto wahrscheinlicher ist es, dass Sie eine finden r'a\bc', die für alle interessierenden RE-Engines funktioniert): Suchen Sie nach einer Wortgrenze, die auf beiden Seiten unmittelbar von Buchstaben umgeben ist (Variante: Nichtwortzeichen auf beide Seiten).
Alex Martelli
1
Interessanterweise wird mein Original mit einem einfachen Literal, von dem ich "weiß", dass es nicht in meiner Eingabe erscheint, in Python als das schnellste herausgestellt. Bei einer 5-MB-Eingabezeichenfolge und bei Verwendung in einer sub () -Operation dauert (?! X) x 21% länger, (?! ()) 16% und ($ ^) 6% länger. Kann in einigen Fällen von Bedeutung sein, in meinen jedoch nicht.
Peter Hansen
2
Das kann ziemlich langsam sein perl -Mre=debug -e'$_=x x 8; /(?!x)x/'. Sie können es schneller machen, indem Sie es am Anfang \A(?!x)xoder am Ende verankern (?!x)x\z. perl -Mre=debug -e'$_=x x 8; /(?!x)x\z/; /\A(?!x)x/'
Brad Gilbert
43

Eine, die vermisst wurde:

^\b$

Es kann nicht übereinstimmen, da die leere Zeichenfolge keine Wortgrenze enthält. In Python 2.5 getestet.

Mark Byers
quelle
7
Dies ist die beste Antwort. Es verwendet keine Lookaheads, bricht bei einigen Regex-Implementierungen nicht ab, verwendet kein bestimmtes Zeichen (z. B. 'a') und schlägt in maximal 3 Verarbeitungsschritten (gemäß regex101.com) fehl, ohne das Ganze zu scannen Eingabezeichenfolge. Dies ist auch auf einen Blick leicht zu verstehen.
CubicleSoft
1
Dies schlägt in Emacs unter bestimmten Bedingungen tatsächlich fehl (wenn am Anfang oder Ende des Puffers eine Leerzeile steht), \`\b\'funktioniert jedoch , indem "Anfang / Ende des Textes" durch die Emacs-Syntax ersetzt wird (im Gegensatz zu "Anfang / Ende" der Linie ").
Phils
35

umschauen:

(?=a)b

Für Regex-Neulinge: Der positive Blick nach vorne (?=a)stellt sicher, dass das nächste Zeichen ist a, ändert jedoch nicht den Suchort (oder fügt das 'a' in die übereinstimmende Zeichenfolge ein). Nachdem das nächste Zeichen bestätigt wurde, stimmt ader verbleibende Teil von regex ( b) nur dann überein, wenn das nächste Zeichen ist b. Daher stimmt diese Regex nur überein, wenn ein Zeichen beide aund bgleichzeitig ist.

Amarghosh
quelle
30

a\bc, wobei \bes sich um einen Ausdruck mit der Breite Null handelt, der der Wortgrenze entspricht.

Es kann nicht in der Mitte eines Wortes erscheinen, zu dem wir es zwingen.

P Shved
quelle
Wenn Sie in Ihrem Anwendungsfall das Muster am Anfang der Zeichenfolge verankern können, verhindert diese Verbesserung, dass die Regexp-Engine nach jeder Instanz von a aim Text sucht und diese testet .
Phils
20

$.

.^

$.^

(?!)

Knio
quelle
1
Niedlich! Mein Unterbewusstsein lenkte mich von Ideen wie den ersten drei ab, da sie "illegal" sind ... konzeptionell, aber offensichtlich nicht zur Regex. Ich erkenne den (!) Nicht ... muss ihn nachschlagen.
Peter Hansen
1
Okay, dann gefällt mir die (?!) Antwort ... effektiv, was Alex vorgeschlagen hat. Beachten Sie, dass in stackoverflow.com/questions/1723182 (auf das Amarghosh oben hingewiesen hat) jemand behauptet, "einige Varianten" von Regex würden dies als Syntaxfehler betrachten. Python gefällt es aber gut. Beachten Sie, dass alle anderen Vorschläge mit den Modi re.DOTALL | re.MULTILINE in Python fehlschlagen würden.
Peter Hansen
1
Wurde dies getestet? Ich hätte angenommen, dass dies ^nur als erstes Zeichen eines $regulären Ausdrucks eine besondere Bedeutung hat und nur am Ende eines regulären Ausdrucks eine besondere Bedeutung hat, es sei denn, der reguläre Ausdruck ist ein mehrzeiliger Ausdruck.
PP.
Eigentlich /$./bedeutet in Perl etwas ganz anderes. Dies bedeutet, dass der aktuelle Wert von $.(Eingabezeilennummer) übereinstimmt . Sogar /$(.)/könnte etwas passen, wenn Sie use re '/s';vorher geschrieben haben. ( perl -E'say "\n" =~ /$(.)/s || 0')
Brad Gilbert
In der POSIX BRE-Syntax, ^und $sind nur am Anfang bzw. Ende des Musters speziell, so dass keines von $.oder .^oder $.^funktionieren würde. (?!)ist eine Perl / PCRE-Funktion, glaube ich.
Phils
13

Maximale Übereinstimmung

a++a

Mindestens eine, agefolgt von einer beliebigen Anzahl a, ohne Rückverfolgung. Versuchen Sie dann, eine weitere zu findena .

oder Unabhängiger Unterausdruck

Dies entspricht dem Einfügen a+eines unabhängigen Unterausdrucks, gefolgt von einem anderen a.

(?>a+)a
Brad Gilbert
quelle
10

Perl 5.10 unterstützt spezielle Steuerwörter namens "Verben", die der (*...)Reihe nach eingeschlossen sind. (Vergleiche mit einer (?...)speziellen Reihenfolge.) Darunter befindet sich auch das (*FAIL)Verb das sofort vom regulären Ausdruck zurückkehrt.

Beachten Sie, dass Verben kurz darauf auch in PCRE implementiert werden, sodass Sie sie auch in PHP oder anderen Sprachen mithilfe der PCRE-Bibliothek verwenden können. (Sie können jedoch nicht in Python oder Ruby. Sie verwenden ihre eigene Engine.)

Kang Seonghoon
quelle
In den Dokumenten unter perldoc.perl.org/perlre.html#%28%2AFAIL%29-%28%2AF%29 heißt es: "Dieses Muster stimmt mit nichts überein und schlägt immer fehl. Es entspricht (?!), Ist aber einfacher Lesen Sie. Tatsächlich wird (?!) intern in (* FAIL) optimiert. " Interessant, da (?!) Meine bisherige "reine" Lieblingsantwort ist (obwohl sie in Javascript nicht funktioniert). Vielen Dank.
Peter Hansen
10
\B\b

\b stimmt mit Wortgrenzen überein - die Position zwischen einem Buchstaben und einem Nichtbuchstaben (oder der Zeichenfolgengrenze).
\Bist seine Ergänzung - es entspricht der Position zwischen zwei Buchstaben oder zwischen Nichtbuchstaben.

Zusammen können sie keiner Position entsprechen.

Siehe auch:

Kobi
quelle
Dies scheint eine ausgezeichnete Lösung zu sein, vorausgesetzt, sie ist an einem bestimmten Punkt verankert (der Anfang des Textes erscheint sinnvoll). Wenn Sie das nicht tun, ist dies eine schreckliche Lösung, da jede Nicht-Wortgrenze im Text getestet wird, um festzustellen, ob auf eine Wortgrenze folgt! Die vernünftige Version wäre also so etwas wie ^\B\b. In Sprachen, in denen "Textanfang" und "Zeilenanfang" unterschiedliche Syntax haben, möchten Sie die Syntax "Textanfang" verwenden, andernfalls testen Sie jede Zeile. (zB in Emacs wäre dies \`\B\boder "\\`\\B\\b".)
Phils
Trotzdem habe ich jetzt festgestellt, dass der angegebene Zweck dieser Frage darin besteht, einen regulären Ausdruck für die Verwendung in einer Gruppe zu erhalten. In diesem Fall ^ist dies bei bestimmten regulären Ausdruckssyntaxen (z. B. POSIX BRE) problematisch, bei denen ^es sich nur um einen Anker handelt, wenn es sich um das erste Zeichen handelt des Musters und entspricht ansonsten einem wörtlichen ^Zeichen.
Phils
@phils - Ich denke, Sie überdenken es :)- dies ist eine unpraktische Frage, bei der das Ziel darin bestand, eine interessante Antwort zu finden - keine effiziente Antwort. Das Muster kann jedoch in der Liner-Zeit (mit der Größe der Zielzeichenfolge) verworfen werden, sodass es für einen regulären Ausdruck nicht schlecht ist. Die meisten Muster hier sind gleich und können sogar ^linear sein, wenn es nicht optimiert ist.
Kobi
Betreff: Optimierungen, ich bin bereit, eine Regexp-Engine zu ignorieren, die hofft, "den Anfang des Textes" an einer anderen Position zu finden :)
Phils
Es ist auch keine so unpraktische Frage und Antwort - der einzige Grund, warum ich hier gelandet bin, war zu sehen, ob jemand eine effizientere Lösung für meine eigene vorschlagen kann, um eine bestimmte Emacs-Variable zu konfigurieren, für die ein Regexp-Wert erforderlich ist, die ich aber wollte effektiv deaktivieren.
Phils
8

Das scheint zu funktionieren:

$.
Jerry Fernholz
quelle
2
Das ähnelt dem Beispiel von Ferdinand Beyer.
Gumbo
9
Und es wird im Punkt-Übereinstimmungs-Zeilenumbruch-Modus übereinstimmen.
Tim Pietzcker
In Perl stimmt das tatsächlich mit der aktuellen Eingabezeilennummer überein $.. In diesem Fall müssen Sie auf $(.)oder gleichwertiger zurückgreifen $(?:.).
Brad Gilbert
Entspricht in der POSIX BRE-Syntax $.einem Literal, $gefolgt von einem beliebigen Zeichen, da $es als Anker in diesem Muster ungültig ist.
Phils
8

Wie wäre es $^oder vielleicht (?!)

Bob
quelle
3
Ein Zeilenumbruch wird durch diesen Ausdruck in dem Modus abgeglichen, in dem ^der Anfang und $das Ende einer Zeile übereinstimmen .
Gumbo
4
Vielleicht meinte er (?!)- einen negativen Lookahead für eine leere Zeichenfolge. Einige Regex-Varianten behandeln dies jedoch auch als Syntaxfehler.
Alan Moore
1
Eine leere Zeichenfolge entspricht der ersten, zumindest in JavaScript.
Roland Pihlakas
In der POSIX BRE-Syntax $^werden diese Literalzeichen übereinstimmen, da die Zeichen als Anker ungültig sind (dh der Grund, warum Sie das Muster verwendet haben, führt dazu, dass es nicht das tut, was Sie wollten.)
Phils
5

Das schnellste wird sein:

r = re.compile(r'a^')
r.match('whatever')

'a' kann ein beliebiges nicht spezielles Zeichen sein ('x', 'y'). Die Implementierung von Knio ist vielleicht etwas reiner, aber diese ist schneller für alle Zeichenfolgen, die nicht mit dem von Ihnen ausgewählten Zeichen anstelle von 'a' beginnen, da sie in diesen Fällen nicht nach dem ersten Zeichen, sondern nach dem zweiten übereinstimmen.

Adam Nelson
quelle
In der Tat wäre (. ^) In meinem Fall ungefähr 10% langsamer als (\ x00 ^).
Peter Hansen
1
Ich akzeptiere dies, da die Verwendung eines anderen Werts als \ n als Zeichen garantiert nie übereinstimmt und ich es als etwas lesbarer (da relativ wenige Personen Regex-Experten sind) als die Option (?! X) x betrachte , obwohl ich das auch gewählt habe. In meinem Fall würde ich für beide Optionen einen Kommentar benötigen, um dies zu erklären. Ich denke, ich werde meinen ursprünglichen Versuch einfach auf '\ x00NEVERMATCHES ^' anpassen. Ich erhalte die Nichtübereinstimmungsgarantie für diese Antwort mit meiner ursprünglichen Selbstdokumentation. Vielen Dank an alle für die Antworten!
Peter Hansen
3
Funktioniert das tatsächlich und wenn ja, wer hat sich entschieden, mit Unix zu brechen? In Unix-Regexps ^ist nur als erstes Zeichen und ähnlich mit $. Mit jedem Unix-Tool stimmt dieser reguläre Ausdruck mit allem überein, der die Literalzeichenfolge enthält a^.
JaakkoK
Heh, das ist ein guter Angriff. Ich habe nie gegen diese wörtliche Zeichenfolge getestet.
Adam Nelson
Oh, wenn das Unix-Regexps bricht, dann wirst du lieben >^.
CubicleSoft
4

Python wird es nicht akzeptieren, aber Perl wird:

perl -ne 'print if /(w\1w)/'

Diese Regex sollte (theoretisch) versuchen, eine unendliche (gerade) Anzahl von ws zu finden, da die erste Gruppe (die ()s) in sich selbst rekursiv ist. Perl scheint keine Warnungen auszugeben, auch nicht unter use strict; use warnings;, daher gehe ich davon aus, dass es zumindest gültig ist und meine (minimalen) Tests mit nichts übereinstimmen, also reiche ich es für Ihre Kritik ein.

Chris Lutz
quelle
1
Theorie ist immer schön, aber in der Praxis würde ich mir Sorgen um reguläre Ausdrücke machen, deren Beschreibungen das Wort "unendlich" enthielten!
Peter Hansen
perl -Mre=debug -e'"www wwww wwwww wwwwww" =~ /(w\1w)/'
Brad Gilbert
@BradGilbert - Wenn Sie das hier ausführen (5.10, etwas veraltet), wird "Regex fehlgeschlagen" erzeugt, wie vom OP angefordert. Stimmt es auf Ihrem System überein?
Chris Lutz
4

[^\d\D]oder (?=a)boder a$aodera^a

Bart Kiers
quelle
Vielen Dank. Beachten Sie, dass (?! X) x die erste Antwort war, die oben aufgeführt wurde.
Peter Hansen
Ja, anscheinend habe ich die anderen Antwortenden zu schnell gescannt.
Bart Kiers
4

Dies funktioniert nicht für Python und viele andere Sprachen, ist jedoch in einem Javascript-Regex []eine gültige Zeichenklasse, die nicht zugeordnet werden kann. Folgendes sollte also sofort fehlschlagen, unabhängig von der Eingabe:

var noMatch = /^[]/;

Ich mag es besser als /$a/weil es mir klar seine Absicht kommuniziert. Und wann immer Sie es jemals brauchen würden, ich brauchte es, weil ich einen Fallback für ein dynamisch kompiliertes Muster brauchte, das auf Benutzereingaben basiert. Wenn das Muster ungültig ist, muss ich es durch ein Muster ersetzen, das mit nichts übereinstimmt. Vereinfacht sieht es so aus:

try {
    var matchPattern = new RegExp(someUserInput);
}
catch (e) {
    matchPattern = noMatch;
}
nicht definiert
quelle
4

Alle Beispiele mit einem Boundary Matcher folgen demselben Rezept. Rezept:

  1. Nehmen Sie einen der Boundary Matcher: ^, $, \ b, \ A, \ Z, \ z

  2. Machen Sie das Gegenteil von dem, wofür sie bestimmt sind

Beispiele:

^ und \ A sind für den Anfang gedacht, verwenden Sie sie also nicht am Anfang

^ --> .^
\A --> .\A

\ b stimmt mit einer Wortgrenze überein, verwenden Sie sie also dazwischen

\b --> .\b.

$, \ Z und \ z sind für das Ende gedacht, verwenden Sie sie also am Ende nicht

$ --> $.
\Z --> \Z.
\z --> \z.

Andere beinhalten die Verwendung von Lookahead und Lookbehind, die ebenfalls mit der gleichen Analogie funktionieren: Wenn Sie einen positiven oder negativen Lookahead geben, gefolgt von etwas Gegenteiligem

(?=x)[^x]
(?!x)x

Wenn Sie positiv oder negativ aussehen, folgen Sie etwas Gegenteiligem

[^x](?<=x)
x(?<!x)

Es könnte mehr solche Muster und mehr solche Analogien geben.

Arun
quelle
3

So viele gute Antworten!

Ähnlich wie bei @ nivks Antwort möchte ich den Leistungsvergleich für Perl für verschiedene Varianten von nie übereinstimmendem regulären Ausdruck teilen.

  1. Eingabe: Pseudozufällige ASCII-Zeichenfolgen (25.000 verschiedene Zeilen, Länge 8-16):

Regex-Geschwindigkeit:

Total for   \A(?!x)x: 69.675450 s, 1435225 lines/s
Total for       a\bc: 71.164469 s, 1405195 lines/s
Total for    (?>a+)a: 71.218324 s, 1404133 lines/s
Total for       a++a: 71.331362 s, 1401907 lines/s
Total for         $a: 72.567302 s, 1378031 lines/s
Total for     (?=a)b: 72.842308 s, 1372828 lines/s
Total for     (?!x)x: 72.948911 s, 1370822 lines/s
Total for       ^\b$: 79.417197 s, 1259173 lines/s
Total for         $.: 88.727839 s, 1127041 lines/s
Total for       (?!): 111.272815 s, 898692 lines/s
Total for         .^: 115.298849 s, 867311 lines/s
Total for    (*FAIL): 350.409864 s, 285380 lines/s
  1. Eingabe: / usr / share / dict / words (100.000 englische Wörter).

Regex-Geschwindigkeit:

Total for   \A(?!x)x: 128.336729 s, 1564805 lines/s
Total for     (?!x)x: 132.138544 s, 1519783 lines/s
Total for       a++a: 133.144501 s, 1508301 lines/s
Total for    (?>a+)a: 133.394062 s, 1505479 lines/s
Total for       a\bc: 134.643127 s, 1491513 lines/s
Total for     (?=a)b: 137.877110 s, 1456528 lines/s
Total for         $a: 152.215523 s, 1319326 lines/s
Total for       ^\b$: 153.727954 s, 1306346 lines/s
Total for         $.: 170.780654 s, 1175906 lines/s
Total for       (?!): 209.800379 s, 957205 lines/s
Total for         .^: 217.943800 s, 921439 lines/s
Total for    (*FAIL): 661.598302 s, 303540 lines/s

(Ubuntu unter Intel i5-3320M, Linux-Kernel 4.13, Perl 5.26)

Filiprem
quelle
Hier ist ein JavaScript-Vergleich einiger hier behandelter Methoden: jsperf.com/regex-that-never-matches
thdoan
2

Ich glaube das

\Z RE FAILS! \A

deckt sogar Fälle ab, in denen der reguläre Ausdruck Flags wie MULTILINE, DOTALL usw. enthält.

>>> import re
>>> x=re.compile(r"\Z RE FAILS! \A")
>>> x.match('')
>>> x.match(' RE FAILS! ')
>>>

Ich glaube (aber ich habe es nicht bewertet), dass unabhängig von der Länge (> 0) der Zeichenfolge zwischen \Zund \Adie Zeit bis zum Ausfall konstant sein sollte.

tzot
quelle
2
(*FAIL)

oder

(*F)

Mit PCRE und PERL können Sie dieses Backtracking-Steuerverb verwenden, das das Muster zum sofortigen Fehlschlagen zwingt.

Casimir et Hippolyte
quelle
2

Nachdem ich einige dieser großartigen Antworten gesehen hatte, veranlasste mich der Kommentar von @ arantius (in Bezug auf Timing $xvs x^vs (?!x)x) zu der aktuell akzeptierten Antwort, einige der bisher gegebenen Lösungen zeitlich festzulegen .

Unter Verwendung des 275k-Zeilenstandards von @ arantius habe ich die folgenden Tests in Python (v3.5.2, IPython 6.2.1) ausgeführt.

TL; DR: 'x^'und 'x\by'sind mit einem Faktor von mindestens ~ 16 die schnellsten und gehörten entgegen @ arantius 'Feststellung (?!x)xzu den langsamsten (~ 37-mal langsamer). Die Geschwindigkeitsfrage ist also sicherlich implementierungsabhängig. Testen Sie es selbst auf Ihrem vorgesehenen System, bevor Sie festlegen, ob Geschwindigkeit für Sie wichtig ist.

UPDATE: Es gibt anscheinend eine große Diskrepanz zwischen Timing 'x^'und 'a^'. Weitere Informationen finden Sie in dieser Frage und in der vorherigen Bearbeitung für die langsameren Timings mit aanstelle von x.

In [1]: import re

In [2]: with open('/tmp/longfile.txt') as f:
   ...:     longfile = f.read()
   ...:     

In [3]: len(re.findall('\n',longfile))
Out[3]: 275000

In [4]: len(longfile)
Out[4]: 24733175

In [5]: for regex in ('x^','.^','$x','$.','$x^','$.^','$^','(?!x)x','(?!)','(?=x)y','(?=x)(?!x)',r'x\by',r'x\bx',r'^\b$'
    ...: ,r'\B\b',r'\ZNEVERMATCH\A',r'\Z\A'):
    ...:     print('-'*72)
    ...:     print(regex)
    ...:     %timeit re.search(regex,longfile)
    ...:     
------------------------------------------------------------------------
x^
6.98 ms ± 58.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
------------------------------------------------------------------------
.^
155 ms ± 960 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$x
111 ms ± 2.12 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$.
111 ms ± 1.76 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$x^
112 ms ± 1.14 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$.^
113 ms ± 1.44 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$^
111 ms ± 839 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
(?!x)x
257 ms ± 5.03 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
------------------------------------------------------------------------
(?!)
203 ms ± 1.56 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
(?=x)y
204 ms ± 4.84 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
------------------------------------------------------------------------
(?=x)(?!x)
210 ms ± 1.66 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
------------------------------------------------------------------------
x\by
7.41 ms ± 122 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
------------------------------------------------------------------------
x\bx
7.42 ms ± 110 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
------------------------------------------------------------------------
^\b$
108 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
\B\b
387 ms ± 5.77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
------------------------------------------------------------------------
\ZNEVERMATCH\A
112 ms ± 1.52 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
\Z\A
112 ms ± 1.38 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Als ich dies zum ersten Mal ausführte, vergaß ich, rdie letzten drei Ausdrücke zu vergessen, und wurde daher als Rücktaste '\b'interpretiert '\x08'. Zu meiner Überraschung war es 'a\x08c'jedoch schneller als das bisher schnellste Ergebnis! Um fair zu sein, es wird immer noch zu diesem Text passen, aber ich dachte, es wäre immer noch erwähnenswert, weil ich nicht sicher bin, warum es schneller ist.

In [6]: for regex in ('x\by','x\bx','^\b$','\B\b'):
    ...:     print('-'*72)
    ...:     print(regex, repr(regex))
    ...:     %timeit re.search(regex,longfile)
    ...:     print(re.search(regex,longfile))
    ...:     
------------------------------------------------------------------------
y 'x\x08y'
5.32 ms ± 46.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
None
------------------------------------------------------------------------
x 'x\x08x'
5.34 ms ± 66.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
None
------------------------------------------------------------------------
$ '^\x08$'
122 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
None
------------------------------------------------------------------------
\ '\\B\x08'
300 ms ± 4.11 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
None

Meine Testdatei wurde mit einer Formel für "... lesbare Inhalte und keine doppelten Zeilen" (unter Ubuntu 16.04) erstellt:

$ ruby -e 'a=STDIN.readlines;275000.times do;b=[];rand(20).times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > /tmp/longfile.txt

$ head -n5 /tmp/longfile.txt 
unavailable speedometer's garbling Zambia subcontracted fullbacks Belmont mantra's
pizzicatos carotids bitch Hernandez renovate leopard Knuth coarsen
Ramada flu occupies drippings peaces siroccos Bartók upside twiggier configurable perpetuates tapering pint paralyzed
vibraphone stoppered weirdest dispute clergy's getup perusal fork
nighties resurgence chafe
nivk
quelle
\B\bist in Bezug auf die Leistung schrecklich fehlerhaft (wie jedes Muster, das nicht an einer Position verankert ist, aber dieses Muster ist besonders schlecht). Versuchen Sie ^\B\bstattdessen Benchmarking .
Phils
2

Leere Regex

Der beste reguläre Ausdruck, der niemals mit etwas übereinstimmt, ist ein leerer regulärer Ausdruck. Aber ich bin nicht sicher, ob alle Regex-Engines das akzeptieren werden.

Unmöglicher Regex

Die andere Lösung besteht darin, einen unmöglichen regulären Ausdruck zu erstellen. Ich habe festgestellt, dass $-^die Berechnung unabhängig von der Größe Ihres Textes nur zwei Schritte dauert ( https://regex101.com/r/yjcs1Z/1 ).

Als Referenz:

  • $^und $.mache 36 Schritte, um zu berechnen -> O (1)
  • \b\B macht 1507 Schritte in meinem Sample und erhöht sich mit der Anzahl der Zeichen in Ihrer Zeichenfolge -> O (n)

Populärer Thread zu dieser Frage:

Äon
quelle
1

Vielleicht das?

/$.+^/
Dan Breen
quelle
In Python funktioniert dieser Ansatz nur, wenn Sie die Flags steuern : re.compile('$.+^', re.MULTILINE|re.DOTALL).search('a\nb\nc\n')Gibt ein Übereinstimmungsobjekt zurück, das dem b und c (und allen benachbarten und dazwischen liegenden Zeilenumbrüchen) entspricht. Der von mir empfohlene Negativ-Lookahead-Ansatz funktioniert (dh passt nicht zu irgendetwas) für jede Kombination von Flags, mit denen er kompiliert werden könnte.
Alex Martelli
Mein schlechtes - verwechselt das $und ^.
Chris Lutz
1
Dies mag ein Versuch sein, das Ende eines Strings vor dem Anfang zu suchen , aber ich habe festgestellt, dass $ nicht "Ende des Strings" bedeutet, es sei denn, es ist das letzte Zeichen der Regex, und ich erwarte, dass ein ähnliches Verhalten zutrifft bis ^, so könnte dies mit einem Teilstring übereinstimmen, der mit einem Literal $ beginnt und mit einem Literal endet ^
pavium
@pavium, in Python oder Javascript verhält es sich sicherlich nicht so. Sonderzeichen wie $ und ^ sollten nicht als Literale behandelt werden, es sei denn, Sie maskieren sie mit \ oder fügen sie in einen Zeichensatz mit [] ein. In welcher Sprache haben Sie das beobachtet?
Peter Hansen
Zumindest in Perl sollte dies geschrieben werden /\z.+\A/(siehe perldoc perlre ). Dies verhindert, dass der Mehrzeilen- und Einzeilenmodus ( use re '/ms') dies beeinflusst.
Brad Gilbert
0
'[^0-9a-zA-Z...]*'

und ... durch alle druckbaren Symbole ersetzen;). Das ist für eine Textdatei.

Drakosha
quelle
Ich denke, dafür muss es einen kürzeren Weg geben, aber das war auch mein erster Gedanke ^^
FP
4
Dies entspricht der leeren Zeichenfolge. Verwenden Sie [^\x00-\xFF]+(für bytebasierte Implementierungen), um jedes mögliche Zeichen abzufangen.
Ferdinand Beyer
6
Ein besserer Ausdruck wäre [^\s\S]. Aber wie Ferdinand Beyer bereits sagte, würde es zu einer leeren Zeichenfolge passen.
Gumbo
3
Drakoshas Regex kann aufgrund der *; Lassen Sie das weg oder ersetzen Sie es durch +, und es muss mindestens einem Zeichen entsprechen. Wenn die Klasse alle möglichen Zeichen ausschließt, kann sie mit nichts übereinstimmen.
Alan Moore
0

Was ist mit anstelle von Regex, verwenden Sie einfach eine immer falsche if-Anweisung? In Javascript:

var willAlwaysFalse=false;
if(willAlwaysFalse)
{
}
else
{
}
Graviton
quelle
Als Antwort auf Charlies Frage fügte ich einen Kommentar hinzu, in dem erklärt wurde, warum ein solcher Ansatz nicht wünschenswert ist. Kurz gesagt, ich benötige eine Gruppe innerhalb eines regulären Ausdrucks, die immer verwendet wird. In einigen Fällen muss die Gruppe jedoch so erstellt werden, dass sie niemals übereinstimmt.
Peter Hansen
-2

Eine tragbare Lösung, die nicht von der Regexp-Implementierung abhängt, besteht darin, nur eine konstante Zeichenfolge zu verwenden, von der Sie sicher sind, dass sie niemals in den Protokollnachrichten angezeigt wird. Erstellen Sie beispielsweise eine Zeichenfolge, die auf Folgendem basiert:

cat /dev/urandom | hexdump | head -20
0000000 5d5d 3607 40d8 d7ab ce72 aae1 4eb3 ae47
0000010 c5e2 b9e8 910d a2d9 2eb3 fdff 6301 c85f
0000020 35d4 c282 e439 33d8 1c73 ca78 1e4d a569
0000030 8aca eb3c cbe4 aff7 d079 ca38 8831 15a5
0000040 818b 323f 0b02 caec f17f 387b 3995 88da
0000050 7b02 c80b 2d42 8087 9758 f56f b71f 0053
0000060 1501 35c9 0965 2c6e 03fe 7c6d f0ca e547
0000070 aba0 d5b6 c1d9 9bb2 fcd1 5ec7 ee9d 9963
0000080 6f0a 2c91 39c2 3587 c060 faa7 4ea4 1efd
0000090 6738 1a4c 3037 ed28 f62f 20fa 3d57 3cc0
00000a0 34f0 4bc2 3067 a1f7 9a87 086b 2876 1072
00000b0 d9e1 6b8f 5432 a60e f0f5 00b5 d9ef ed6f
00000c0 4a85 70ee 5ec4 a378 7786 927f f126 2ec2
00000d0 18c5 46fe b167 1ae6 c87c 1497 48c9 3c09
00000e0 8d09 e945 13ce 7da2 08af 1a96 c24c c022
00000f0 b051 98b3 2bf5 4d7d 5ec4 e016 a50d 355b
0000100 0e89 d9dd b153 9f0e 9a42 a51f 2d46 2435
0000110 ef35 17c2 d2aa 3cc7 e2c3 e711 d229 f108
0000120 324e 5d6a 650a d151 bc55 963f 41d3 66ee
0000130 1d8c 1fb1 1137 29b2 abf7 3af7 51fe 3cf4

Sicher, dies ist keine intellektuelle Herausforderung, sondern eher eine Klebebandprogrammierung .

hlovdal
quelle
-6
new Regex(Guid.NewGuid().ToString())

Erstellt ein Muster, das nur alphanumerische Zeichen und ' -' enthält (keines davon sind Regex-Sonderzeichen), aber es ist statistisch unmöglich, dass dieselbe Zeichenfolge irgendwo zuvor angezeigt wurde (da dies der springende Punkt einer GUID ist.)

finnw
quelle
2
"Statistisch unmöglich"? Huh? Abhängig davon, wie die GUID berechnet wird, ist es möglich und oft recht einfach, die nächsten GUIDs vorherzusagen (da sie von der Maschine abhängen, die sie berechnet, und von der Zeit). Sie meinen "unwahrscheinlich", "mit sehr geringer Wahrscheinlichkeit", aber Sie können nicht "unmöglich" sagen, selbst für perfekt zufällige Zeichenfolgen. Ihr Regex wird mit einer unendlichen Anzahl von Zeichenfolgen übereinstimmen - diese Frage sucht nach einer, die mit nichts übereinstimmt. Je.
Ferdinand Beyer