Regex, któremu nigdy nic nie dorówna

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” ...

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 $.

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

Jeden, którego brakowało:

^\b$

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

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.

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.

$.

.^

$.^

(?!)

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

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).

\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ż:

• Granice słów
• Ten wzór nie pasuje do kilku pozycji
• Inspiracja

To wydaje się działać:

$.

A $^może (?!)? 

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.

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.

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

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;
}

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.

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

2. 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)

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.

(*FAIL)

lub

(*F)

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

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

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:

• Wyrażenie regularne na * nie * pasuje do żadnych znaków

Może to?

/$.+^/

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

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

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
{
}

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ą .

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).