Corrispondenza rapida stringa parziale in R

Question

Dato un vettore di stringhe texts e un vettore di modelli patterns, voglio trovare qualsiasi modello corrispondente per ogni testo.

Per piccoli gruppi di dati, questo può essere fatto facilmente in R con grepl:

patterns = c("some","pattern","a","horse") 
texts = c("this is a text with some pattern", "this is another text with a pattern") 

# for each x in patterns 
lapply(patterns, function(x){ 
    # match all texts against pattern x 
    res = grepl(x, texts, fixed=TRUE) 
    print(res) 
    # do something with the matches 
    # ... 
}) 

Questa soluzione è corretto, ma non scalare. Anche con dataset moderatamente più grandi (~ 500 testi e pattern), questo codice è imbarazzantemente lento, risolvendo solo circa 100 casi al secondo su una macchina moderna - il che è ridicolo considerando che si tratta di una parzialità parziale della stringa grezza, senza regex (impostata con fixed=TRUE). Anche la creazione del parallelo lapply non risolve il problema. C'è un modo per riscrivere questo codice in modo efficiente?

Grazie, Mulone

Answer 1

Sei accuratamente caratterizzato il vostro problema e le prestazioni che stai vedendo? Ecco il Complete Works of William Shakespeare e una query contro di loro

text = readLines("~/Downloads/pg100.txt") 
pattern <- 
    strsplit("all the world's a stage and all the people players", " ")[[1]] 

che sembra essere molto più performante di quello che comporta?

> length(text) 
[1] 124787 
> system.time(xx <- lapply(pattern, grepl, text, fixed=TRUE)) 
    user system elapsed 
    0.444 0.001 0.444 
## avoid retaining memory; 500 x 500 case; no blank lines 
> text = text[nzchar(text)] 
> system.time({ for (p in rep(pattern, 50)) grepl(p, text[1:500], fixed=TRUE) }) 
    user system elapsed 
    0.096 0.000 0.095 

Ci si aspetta il ridimensionamento lineare con la lunghezza (numero di elementi) di motivo e testo. Sembra che mis-ricordo il mio Shakespeare

> idx = Reduce("+", lapply(pattern, grepl, text, fixed=TRUE)) 
> range(idx) 
[1] 0 7 
> sum(idx == 7) 
[1] 8 
> text[idx == 7] 
[1] " And all the men and women merely players;"      
[2] " cicatrices to show the people when he shall stand for his place." 
[3] " Scandal'd the suppliants for the people, call'd them"    
[4] " all power from the people, and to pluck from them their tribunes" 
[5] " the fashion, and so berattle the common stages (so they call"  
[6] " Which God shall guard; and put the world's whole strength"  
[7] " Of all his people and freeze up their zeal,"      
[8] " the world's end after my name-call them all Pandars; let all"  

Answer 2

Usa pacchetto stringi - è anche più veloce di Grepl. Controlla i parametri! Ho usato il testo da @ Martin-Morgan post

require(stringi) 
require(microbenchmark) 

text = readLines("~/Desktop/pg100.txt") 
pattern <- strsplit("all the world's a stage and all the people players", " ")[[1]] 

grepl_fun <- function(){ 
    lapply(pattern, grepl, text, fixed=TRUE) 
} 

stri_fixed_fun <- function(){ 
    lapply(pattern, function(x) stri_detect_fixed(text,x,NA)) 
} 

#  microbenchmark(grepl_fun(), stri_fixed_fun()) 
# Unit: milliseconds 
#     expr  min  lq median  uq  max neval 
#   grepl_fun() 432.9336 435.9666 446.2303 453.9374 517.1509 100 
#  stri_fixed_fun() 213.2911 218.1606 227.6688 232.9325 285.9913 100 

# if you don't believe me that the results are equal, you can check :) 
xx <- grepl_fun() 
stri <- stri_fixed_fun() 

for(i in seq_along(xx)){ 
    print(all(xx[[i]] == stri[[i]])) 
}