r regex

expresiones regulares en la base R: ''perl=TRUE'' vs.el valor predeterminado(PCRE vs. TRE)



regex (3)

Cuando se utilizan funciones de cadena de base R como gsub y grep , ¿hay alguna desventaja para, como cuestión de costumbre, especificar siempre perl = TRUE ? ¿Hay alguna desventaja en esto?

Con perl=TRUE , las expresiones pueden hacer más cosas (por ejemplo, puede usar mirar hacia adelante o mirar hacia atrás las aserciones, o puede hacer la conversión de mayúsculas y minúsculas con //U ), y el rendimiento también es más rápido, como dice la documentación.

Entonces, ¿hay inconvenientes? ¿ perl = TRUE no es el predeterminado solo por compatibilidad con versiones anteriores? ¿Hay problemas de portabilidad que debería tener en cuenta cuando perl = TRUE?


Al ejecutar los puntos de referencia de @ wiktor-stribiżew, obtengo un resultado diferente de él. Con la primera prueba, el motor PCRE es más rápido que TRE (es decir, perl=TRUE es más rápido). Con el segundo punto de referencia, no hay una diferencia significativa en el rendimiento entre PCRE o TRE.

Estos se ejecutaron en la versión R 3.4.2 (2017-09-28), macOS Sierra 10.12.6, i7-2675QM CPU @ 2.20GHz

``` txt <- "Butterflies are insects in the macrolepidopteran clade Rhopalocera from the order Lepidoptera, which also includes moths. Adult butterflies have large, often brightly coloured wings, and conspicuous, fluttering flight. The group comprises the large superfamily Papilionoidea, which contains at least one former group, the skippers (formerly the superfamily /"Hesperioidea/") and the most recent analyses suggest it also contains the moth-butterflies (formerly the superfamily /"Hedyloidea/"). Butterfly fossils date to the Paleocene, which was about 56 million years ago." library(microbenchmark) PCRE_1 <- function(text) sub(''.*//((.*)//).*'', ''//1'', txt, perl=TRUE) TRE_1 <- function(text) sub(''.*//((.*)//).*'', ''//1'', txt) (test <- microbenchmark( PCRE_1(txt), TRE_1(txt), times = 500000 )) #> Unit: microseconds #> expr min lq mean median uq max neval #> PCRE_1(txt) 31.693 32.857 37.00757 33.413 35.805 43810.177 5e+05 #> TRE_1(txt) 46.037 47.199 53.06407 47.807 51.981 7702.869 5e+05 PCRE_2 <- function(text) regmatches(txt, gregexpr("/"[A-Za-z]+/"", txt, perl=TRUE)) TRE_2 <- function(text) regmatches(txt, gregexpr("/"[A-Za-z]+/"", txt)) (test <- microbenchmark( PCRE_2(txt), TRE_2(txt), times = 500000 )) #> Unit: microseconds #> expr min lq mean median uq max neval #> PCRE_2(txt) 63.801 68.115 75.51773 69.164 71.219 47686.40 5e+05 #> TRE_2(txt) 63.825 67.849 75.20246 68.883 70.933 49691.92 5e+05 ```


Mis resultados Ubuntu 16.04, - Perl es más rápido, ver abajo.

Unit: microseconds expr min lq mean median uq max neval cld PCRE_1(txt) 8.949 9.809 11.16 10.18 10.62 135299 5e+05 a TRE_1(txt) 23.816 24.805 26.84 25.23 26.17 5433 5e+05 b Unit: microseconds expr min lq mean median uq max neval cld PCRE_2(txt) 26.97 30.96 37.32 32.19 35.06 243164 5e+05 a TRE_2(txt) 33.75 38.07 44.50 39.40 43.33 35632 5e+05 b Session info ----------------------------------------------------------------- setting value version R version 3.4.2 (2017-09-28) system x86_64, linux-gnu ui RStudio (1.1.383) language en collate en_US.UTF-8 tz Europe/Berlin date 2017-11-12 Linux 4.4.0-93-generic #116-Ubuntu SMP Fri Aug 11 21:17:51 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux model name : Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz stepping : 3 microcode : 0x9 cpu MHz : 3647.929 cache size : 8192 KB


No es una buena idea comparar manzanas con naranjas, ya que PCRE regex puede hacer mucho más que TRE regex enine. Aunque comparten construcciones similares, incluso entonces las apariencias pueden resultar engañosas.

¿Qué es similar entre TRE y PCRE?

TRE admite literales como PCRE. Un literal es un carácter ordinario, un carácter hexadecimal de 8 bits (como /x1B ), un carácter hexadecimal ancho (como /x{263a} ) o un carácter escapado: /a , /e , /f , /n , /r , /t . PCRE admite más : /cx ("control-x", donde x es cualquier carácter ASCII), /0dd (carácter con código octal 0dd ), /ddd (carácter con código octal ddd o referencia posterior), /o{ddd..} (carácter con código octal ddd.. ), /xhh (carácter con código hexadecimal hh ), /x{hhh..} (carácter con código hexadecimal hhh.. ).

Ambos tienen un . comodín , pero en TRE, coincide con cualquier carácter, en PCRE, solo coincide con cualquier carácter pero saltos de línea (y cuáles dependen del verbo PCRE de convención de nueva línea, (*CR) , (*LF) , (*CRLF) , (*ANYCRLF) , (*ANY) ). gsub(".+", "~", "_/n_") dará como resultado ~ , pero gsub(".+", "~", "_/n_", perl=TRUE) producirá ~/n~ . Y un ejemplo opuesto, para hacer TRE . actúe como en PCRE, use el modificador (?n) , gsub("(?n).+", "~", "_/n_") para obtener ~/n~ (sin forma de elegir entre los estilos de final de línea) . En patrones PCRE, para hacer . coincide con los saltos de línea, debe usar el modificador DOTALL en línea (?s) antes . (o (?s:.*) como grupos modificadores).

Ambos admiten un operador de alternancia , pero como TRE es un motor dirigido por texto, las alternativas más largas coinciden, y en PCRE, la alternativa más a la izquierda "gana". sub("(s|su)", "~", "sub") produce ~b (ya que su es la alternativa de coincidencia más larga), pero sub("(s|su)", "~", "sub", perl=TRUE) produce ~ub (ya que s es la primera alternativa para hacer coincidir).

Ambos admiten backreferences , pero TRE solo admite hasta 9 referencias posteriores. Si necesita 10 o más, use PCRE. sub("(.)//1(.)//2(.)//3(.)//4(.)//5(.)//6(.)//7(.)//8(.)//9(.)//10", "~", "112233445566778899aa", perl=TRUE) encontrarán una coincidencia, sin perl=TRUE , no se detectará ninguna coincidencia.

Ambas parecen tener clases de caracteres , como [...] construcciones, pero de hecho, en el mundo POSIX al que pertenece TRE, se denominan expresiones de paréntesis . Si bien puede definir rangos de caracteres literales en ambos, o especificar caracteres literales con relación OR entre ellos, no se pueden usar clases de caracteres abreviados en las expresiones de paréntesis, ni ninguna secuencia de escape. El patrón [/d]+ en una expresión regular TRE se trata como 1 o más barras invertidas o / y letras d , mientras que en un patrón PCRE se analizará como 1+ dígitos (intente gsub("[//d]+", "~", "00//99d") (-> 00~99~ ) y gsub("[//d]+", "~", "00//99d", perl=TRUE) (-> ~/~d )). Este hecho explicará por qué [/]/-/[]+ en un patrón PCRE coincide con 1+ ] , - o [ y no en una expresión TRE donde necesita usar "colocación inteligente", como [][-] .

TRE y PCRE son compatibles con /d (dígitos), /D (sin dígitos), /w (caracteres de "palabras"), /W (caracteres "sin palabras"), /s (cualquier espacio en blanco), /S (cualquiera no espacios en blanco) clases de caracteres abreviados . Sin embargo, PCRE también admite /v (cualquier espacio en blanco vertical), /V (cualquier carácter que no sea un espacio en blanco vertical), /h (cualquier espacio en blanco horizontal), /H (cualquier carácter que no sea un espacio en blanco horizontal), /N (cualquiera carácter no de nueva línea), /X (cualquier grafema Unicode, útil cuando se procesan letras con signos diacríticos), /R (cualquier secuencia de salto de línea Unicode).

Ambos sabores admiten quantifiers , ¿ regular, codicioso ? , * , + , vago ?? , *? , +? , cuantificadores de rango / limitación como codiciosos {3} , {8,26} o {3,} y sus equivalentes perezosos con ? detrás de ellos. Tenga en cuenta que TRE tiene un soporte más pobre para cuantificadores limitantes (solo admite valores inferiores a 256 para el cuantificador {min} , y arroja excepciones de "memoria insuficiente" para {2557,} y valores mayores. Asegúrese de utilizar siempre el valor 0 para valor mínimo si es lo que implica, ya que {,2} en TRE en realidad coincide con 3 ocurrencias . Sin embargo, PCRE admite cuantificadores posesivos , ++ ?+ , *+ , {1,5}+ . Los patrones cuantificados con ellos no permiten retrocediendo hacia ellos, una vez emparejados, el motor nunca los vuelve a intentar.

Ambos tipos admiten clases de caracteres POSIX que se pueden utilizar entre [ ... ] . Sin embargo, TRE admite [:alnum:] (alfanumérico), [:alpha:] (letras), [:blank:] (espacio en blanco horizontal), [:cntrl:] (caracteres de control), [:digit:] (dígitos) , [:graph:] (caracteres visibles, cualquier cosa excepto espacios y caracteres de control), [:lower:] (letras minúsculas), [:print:] (todos los caracteres imprimibles), [:punct:] (símbolos y puntuación), [:space:] (cualquier espacio en blanco), [:upper:] (letras mayúsculas) y [:xdigit:] (caracteres en valores hexadecimales). PCRE agrega [:word:] (caracteres de "palabra") y [:ascii:] (cualquier carácter ASCII).

Ambos admiten límites de palabras, pero los patrones PCRE lo hacen de una manera más confiable. Cf. gsub("//b", "~", "CODE") produce ~C~O~D~E~ y gsub("//b", "~", "CODE", perl=T) produce ~CODE~ . Aunque TRE admite límites de palabras iniciales /b /< y finales /> específicos, PCRE /b son aún más confiables.

Ambos admiten modifiers línea que cambian cierto comportamiento del patrón cuando se usan dentro de un patrón, por ejemplo (?i) . TRE admite i (sin distinción entre mayúsculas y minúsculas), n (el punto ya no coincide con la nueva línea), r (hace que la expresión regular coincida de una manera asociativa derecha en lugar de la forma asociativa izquierda normal. Por defecto, la concatenación se deja asociativa en TRE, según la gramática dada en las especificaciones básicas de las expresiones regulares de Std 1003.1-2001 (POSIX). Este indicador invierte la asociatividad de la concatenación a la asociativa correcta. La asociatividad puede tener un efecto sobre cómo se divide una coincidencia en subcoincidencias, pero no cambia lo que coincide por toda la expresión regular) y U (intercambia codicia, *? vuelve codicioso y * vuelve perezoso). PCRE admite modificadores i y U , y más: m ( ^ y $ coinciden con el inicio / final de la línea , no toda la cadena), s (el punto coincide con la nueva línea), x (permite usar espacios en blanco para formatear el patrón y usar comentarios), J (permite usar nombres que capturan grupos con el mismo nombre), X (hace que las letras con una barra diagonal inversa sean un error si esa combinación no es un token regex válido), D (hace que $ solo coincida con el final de la cadena, de lo contrario, también coincide con una posición antes de la nueva línea final en la cadena) y A (solo coincide al comienzo de la cadena, como si hubiera /A o ^ delante).

Aspecto de retroceso

Consulte los documentos de TRE : el algoritmo de coincidencia utilizado en TRE utiliza el tiempo lineal de peor caso en la longitud del texto que se busca y el tiempo cuadrático de peor caso en la longitud de la expresión regular utilizada. En otras palabras, la complejidad temporal del algoritmo es O (M2N), donde M es la longitud de la expresión regular y N es la longitud del texto . Eso lleva a problemas con patrones como (.{2,})/1+ para buscar subcadenas duplicadas consecutivas. Consulte Eliminar elementos repetidos en una cadena con R.

Por lo tanto, cuando necesite confiar mucho en retroceder, elija PCRE.

¿Qué puede hacer PCRE y TRE no?

La deficiencia más visible de TRE es que no admite búsquedas. Sin embargo, hay muchas cosas de las que PCRE puede presumir :

Hay más cosas, como las anchors ( /A (inicio de cadena), /Z (final de cadena), /z (final de cadena)), construcción condicional "if-then-else" , agrupaciones atómicas (trabajando en el de la misma manera que los cuantificadores posesivos, pero no permite retroceder en secuencias enteras de patrones), etc.

Pruebas de referencia en Windows 7, Linux Ubuntu 16.04, MacOS Sierra 10.12.6

Si queremos comparar el rendimiento de los motores TRE y PCRE regex en R, debemos usar patrones simples que coincidan literalmente con los mismos textos con estos 2 motores.

Uso R principalmente en Windows, pero instalé R 3.2.3 en una máquina virtual Linux específicamente para esta prueba. Los resultados para MacOS están tomados de la respuesta de t.kalinowski .

Comparemos el rendimiento de expresiones regulares TRE (predeterminado) y PCRE ( perl=TRUE ) utilizando la biblioteca de microbenchmark (ver más opciones de benchmarking en R ):

library(microbenchmark)

El texto es un artículo de Wikipedia sobre mariposas .

txt <- "Butterflies are insects in the macrolepidopteran clade Rhopalocera from the order Lepidoptera, which also includes moths. Adult butterflies have large, often brightly coloured wings, and conspicuous, fluttering flight. The group comprises the large superfamily Papilionoidea, which contains at least one former group, the skippers (formerly the superfamily /"Hesperioidea/") and the most recent analyses suggest it also contains the moth-butterflies (formerly the superfamily /"Hedyloidea/"). Butterfly fossils date to the Paleocene, which was about 56 million years ago."

Intentemos extraer el último texto entre paréntesis con sub , una sub muy común en R:

# sub(''.*//((.*)//).*'', ''//1'', txt) # => [1] "formerly the superfamily /"Hedyloidea/"" PCRE_1 <- function(text) { return(sub(''.*//((.*)//).*'', ''//1'', txt, perl=TRUE)) } TRE_1 <- function(text) { return(sub(''.*//((.*)//).*'', ''//1'', txt)) } test <- microbenchmark( PCRE_1(txt), TRE_1(txt), times = 500000 ) test

Los resultados son los siguientes:

WINDOWS ------- Unit: microseconds expr min lq mean median uq max neval PCRE_1(txt) 163.607 165.418 168.65393 166.625 167.229 7314.588 5e+05 TRE_1(txt) 70.031 72.446 74.53842 73.050 74.257 38026.680 5e+05 MacOS ----- Unit: microseconds expr min lq mean median uq max neval PCRE_1(txt) 31.693 32.857 37.00757 33.413 35.805 43810.177 5e+05 TRE_1(txt) 46.037 47.199 53.06407 47.807 51.981 7702.869 5e+05 Linux ------ Unit: microseconds expr min lq mean median uq max neval PCRE_1(txt) 10.557 11.555 13.78216 12.097 12.662 4301.178 5e+05 TRE_1(txt) 25.875 27.350 31.51925 27.805 28.737 17974.716 5e+05

TRE regex sub gana solo en Windows , más de 2 veces más rápido. Tanto en MacOS como en Linux, la versión PCRE ( perl=TRUE ) gana con una proporción similar.

Ahora, comparemos el rendimiento de las expresiones regulares que no utilizan mucho el retroceso y extraiga las palabras entre comillas dobles:

# regmatches(txt, gregexpr("/"[A-Za-z]+/"", txt)) # => [1] "/"Hesperioidea/"" "/"Hedyloidea/"" PCRE_2 <- function(text) { return(regmatches(txt, gregexpr("/"[A-Za-z]+/"", txt, perl=TRUE))) } TRE_2 <- function(text) { return(regmatches(txt, gregexpr("/"[A-Za-z]+/"", txt))) } test <- microbenchmark( PCRE_2(txt), TRE_2(txt), times = 500000 ) test WINDOWS ------- Unit: microseconds expr min lq mean median uq max neval PCRE_2(txt) 324.799 330.232 349.0281 332.646 336.269 124404.14 5e+05 TRE_2(txt) 187.755 191.981 204.7663 193.792 196.208 74554.94 5e+05 MacOS ----- Unit: microseconds expr min lq mean median uq max neval PCRE_2(txt) 63.801 68.115 75.51773 69.164 71.219 47686.40 5e+05 TRE_2(txt) 63.825 67.849 75.20246 68.883 70.933 49691.92 5e+05 LINUX ----- Unit: microseconds expr min lq mean median uq max neval PCRE_2(txt) 30.199 34.750 44.05169 36.151 43.403 38428.2 5e+05 TRE_2(txt) 37.752 41.854 52.58230 43.409 51.781 38915.7 5e+05

El mejor valor medio pertenece a la expresión regular PCRE en Linux, en MacOS, la diferencia es casi negligente, y en Windows, TRE funciona mucho más rápido.

Resumen

Está claro que la biblioteca de expresiones regulares TRE (predeterminada) funciona mucho más rápido en Windows . En Linux , la expresión regular de PCRE es considerablemente más rápida. En MacOS , la expresión regular de PCRE sigue siendo preferible ya que, con patrones de retroceso, la expresión regular de PCRE es más rápida que TRE en ese sistema operativo.