Szybkie częściowe dopasowanie ciągów w R

Question

Biorąc pod uwagę wektor ciągów texts i wektor wzorów patterns, chcę znaleźć dowolny pasujący wzór dla każdego tekstu.

Dla małych zbiorów danych, może być łatwo wykonana z grepl R:

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

To rozwiązanie jest prawidłowe, ale nie skalowania. Nawet z umiarkowanie dużymi zbiorami danych (~ 500 tekstów i wzorców) kod ten jest zawstydzająco wolny, rozwiązując tylko około 100 przypadków na sekundę na nowoczesnej maszynie - co jest śmieszne, biorąc pod uwagę, że jest to proste częściowe dopasowywanie ciągów, bez regex (ustawiane za pomocą fixed=TRUE). Nawet robienie paragrafu lapply nie rozwiązuje problemu. Czy istnieje sposób na ponowne napisanie tego kodu wydajnie?

Dzięki Mulone

Answer 1

Czy trafnie charakteryzuje swój problem i wydajność jesteś widzeniem? Oto Complete Works of William Shakespeare i kwerendy przeciwko nim

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

co wydaje się być znacznie bardziej wydajnych niż sugerujesz?

> 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 

Oczekujemy skalowania liniowego z długością (liczbą elementów) wzoru i tekstu. Wydaje się mis zapamiętania mój Szekspir

> 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

Używaj stringi pakietu - to nawet szybciej niż Grepl. Sprawdź benchmarki! Użyłem tekstu z @ 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]])) 
}