Regex, któremu nigdy nic nie dorówna


133

To może brzmieć jak głupie pytanie, ale odbyłem długą rozmowę z niektórymi z moich kolegów programistów i brzmiało to jak fajna rzecz do wymyślenia.

Więc; co myślisz - jak wygląda regex, któremu nigdy nie pasuje żaden ciąg!

Edycja : Dlaczego tego chcę? Po pierwsze dlatego, że myślę o takim wyrażeniu, wydaje mi się interesujące, a po drugie, ponieważ potrzebuję go do scenariusza.

W tym skrypcie definiuję słownik jako Dictionary<string, Regex>. Zawiera, jak widzisz, ciąg i wyrażenie.

Na podstawie tego słownika tworzę metody, które używają tego słownika jako jedynego odniesienia do tego, jak powinny wykonywać swoją pracę, jedna z nich dopasowuje wyrażenia regularne do przeanalizowanego pliku dziennika.

Jeśli wyrażenie zostanie dopasowane, do innego Dictionary<string, long>zostanie dodana wartość zwracana przez wyrażenie. Tak więc, aby złapać wszelkie komunikaty dziennika, które nie są zgodne z wyrażeniem w słowniku, utworzyłem nową grupę o nazwie „nieznane”.

Do tej grupy dodawane jest wszystko, co nie pasuje do niczego innego. Aby jednak „nieznane” wyrażenie nie pasowało (przez przypadek) do komunikatu dziennika, musiałem utworzyć wyrażenie, które z pewnością nigdy nie jest dopasowane, bez względu na to, jaki ciąg je podam.

Tak więc masz mój powód, dla którego to „nie jest prawdziwe pytanie” ...


1
Zauważ, że bardzo trudno jest udowodnić coś negatywnego.
Lasse V. Karlsen

5
Ciekawy. Gdzie użyłbyś takiego wyrażenia regularnego?
Charlie Salts

1
Zaznaczę, że wiele z powyższych komentarzy i odpowiedzi na to pytanie pochodziło pierwotnie ze stackoverflow.com/questions/1845078/ ..., które zadałem. Marc Gravell połączył je, co moim zdaniem sprawia, że ​​wiele z tych odpowiedzi jest dość dziwacznych bez dokładnego oryginalnego kontekstu, do tego stopnia, że ​​niektóre komentarze wydają się nie mieć sensu. (Prawdopodobnie również kradnie potencjalne przyszłe punkty rep.) Sugerowałbym, że pytania z tak szczegółowym tłem nigdy nie mogą być „dokładnymi duplikatami”. Cokolwiek ...
Peter Hansen

2
To pytanie zostało dodane do często zadawanych pytań dotyczących wyrażeń regularnych przepełnienia stosu w sekcji „Zaawansowane wyrażenie regularne ”.
aliteralmind

3
„Zauważ, że bardzo trudno jest udowodnić coś negatywnego” - jest to powszechnie uważane, ale całkowicie i oczywiście fałszywe ... tak jak wiemy przynajmniej odkąd Euclid udowodnił, że nie ma największej liczby pierwszej. A każdy dowód P jest dowodem zaprzeczenia (nie P). Prawdą jest, że trudno jest udowodnić empiryczną uniwersalność, pozytywną lub negatywną, np. „Wszystkie kruki są czarne” lub „żaden kruk nie jest biały”. Algorytmy mają charakter analityczny, a nie empiryczny, więc jest to szczególnie złe zastosowanie fałszywej reguły. np. dowód, że wzorzec „a” nie pasuje do żadnego ciągu zaczynającego się od „b”, nie jest „bardzo trudny”.
Jim Balter,

Odpowiedzi:


69

W rzeczywistości jest to dość proste, chociaż zależy to od implementacji / flag *:

$a

Dopasuje znak apo końcu ciągu. Powodzenia.

