Una Regex que nunca será igualada por nada

Esto puede sonar como una pregunta estúpida, pero tuve una larga conversación con algunos de mis compañeros desarrolladores y me pareció algo divertido de lo que pensar.

Asi que; ¿Cuál es tu pensamiento? ¿Cómo es una Regex, que nunca será igualada por ninguna cadena, nunca!

Editar : ¿Por qué quiero esto? Bueno, en primer lugar porque me parece interesante pensar en una expresión así y, en segundo lugar, porque la necesito para un guión.

En ese script defino un diccionario como Dictionary . Esto contiene, como ve, una cadena y una expresión.

Basado en ese diccionario, creo métodos que usan este diccionario como referencia única sobre cómo deben hacer su trabajo, uno de ellos coincide con las expresiones regulares en un archivo de registro analizado.

Si se corresponde una expresión, a otro Dictionary se le agrega un valor que la expresión devuelve. Entonces, para capturar cualquier mensaje de registro que no coincida con una expresión en el diccionario, creé un nuevo grupo llamado “desconocido”.

Para este grupo, todo lo que no concuerda con nada se agrega. Pero para evitar que la expresión “desconocida” no coincida (por accidente) con un mensaje de registro, tuve que crear una expresión que ciertamente nunca coincide, sin importar la cadena que le dé.

Por lo tanto, ahí tienes mi razón para esta “no es una pregunta real” …

Esto es realmente bastante simple, aunque depende de la implementación / flags *:

 $a 

Coincidirá con un personaje a después del final de la cadena. Buena suerte.

ADVERTENCIA:
Esta expresión es costosa: explorará toda la línea, buscará el ancla de final de línea y solo entonces no encontrará la a y devolverá una coincidencia negativa. (Consulte el comentario a continuación para obtener más detalles).


* Originalmente no pensé demasiado en expresiones regulares de modo multilínea, donde $ también coincide con el final de una línea. De hecho, coincidiría con la cadena vacía justo antes de la nueva línea , por lo que un carácter ordinario como a nunca puede aparecer después de $ .

Aproveche negative lookahead :

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

este RE es una contradicción en los términos y, por lo tanto, nunca coincidirá con nada.

NOTA:
En Python, re.match () agrega implícitamente un ancla de inicio de cadena ( \A ) al comienzo de la expresión regular. Este anclaje es importante para el rendimiento: sin él, se explorará toda la cuerda. Aquellos que no usan Python querrán agregar el ancla explícitamente:

 \A(?!x)x 

mira alrededor:

(?=a)b

Para los novatos de expresiones regulares: la mirada positiva hacia delante (?=a) asegura que el siguiente carácter sea a , pero no cambia la ubicación de búsqueda (o incluye la ‘a’ en la cadena coincidente). Ahora que se confirma que el siguiente carácter es a, la parte restante de la expresión regular ( b ) solo coincide si el siguiente carácter es b . Por lo tanto, esta expresión regular solo coincide si un personaje es a y b al mismo tiempo.

a\bc , donde \b es una expresión de ancho cero que coincide con el límite de palabras.

No puede aparecer en medio de una palabra, que lo forzamos a hacerlo.

Uno que se perdió:

 ^\b$ 

No puede coincidir porque la cadena vacía no contiene un límite de palabras. Probado en Python 2.5.

$.

.^

$.^

(?!)

Coincidencia máxima

 a++a 

Al menos uno a seguido de cualquier cantidad de a , sin retroceder. Luego intenta emparejar uno más a .

o Subexpresión independiente

Esto es equivalente a poner a+ en una subexpresión independiente, seguido por otro a .

 (?>a+)a 

Perl 5.10 admite palabras de control especiales llamadas “verbos”, que se incluyen en la secuencia (*...) . (Compare con (?...) secuencia especial.) Entre ellos, incluye el verbo (*FAIL) que regresa inmediatamente de la expresión regular.

Tenga en cuenta que los verbos también se implementan en PCRE poco después, por lo que puede usarlos en PHP u otros idiomas usando la biblioteca PCRE también. (No se puede en Python o Ruby, sin embargo, usan su propio motor).

 \B\b 

\b coincide con los límites de las palabras: la posición entre una letra y una no letra (o el límite de la cadena).
\B es su complemento: coincide con la posición entre dos letras o entre las que no son letras.

Juntos no pueden coincidir con ninguna posición.

Ver también:

  • Límites de palabra
  • Este patrón no coincide con algunas posiciones
  • Inspiración

Esto parece funcionar:

 $. 

¿Qué tal $^ o tal vez (?!) ?

Python no lo aceptará, pero Perl hará lo siguiente:

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

