Un Regex che non sarà mai eguagliato da nulla

Potrebbe sembrare una domanda stupida, ma ho parlato a lungo con alcuni dei miei colleghi sviluppatori e mi sembrava una cosa divertente da pensare.

Così; cosa ne pensi? Che aspetto ha un Regex, che non sarà mai eguagliato da nessuna corda, mai!

Modifica : Perché voglio questo? Bene, in primo luogo perché trovo interessante pensare a una tale espressione e in secondo luogo perché ne ho bisogno per una sceneggiatura.

In quello script definisco un dizionario come Dictionary . Questo contiene, come vedi, una stringa e un’espressione.

Sulla base di quel dizionario creo metodi che usano tutti questo dizionario come riferimento solo su come dovrebbero fare il loro lavoro, uno di essi corrisponde alle espressioni regolari contro un file di log analizzato.

Se un’espressione è abbinata, un altro Dictionary viene aggiunto un valore che viene restituito dall’espressione. Quindi, per catturare tutti i messaggi di log che non sono corretti da un’espressione nel dizionario, ho creato un nuovo gruppo chiamato “sconosciuto”.

A questo gruppo viene aggiunto tutto ciò che non corrisponde ad altro. Ma per evitare che l’espressione “sconosciuta” mismatch (accidentalmente) un messaggio di log, dovevo creare un’espressione che sicuramente non ha mai eguagliato, non importa quale stringa gli dò.

Quindi, ecco la mia ragione per questa “non una vera domanda” …

Questo è in realtà abbastanza semplice, anche se dipende dall’implementazione / flag *:

 $a 

Corrisponde a un carattere a dopo la fine della stringa. In bocca al lupo.

AVVERTIMENTO:
Questa espressione è costosa: analizzerà l’intera linea, troverà l’ancora di fine linea e solo allora non troverà la a e restituirà una corrispondenza negativa. (Vedi il commento sotto per maggiori dettagli.)


* Inizialmente non mi ero preoccupato molto della regexp in modalità multilinea, dove $ corrisponde anche alla fine di una riga. In effetti, corrisponderebbe alla stringa vuota proprio prima della nuova riga , quindi un carattere normale come a non può mai apparire dopo $ .

Sfrutta il negative lookahead :

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

questa RE è una contraddizione in termini e quindi non potrà mai eguagliare nulla.

NOTA:
In Python, re.match () aggiunge implicitamente un anchor di inizio stringa ( \A ) all’inizio dell’espressione regolare. Questa ancora è importante per le prestazioni: senza di essa verrà eseguita la scansione dell’intera stringa. Coloro che non usano Python vorranno aggiungere l’ancora esplicitamente:

 \A(?!x)x 

guardarsi intorno:

(?=a)b

Per le principianti regex: Lo sguardo positivo avanti (?=a) assicura che il carattere successivo sia a , ma non cambia la posizione di ricerca (o include ‘a’ nella stringa corrispondente). Ora che il prossimo carattere viene confermato come a , la parte rimanente della regex ( b ) corrisponde solo se il carattere successivo è b . Quindi, questa regex corrisponde solo se un personaggio è sia a che b allo stesso tempo.

a\bc , dove \b è un’espressione a larghezza zero che corrisponde al limite della parola.

Non può apparire nel mezzo di una parola, alla quale lo costringiamo.

Uno che è mancato:

 ^\b$ 

Non può corrispondere perché la stringa vuota non contiene un limite di parole. Testato in Python 2.5.

$.

.^

$.^

(?!)

Corrispondenza massima

 a++a 

Almeno una a seguita da qualsiasi numero di a , senza retrocedere. Quindi prova ad abbinare un altro a .

o sottoespressione indipendente

Questo equivale a mettere a+ in una sotto espressione indipendente, seguito da a altro a .

 (?>a+)a 

Perl 5.10 supporta parole di controllo speciali chiamate “verbi”, che è racchiusa nella sequenza (*...) . (Confronta con (?...) una sequenza speciale.) Tra questi, include (*FAIL) verbo che ritorna immediatamente dall’espressione regolare.

Nota che i verbi sono implementati anche in PCRE poco dopo, quindi puoi usarli in PHP o in altre lingue usando anche la libreria PCRE. (Non è ansible in Python o Ruby, tuttavia, usano il proprio motore.)

 \B\b 

\b corrisponde ai limiti delle parole – la posizione tra una lettera e una non lettera (o il limite della stringa).
\B è il suo complemento – corrisponde alla posizione tra due lettere o tra non lettere.

Insieme non possono corrispondere a nessuna posizione.

Guarda anche:

  • Confini di parole
  • Questo modello non corrisponde ad alcune posizioni
  • Ispirazione

Questo sembra funzionare:

 $. 

Che ne dici di $^ o forse (?!) ?

Python non lo accetterà, ma Perl:

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