OSTRZEŻENIE:
To wyrażenie jest drogie - przeskanuje całą linię, znajdzie kotwicę końca linii, a dopiero potem nie znajdzie ai zwróci negatywne dopasowanie. (Więcej szczegółów w komentarzu poniżej).


* Początkowo nie zastanawiałem się zbytnio nad wyrażeniem regularnym w trybie wielowierszowym, gdzie $dopasowuje również koniec wiersza. W rzeczywistości pasowałby do pustego ciągu tuż przed nową linią , więc zwykły znak, taki jak, anigdy nie może pojawić się po $.


50
To wyrażenie jest drogie - przeskanuje całą linię, znajdzie kotwicę końca linii, a dopiero potem nie znajdzie „a” i zwróci negatywne dopasowanie. Widzę, że przeskanowanie pliku linii o wielkości ~ 275 kB zajmuje ~ 480 ms. Odwrotna „a ^” zajmuje mniej więcej tyle samo czasu, nawet jeśli wydaje się bardziej wydajna. Z drugiej strony, ujemne lookahead nie musi niczego skanować: „(?! X) x” (cokolwiek, po którym nie następuje x, po którym następuje x, tj. Nic) zajmuje około 30 ms, czyli mniej niż 7% czasu. (Mierzone czasem gnu i egrep.)
arantius

1
W Perlu będzie to pasowało do bieżącej wartości $a. Jego odpowiednik w Perlu $(?:a)jest również bardzo wolny perl -Mre=debug -e'$_=a x 50; /$(?:a)/'.
Brad Gilbert,

@arantius, proszę zobaczyć moją odpowiedź dotyczącą czasu , ponieważ znalazłem dokładne przeciwieństwo mierzone za pomocą timeiti python3.
nivk

Nie jest szokujące, że sześć lat i główna wersja Pythona może zmienić sytuację.
arantius

1
W składni POSIX BRE $abędzie pasował do tekstu literału $a, ponieważ $jest nieprawidłowy jako kotwica w tym wzorcu.
phils

77

Dźwignia negative lookahead:

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

ta RE jest wewnętrzną sprzecznością i dlatego nigdy do niczego nie będzie pasować.

UWAGA:
W Pythonie re.match () niejawnie dodaje zakotwiczenie początku łańcucha ( \A) na początku wyrażenia regularnego. Ta kotwica jest ważna dla wydajności: bez niej cały ciąg zostanie przeskanowany. Ci, którzy nie używają Pythona, będą chcieli jawnie dodać kotwicę:

\A(?!x)x

@Chris, tak - również (?=x)(?!x)i tak dalej (konkatenacje sprzecznych lookaheads i to samo dla lookbehinds), a wiele z nich działa również dla dowolnych wartości x(lookbehinds potrzebują xs, które pasują do ciągów o stałej długości).
Alex Martelli

1
Wydaje się, że działa dobrze. Ale co zamiast tego po prostu (?!)? Ponieważ () zawsze będzie pasować, czy (?!) Nie będzie gwarantowane, że nie będzie pasować?
Peter Hansen

2
@Peter, tak, jeśli Python akceptuje tę składnię (i wydaje się, że tak jest w ostatnich wersjach), byłoby to również sprzeczne. Inny pomysł (nie tak elegancki, ale im więcej pomysłów, tym bardziej prawdopodobne jest, że znajdziesz jeden działający we wszystkich interesujących Cię silnikach RE): r'a\bc'szukanie granicy słowa bezpośrednio otoczonej literami po obu stronach (wariant: znaki niesłowne na obie strony).
Alex Martelli

1
Co ciekawe, mój oryginał z prostym literałem, o którym „wiem”, nie pojawi się w moich danych wejściowych, okazuje się najszybszy w Pythonie. Z ciągiem wejściowym o wielkości 5 MB i używając go w operacji sub (), (?! X) x trwa o 21% dłużej, (?! ()) Jest o 16%, a ($ ^) o 6% dłużej. W niektórych przypadkach może mieć znaczenie, ale nie w moim.
Peter Hansen