Esta expresión regular debería (teóricamente) intentar hacer coincidir un número infinito (par) de w s, porque el primer grupo (el () s) recurre a sí mismo. Perl no parece emitir ninguna advertencia, incluso bajo use strict; use warnings; use strict; use warnings; , entonces supongo que es al menos válido, y mi prueba (mínima) no coincide con nada, así que la envío para su crítica.

El más rápido será:

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

‘a’ puede ser cualquier carácter no especial (‘x’, ‘y’). La implementación de Knio puede ser un poco más pura, pero esta será más rápida para todas las cadenas que no comiencen con el carácter que elijas en lugar de ‘a’ porque no coincidirá después del primer carácter en lugar de después del segundo en esos casos.

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

Esto no funcionará para Python y muchos otros lenguajes, pero en una expresión regular de Javascript, [] es una clase de caracteres válida que no se puede combinar. Entonces, lo siguiente debería fallar inmediatamente, sin importar la entrada:

 var noMatch = /^[]/; 

Me gusta más que /$a/ porque para mí, comunica claramente su intención. Y en cuanto a cuándo alguna vez lo necesitaría, lo necesitaba porque necesitaba un respaldo para un patrón comstackdo dinámicamente en función de la entrada del usuario. Cuando el patrón no es válido, necesito reemplazarlo con un patrón que no coincida con nada. Simplificado, se ve así:

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

Yo creo eso

 \Z RE FAILS! \A 

cubre incluso los casos en los que la expresión regular incluye indicadores como MULTILINE, DOTALL, etc.

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

Creo (pero no lo he comparado) que cualquiera que sea la longitud (> 0) de la cadena entre \Z y \A , el tiempo hasta la falla debe ser constante.

Después de ver algunas de estas excelentes respuestas, el comentario de @ arantius (sobre el tiempo $x vs x^ vs (?!x)x ) en la respuesta actualmente aceptada me hizo querer medir algunas de las soluciones dadas hasta ahora.

Utilizando el estándar de línea de 275k de @ arantius, ejecuté las siguientes pruebas en Python (v3.5.2, IPython 6.2.1).

TL; DR: 'x^' y 'x\by' son los más rápidos en un factor de al menos ~ 16, y contrario al hallazgo de @ arantius, (?!x)x estaba entre los más lentos (~ 37 veces más lentos). Entonces, la cuestión de la velocidad ciertamente depende de la implementación. Pruébelo usted mismo en su sistema previsto antes de comprometerse si la velocidad es importante para usted.

ACTUALIZACIÓN: aparentemente hay una gran discrepancia entre el tiempo 'x^' y 'a^' . Consulte esta pregunta para obtener más información, y la edición anterior para los tiempos más lentos con a lugar de 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 primera vez que ejecuté esto, olvidé recuperar las últimas 3 expresiones, por lo que '\b' se interpretó como '\x08' , el carácter de retroceso. Sin embargo, para mi sorpresa, 'a\x08c' fue más rápido que el resultado anterior más rápido. Para ser justos, aún coincidirá con ese texto, pero pensé que todavía valía la pena señalarlo porque no estoy seguro de por qué es más rápido.

 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 

Mi archivo de prueba fue creado usando una fórmula para “… Contenido legible y sin líneas duplicadas” (en 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 

¿Tal vez esto?

 /$.+^/ 
 (*FAIL) 

o

 (*F) 

Con PCRE y PERL puede usar este verbo de control de retroceso que obliga al patrón a fallar inmediatamente.

¡Tantas buenas respuestas!

De forma similar a la respuesta de @ nivk, me gustaría compartir la comparación de rendimiento de Perl para diferentes variantes de expresiones regulares que nunca coinciden.

  1. Entrada: cadenas ascii pseudoaleatorias (25,000 líneas diferentes, longitud 8-16):

Velocidad 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. Entrada: / usr / share / dict / words (100,000 palabras en inglés).

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

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

y reemplazar … con todos los símbolos imprimibles;). Eso es para un archivo de texto.

¿Qué pasa con la expresión regular en lugar de con la expresión regular, solo usa una statement if false siempre? En javascript:

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

Una solución portátil que no dependerá de la implementación de expresiones regulares es simplemente usar una cadena constante que está seguro nunca aparecerá en los mensajes de registro. Por ejemplo, crea una cadena basada en lo siguiente:

 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 

Claro, esto no es un desafío intelectual, sino más bien como una progtwigción de cinta adhesiva .

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

Crea un patrón que contiene solo caracteres alfanuméricos y ‘ - ‘ (ninguno de los cuales son caracteres especiales de expresiones regulares), pero es estadísticamente imposible que la misma cadena haya aparecido en ningún lugar antes (porque ese es el objective de un GUID).

    Intereting Posts