Questa espressione regolare dovrebbe (teoricamente) provare ad abbinare un numero infinito (pari) di w s, perché il primo gruppo (i () s) ricorre a se stesso. Perl non sembra emettere alcun avvertimento, anche se sotto use strict; use warnings; use strict; use warnings; , quindi presumo che sia almeno valido, e il mio test (minimo) non corrisponde a nulla, quindi lo invio per la tua critica.

Il più veloce sarà:

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

‘a’ può essere qualsiasi carattere non speciale (‘x’, ‘y’). L’implementazione di Knio potrebbe essere un po ‘più pura, ma questa sarà più veloce per tutte le stringhe che non iniziano con qualsiasi carattere tu scelga invece di “a” perché non corrisponderà dopo il primo carattere piuttosto che dopo il secondo in questi casi.

[^\d\D] o (?=a)b o a$a o a^a

Questo non funzionerà con Python e molti altri linguaggi, ma in un’espressione regolare di Javascript, [] è una class di caratteri valida che non può essere abbinata. Quindi il seguente dovrebbe fallire immediatamente, indipendentemente dall’input:

 var noMatch = /^[]/; 

Mi piace meglio di /$a/ perché per me, comunica chiaramente il suo intento. E per quando ne avresti mai avuto bisogno, ne avevo bisogno perché avevo bisogno di un fallback per un pattern compilato dynamicmente in base all’input dell’utente. Quando il modello non è valido, ho bisogno di sostituirlo con un modello che non corrisponde a nulla. Semplificato, sembra questo:

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

credo che

 \Z RE FAILS! \A 

copre anche i casi in cui l’espressione regolare include bandiere come MULTILINE, DOTALL ecc.

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

Credo (ma non l’ho benchmark) che qualunque sia la lunghezza (> 0) della stringa tra \Z e \A , il time-to-failure dovrebbe essere costante.

Dopo aver visto alcune di queste grandi risposte, il commento di @ arantius (per quanto riguarda la temporizzazione di $x vs x^ vs (?!x)x ) sulla risposta attualmente accettata mi ha fatto desiderare di dedicare alcune delle soluzioni date finora.

Usando lo standard di linea 275k di @ arantius, ho eseguito i seguenti test in Python (v3.5.2, IPython 6.2.1).

TL; DR: 'x^' e 'x\by' sono i più veloci di un fattore di almeno ~ 16, e contrariamente al risultato di @ arantius, (?!x)x era tra i più lenti (~ 37 volte più lenti). Quindi la questione della velocità è certamente dipendente dall’implementazione. Provalo tu stesso sul tuo sistema previsto prima di impegnarti se la velocità è importante per te.

AGGIORNAMENTO: C’è apparentemente una grande discrepanza tra i tempi 'x^' e 'a^' . Si prega di vedere questa domanda per maggiori informazioni, e la modifica precedente per i tempi più lenti con a invece di 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) 

La prima volta che l’ho eseguito, mi sono dimenticato di eseguire le ultime 3 espressioni, quindi '\b' stato interpretato come '\x08' , il carattere backspace. Tuttavia, con mia sorpresa, 'a\x08c' stato più veloce del precedente risultato più veloce! Per essere onesti, continuerà a corrispondere a quel testo, ma ho pensato che fosse ancora degno di nota perché non sono sicuro del motivo per cui è più veloce.

 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 

Il mio file di test è stato creato utilizzando una formula per “… Contenuti leggibili e senza righe duplicate” (su 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 

Forse questo?

 /$.+^/ 
 (*FAIL) 

o

 (*F) 

Con PCRE e PERL puoi usare questo verbo di controllo del backtracking che forza immediatamente il pattern a fallire.

Così tante buone risposte!

Simile alla risposta di @nivk, mi piacerebbe condividere il confronto delle prestazioni per Perl per diverse varianti di regex senza corrispondenza.

  1. Input: stringhe ascii pseudo-casuali (25.000 righe diverse, lunghezza 8-16):

Velocità Regex:

 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. Input: / usr / share / dict / words (100.000 parole inglesi).

Velocità Regex:

 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 su Intel i5-3320M, kernel Linux 4.13, Perl 5.26)

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

e sostituire … con tutti i simboli stampabili;). Questo è per un file di testo.

Che dire invece di regex, basta usare un’istruzione if sempre falsa? In javascript:

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

Una soluzione portatile che non dipenderà dall’esecuzione regexp consiste nell’usare solo una stringa costante che si è certi non apparirà mai nei messaggi di registro. Ad esempio, crea una stringa basata su quanto segue:

 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 

Certo, questa non è una sfida intellettuale, ma più simile alla programmazione dei nastri conduttivi .

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

Crea un pattern contenente solo caratteri alfanumerici e ‘ - ‘ (nessuno dei quali è espressioni speciali speciali) ma è statisticamente imansible che la stessa stringa sia comparsa prima (perché questo è il punto intero di un GUID).