2
To może być dość powolne perl -Mre=debug -e'$_=x x 8; /(?!x)x/'. Możesz to przyspieszyć, zakotwiczając go na początku \A(?!x)xlub na końcu (?!x)x\z. perl -Mre=debug -e'$_=x x 8; /(?!x)x\z/; /\A(?!x)x/'
Brad Gilbert,

44

Jeden, którego brakowało:

^\b$

Nie może pasować, ponieważ pusty ciąg nie zawiera granicy słowa. Przetestowano w Pythonie 2.5.


8
To najlepsza odpowiedź. Nie używa lookaheads, nie psuje się pod niektórymi implementacjami regex, nie używa określonego znaku (np. 'A') i kończy się niepowodzeniem w maksymalnie 3 krokach przetwarzania (zgodnie z regex101.com) bez skanowania całości ciąg wejściowy. Jest to również łatwe do zrozumienia na pierwszy rzut oka.
CubicleSoft

1
To faktycznie zawodzi w Emacsie w pewnych warunkach (jeśli na początku lub na końcu bufora jest pusta linia), jednak \`\b\'działa, co zastępuje składnię Emacsa dla „początku / końca tekstu” (w przeciwieństwie do „początku / końca linii").
phils

35

rozejrzeć się:

(?=a)b

Dla początkujących wyrażeń regularnych: Pozytywne spojrzenie w przyszłość (?=a)zapewnia, że ​​następny znak jest a, ale nie zmienia lokalizacji wyszukiwania (lub zawiera „a” w dopasowanym ciągu). Teraz, gdy potwierdzono, że jest następny znak a, pozostała część wyrażenia regularnego ( b) pasuje tylko wtedy, gdy następny znak to b. Tak więc to wyrażenie regularne pasuje tylko wtedy, gdy znak jest jednocześnie ai bjednocześnie.


31

a\bc, gdzie \bjest wyrażeniem o zerowej szerokości pasującym do granicy słowa.

Nie może pojawić się w środku słowa, do którego go zmuszamy.


1
Jeśli twój przypadek użycia pozwala ci zakotwiczyć wzorzec na początku łańcucha, to ulepszenie uniemożliwi silnikowi regexp wyszukiwanie i testowanie każdego wystąpienia aw tekście.
phils

20

$.

.^

$.^

(?!)


1
Uroczy! Moja podświadomość odciągnęła mnie od idei takich jak pierwsze trzy, ponieważ są „nielegalne”… koncepcyjnie, ale oczywiście nie do wyrażenia regularnego. Nie rozpoznaję tego (!) ... będę musiał to sprawdzić.
Peter Hansen

1
Okej, podoba mi się (?!) Odpowiedź ... w rzeczywistości to, co zasugerował Alex. Zauważ, że na stackoverflow.com/questions/1723182 (wskazanym przez Amarghosha powyżej) ktoś twierdzi, że „niektóre odmiany” wyrażenia regularnego uznałby to za błąd składni. Jednak Python lubi to dobrze. Zauważ, że wszystkie inne sugestie zawiodłyby w trybach re.DOTALL | re.MULTILINE w Pythonie.
Peter Hansen

1
Czy to zostało przetestowane? Zakładałbym, że ^ma specjalne znaczenie tylko jako pierwszy znak $wyrażenia regularnego i ma specjalne znaczenie tylko na końcu wyrażenia regularnego, chyba że wyrażenie regularne jest wyrażeniem wielowierszowym.
PP.

Właściwie w Perlu /$./oznacza coś zupełnie innego. Oznacza to dopasowanie aktualnej wartości $.(numer linii wejściowej) . Nawet /$(.)/mógłby coś dopasować, gdybyś napisał use re '/s';wcześniej. ( perl -E'say "\n" =~ /$(.)/s || 0')
Brad Gilbert,

W składni POSIX BRE, ^i $są wyjątkowe tylko na początku i na końcu (odpowiednio) wzoru, więc żaden z $.lub .^czy $.^będzie działać. (?!)jest, jak sądzę, funkcją Perl / PCRE.
phils

13

Maksymalne dopasowanie

a++a

Co najmniej jeden, apo którym następuje dowolna liczba aznaków, bez cofania. Następnie spróbuj dopasować jeszcze jeden a.

lub niezależne wyrażenie podrzędne

Jest to równoważne wstawieniu a+niezależnego wyrażenia podrzędnego, a po nim innego a.

(?>a+)a

10

Perl 5.10 obsługuje specjalne słowa kontrolne zwane „czasownikami”, które są zawarte w (*...)sekwencji. (Porównaj ze (?...)specjalną sekwencją.) Wśród nich znajduje się (*FAIL)czasownik, który natychmiast powraca z wyrażenia regularnego.

Zauważ, że czasowniki są również zaimplementowane w PCRE wkrótce potem, więc możesz ich używać w PHP lub innych językach, używając również biblioteki PCRE. (Jednak nie możesz tego zrobić w Pythonie ani Rubim. Używają one własnego silnika).


Dokumentacja na ten temat na perldoc.perl.org/perlre.html#%28%2AFAIL%29-%28%2AF%29 mówi „Ten wzorzec nie pasuje do niczego i zawsze zawodzi. Jest równoważny z (?!), Ale łatwiejszy do czytaj. W rzeczywistości (?!) jest wewnętrznie optymalizowany do (* FAIL). " Ciekawe, bo (?!) To moja ulubiona jak dotąd „czysta” odpowiedź (mimo że nie działa w Javascript). Dzięki.
Peter Hansen,

10
\B\b

\bdopasowuje granice słów - pozycja między literą a nie literą (lub granicą ciągu).
\Bjest jego uzupełnieniem - dopasowuje pozycję między dwiema literami lub między nieliterami.

Razem nie mogą dopasować się do żadnej pozycji.

Zobacz też:


Wydaje się, że jest to doskonałe rozwiązanie, pod warunkiem, że jest zakotwiczone w konkretnym punkcie (początek tekstu wydaje się sensowny). Jeśli tego nie zrobisz, jest to okropne rozwiązanie, ponieważ każda granica nie będąca słowem w tekście zostanie przetestowana, aby sprawdzić, czy następuje po niej granica słowa! Więc rozsądna wersja byłaby podobna ^\B\b. W językach, w których „początek tekstu” i „początek wiersza” mają różną składnię, chciałbyś użyć składni „początku tekstu”, w przeciwnym razie będziesz testować każdy wiersz. (np. w Emacsie byłoby to \`\B\blub "\\`\\B\\b".)
phils

To powiedziawszy, zauważyłem teraz, że podanym celem tego pytania jest uzyskanie wyrażenia regularnego do użycia w grupie, w którym ^to przypadku jest problematyczne w niektórych składni wyrażeń regularnych (np. POSIX BRE), gdzie ^jest kotwicą tylko wtedy, gdy jest to pierwszy znak wzorca, a poza tym dopasowuje literalny ^znak.
phils

@phils - myślę, że się nad tym zastanawiasz :)- to niepraktyczne pytanie, którego celem było znalezienie interesującej odpowiedzi, a nie skutecznej. To powiedziawszy, wzorzec może zostać odrzucony w czasie liniowym (z rozmiarem ciągu docelowego), więc nie jest zły dla wyrażenia regularnego - większość wzorca jest tutaj taka sama, a nawet ^może być liniowa, jeśli nie jest zoptymalizowana.
Kobi

Re: optymalizacje, jestem skłonny zignorować silnik regexp, który ma nadzieję znaleźć "początek tekstu" w jakimkolwiek innym miejscu :)
phils

Poza tym nie jest to takie niepraktyczne pytania i odpowiedzi - jedynym powodem, dla którego tu trafiłem, było sprawdzenie, czy ktoś mógłby zasugerować bardziej wydajne rozwiązanie dla mojego własnego w praktycznym celu skonfigurowania określonej zmiennej Emacsa, która wymagałaby wartości regexp, ale której ja chciał skutecznie wyłączyć.
phils

8

To wydaje się działać:

$.

2
Jest to podobne do przykładu Ferdinanda Beyera.
Gumbo

9
I będzie pasować w trybie dot-match-newlines.
Tim Pietzcker

W Perlu będzie to faktycznie zgodne z bieżącym numerem linii wejściowej $.. W takim przypadku musisz uciec się do$(.) lub bardziej równoważnie $(?:.).
Brad Gilbert,

W składni POSIX BRE, $.dopasuje literał, $po którym następuje dowolny znak, ponieważ $jest nieprawidłowy jako kotwica w tym wzorcu.
phils

8

A $^może (?!)


3
Podział wiersza zostanie dopasowany przez to wyrażenie w trybie, w którym ^dopasowuje początek i $koniec wiersza.
Gumbo

4
Może miał na myśli (?!)- negatywne spojrzenie w przód dla pustego ciągu. Ale niektóre odmiany wyrażeń regularnych potraktują to również jako błąd składni.
Alan Moore

1
Pusty ciąg pasuje do pierwszego, przynajmniej w JavaScript.
Roland Pihlakas

W składni POSIX BRE, $^będzie pasował do tych literałów, ponieważ znaki są nieprawidłowe jako kotwice (tj. Sam powód, dla którego użyłeś wzorca, powoduje, że nie robi tego, co chciałeś).
phils

5

Najszybciej będzie:

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

„a” może być dowolnym znakiem innym niż specjalny („x”, „y”). Implementacja Knio może być nieco czystsza, ale ta będzie szybsza dla wszystkich ciągów znaków, nie rozpoczynających się od wybranego znaku zamiast „a”, ponieważ w takich przypadkach nie będzie pasować po pierwszym znaku, a nie po drugim.


Rzeczywiście, (. ^) Byłoby około 10% wolniejsze niż (\ x00 ^) w moim przypadku.
Peter Hansen

1
Akceptuję to, ponieważ użycie dowolnej wartości innej niż \ n jako znaku gwarantuje, że nigdy nie będzie pasować, i uważam ją za nieco bardziej czytelną (biorąc pod uwagę, że stosunkowo niewiele osób jest ekspertami od wyrażeń regularnych) niż opcja (?! X) x , chociaż głosowałem również za tym. W moim przypadku dla każdej opcji potrzebowałbym komentarza, aby to wyjaśnić, więc myślę, że po prostu dostosuję moją pierwotną próbę do '\ x00NEVERMATCHES ^'. Mam gwarancję, że ta odpowiedź nie pasuje, dzięki mojej oryginalnej samodokumentacji. Dziękuję wszystkim za odpowiedzi!
Peter Hansen

3
Czy to faktycznie działa, a jeśli tak, to kto zdecydował się zerwać z Uniksem? W uniksowych wyrażeniach regularnych ^jest wyjątkowy tylko jako pierwszy znak i podobnie z $. W przypadku dowolnego narzędzia uniksowego to wyrażenie regularne dopasuje wszystko, co zawiera literał a^.
JaakkoK

Heh, to dobry atak. Nigdy nie testowałem tego dosłownego ciągu.
Adam Nelson

Och, jeśli to zepsuje wyrażenia regularne Unix, pokochasz >^.
CubicleSoft

4

Python tego nie zaakceptuje, ale Perl:

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

To wyrażenie regularne powinno (teoretycznie) próbować dopasować nieskończoną (parzystą) liczbę ws, ponieważ pierwsza grupa (grupy ()) powraca do siebie. Wydaje się, że Perl nie wydaje żadnych ostrzeżeń, nawet poniżej use strict; use warnings;, więc zakładam, że jest co najmniej poprawny, a moje (minimalne) testy nie pasują do niczego, więc przesyłam je do Twojej krytyki.


1
Teoria jest zawsze fajna, ale w praktyce myślę, że martwiłbym się wyrażeniami regularnymi, których opisy zawierały słowo „nieskończony”!
Peter Hansen

perl -Mre=debug -e'"www wwww wwwww wwwwww" =~ /(w\1w)/'
Brad Gilbert,

@BradGilbert - Uruchomienie tego tutaj (5.10, trochę nieaktualne) daje "regex failed", zgodnie z żądaniem OP. Czy pasuje do twojego systemu?
Chris Lutz,

4

[^\d\D]lub (?=a)blub a$aluba^a


Dzięki. Zauważ, że (?! X) x była pierwszą podaną odpowiedzią, wymienioną powyżej.
Peter Hansen,

Tak, wydawało się, że przeskanowałem pozostałych odpowiadających zbyt szybko.
Bart Kiers,

4

To nie zadziała w Pythonie i wielu innych językach, ale w wyrażeniu regularnym JavaScript []jest poprawną klasą znaków, której nie można dopasować. Tak więc, bez względu na dane wejściowe, następujące działania powinny natychmiast zakończyć się niepowodzeniem:

var noMatch = /^[]/;

Podoba mi się bardziej niż /$a/dlatego, że dla mnie jasno przekazuje swój zamiar. A jeśli chodzi o to, kiedy kiedykolwiek będziesz go potrzebować, potrzebowałem go, ponieważ potrzebowałem rozwiązania zastępczego dla dynamicznie kompilowanego wzorca na podstawie danych wejściowych użytkownika. Gdy wzorzec jest nieprawidłowy, muszę go zastąpić wzorcem, który do niczego nie pasuje. W uproszczeniu wygląda to tak:

try {
    var matchPattern = new RegExp(someUserInput);
}
catch (e) {
    matchPattern = noMatch;
}

4

Wszystkie przykłady dotyczące dopasowania granic są zgodne z tą samą regułą. Przepis:

  1. Wybierz dowolne dopasowanie granic: ^, $, \ b, \ A, \ Z, \ z

  2. Zrób coś przeciwnego do tego, do czego są przeznaczone

Przykłady:

^ i \ A są przeznaczone na początek, więc nie używaj ich na początku

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

\ b dopasowuje granicę słowa, więc używaj jej pomiędzy

\b --> .\b.

$, \ Z i \ z są przeznaczone na koniec, więc nie używaj ich na końcu

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

Inne obejmują użycie patrzenia w przód i w tył, które również działają z tą samą analogią: jeśli dajesz pozytywne lub negatywne spojrzenie w przód, a następnie coś przeciwnego

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

Jeśli dajesz pozytywne lub negatywne spojrzenie za siebie, podążając za czymś przeciwnym

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

Mogłoby być więcej takich wzorców i więcej takich analogii.


3

Tyle dobrych odpowiedzi!

Podobnie jak w przypadku odpowiedzi @ nivk, chciałbym podzielić się porównaniami wydajności Perla dla różnych wariantów niepasujących wyrażeń regularnych.

  1. Dane wejściowe: pseudolosowe ciągi ascii (25 000 różnych linii, długość 8-16):

Regex prędkość:

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. Wpisz: / usr / share / dict / words (100 000 angielskich słów).

Regex prędkość:

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 na Intel i5-3320M, jądro Linux 4.13, Perl 5.26)


Oto porównanie JavaScript niektórych metod omawianych tutaj: jsperf.com/regex-that-never-matches
thdoan,

2

Wierzę w to

\Z RE FAILS! \A

obejmuje nawet przypadki, w których wyrażenie regularne zawiera flagi takie jak MULTILINE, DOTALL itp.

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

Uważam (ale nie testowałem tego), że niezależnie od długości (> 0) łańcucha między \Za \A, czas do awarii powinien być stały.


2
(*FAIL)

lub

(*F)

Z PCRE i PERL możesz użyć tego czasownika sterującego cofaniem, który wymusza natychmiastowe niepowodzenie wzorca.


2

Po obejrzeniu niektórych z tych wspaniałych odpowiedzi, komentarz @ arantius (dotyczący synchronizacji w $xporównaniu x^z(?!x)x ) na temat obecnie zaakceptowanej odpowiedzi sprawił, że chciałem niektóre z dotychczas podanych rozwiązań.

Używając standardu linii @ arantius 275k, przeprowadziłem następujące testy w Pythonie (v3.5.2, IPython 6.2.1).

TL; DR: 'x^'i 'x\by'są najszybsze o współczynnik co najmniej ~ 16 i w przeciwieństwie do ustalenia @ arantius, (?!x)xbyły jednymi z najwolniejszych (~ 37 razy wolniej). Zatem kwestia szybkości jest z pewnością zależna od implementacji. Jeśli prędkość jest dla Ciebie ważna, przetestuj to samodzielnie w zamierzonym systemie przed zatwierdzeniem.

AKTUALIZACJA: Najwyraźniej istnieje duża rozbieżność między synchronizacją 'x^'a 'a^'. Zobacz to pytanie, aby uzyskać więcej informacji, oraz poprzednią edycję dotyczącą wolniejszych czasów z azamiast 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)

Gdy po raz pierwszy to uruchomiłem, zapomniałem rprzejrzeć 3 ostatnie wyrażenia, więc '\b'został zinterpretowany jako '\x08'znak backspace. Jednak ku mojemu zdziwieniu 'a\x08c'był szybszy niż poprzedni najszybszy wynik! Szczerze mówiąc, nadal będzie pasował do tego tekstu, ale pomyślałem, że nadal warto go zauważyć, ponieważ nie jestem pewien, dlaczego jest szybszy.

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

Mój plik testowy został utworzony przy użyciu formuły „... Czytelna zawartość i brak zduplikowanych wierszy” (w systemie Ubuntu 16.04):

$ 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

\B\bjest okropnie wadliwa pod względem wydajności (jak każdy wzór, który nie jest zakotwiczony w pozycji, ale ten wzór jest szczególnie zły). ^\B\bZamiast tego wypróbuj testy porównawcze .
phils

2

Puste wyrażenie regularne

Najlepszym wyrażeniem regularnym, które nigdy nie pasuje do niczego, jest puste wyrażenie regularne. Ale nie jestem pewien, czy każdy silnik regex to zaakceptuje.

Niemożliwe wyrażenie regularne

Innym rozwiązaniem jest utworzenie niemożliwego wyrażenia regularnego. Odkryłem, że $-^obliczenie zajmuje tylko dwa kroki, niezależnie od rozmiaru tekstu ( https://regex101.com/r/yjcs1Z/1 ).

Na przykład:

  • $^i $.wykonaj 36 kroków, aby obliczyć -> O (1)
  • \b\B wykonuje 1507 kroków na mojej próbce i zwiększa się wraz z liczbą znaków w twoim ciągu -> O (n)

Bardziej popularny wątek dotyczący tego pytania:


1

Może to?

/$.+^/

W Pythonie to podejście działa tylko wtedy, gdy kontrolujesz flagi : re.compile('$.+^', re.MULTILINE|re.DOTALL).search('a\nb\nc\n')zwraca obiekt dopasowania odpowiadający bi c (oraz wszystkim sąsiednim i pomiędzy znakami nowej linii). Podejście z negatywnym wyprzedzeniem, które zalecam, działa (tj. Niczego nie dopasowuje) dla dowolnej kombinacji flag, z którą można go skompilować.
Alex Martelli

Mój błąd - pomieszałem $i ^.
Chris Lutz

1
Może to być próba wyszukania końca ciągu przed jego początkiem, ale odkryłem, że $ nie oznacza `` końca ciągu '', chyba że jest to ostatni znak wyrażenia regularnego i spodziewam się podobnego zachowania do ^, więc może to pasować do podciągu zaczynającego się od literału $, a kończącego na dosłownym ^
pavium

@pavium, z pewnością nie zachowuje się w ten sposób w Pythonie lub Javascript. O ile nie zmienisz ich znaczenia za pomocą \ lub nie włączysz ich do zestawu znaków za pomocą [], znaki specjalne, takie jak $ i ^, nie powinny być traktowane jako literały. W jakim języku to zauważyłeś?
Peter Hansen

Przynajmniej w Perlu powinno to być napisane /\z.+\A/(patrz perldoc perlre ). Zapobiega use re '/ms'to wpływaniu na to trybu wieloliniowego i jednowierszowego ( ).
Brad Gilbert,

0
'[^0-9a-zA-Z...]*'

i zamień ... na wszystkie drukowalne symbole;). To dotyczy pliku tekstowego.


Myślę, że musi być na to krótsza droga, ale to też była moja pierwsza myśl ^^
FP

4
Spowoduje to dopasowanie pustego ciągu. Aby złapać każdy możliwy znak, użyj [^\x00-\xFF]+(dla implementacji opartych na bajtach).
Ferdinand Beyer

6
Lepszy byłby wyraz [^\s\S]. Ale jak już powiedział Ferdinand Beyer, pasowałoby do pustego ciągu.
Gumbo

3
Wyrażenie regularne Drakosha może dopasować pusty ciąg z powodu *; zostaw to wyłączone lub zamień na +i musi pasować do co najmniej jednego znaku. Jeśli klasa wyklucza wszystkie możliwe znaki, nie może do niczego pasować.
Alan Moore

0

A co powiesz na to, że zamiast wyrażenia regularnego użyj po prostu zawsze fałszywej instrukcji if? W javascript:

var willAlwaysFalse=false;
if(willAlwaysFalse)
{
}
else
{
}

Dodałem komentarz w odpowiedzi na pytanie Charliego, wyjaśniając, dlaczego takie podejście nie jest pożądane. Krótko mówiąc, potrzebuję grupy wewnątrz wyrażenia regularnego, która będzie zawsze używana, ale w niektórych przypadkach grupa musi być zbudowana tak, aby nigdy nie pasowała.
Peter Hansen

-2

Przenośnym rozwiązaniem, które nie będzie zależeć od implementacji wyrażenia regularnego, jest po prostu użycie stałego ciągu, który z pewnością nigdy nie pojawi się w komunikatach dziennika. Na przykład utwórz ciąg w oparciu o następujące elementy:

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

Jasne, nie jest to intelektualne wyzwanie, ale bardziej przypomina programowanie taśmą klejącą .


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

Tworzy wzorzec zawierający tylko -znaki alfanumeryczne i „ ” (z których żaden nie jest znakami specjalnymi wyrażenia regularnego), ale statystycznie niemożliwe jest, aby ten sam ciąg pojawił się gdziekolwiek wcześniej (ponieważ o to chodzi w identyfikatorze GUID).


2
„Statystycznie niemożliwe”? Co? W zależności od tego, jak obliczany jest identyfikator GUID, możliwe jest i często dość proste przewidzenie kolejnych identyfikatorów GUID (ponieważ zależą one od komputera, który je oblicza i od czasu). Masz na myśli „mało prawdopodobne”, „z bardzo małym prawdopodobieństwem”, ale nie możesz powiedzieć „niemożliwe” nawet dla całkowicie przypadkowych łańcuchów. Twój Regex będzie pasował do nieskończonej liczby ciągów - to pytanie szuka takiego, który nie będzie pasował do niczego. Zawsze.
Ferdinand Beyer
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.