빠른 부분 문자열 일치 R

Question

문자열의 벡터 texts과 패턴 patterns의 벡터가 주어지면 각 텍스트에 대해 일치하는 패턴을 찾고 싶습니다.

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

이 솔루션은 정확하지만 확장하지 않습니다 작은 데이터 세트에 대한

이 쉽게 grepl와 R에서 수행 할 수 있습니다. 약간 큰 데이터 세트 (~ 500 개의 텍스트와 패턴)가 있더라도,이 코드는 현대 기계에서 초당 약 100 개의 케이스를 해결한다는 것은 당황 스럽습니다. 이것은 정규 표현식을 사용하지 않고 조잡한 문자열 부분 매칭이라고 생각하면 어리 석습니다 (fixed=TRUE). lapply을 병렬로 설정해도 문제가 해결되지 않습니다. 이 코드를 효율적으로 다시 쓸 수있는 방법이 있습니까?

덕분에, Mulone

Answer 1

당신은 정확하게 문제와 당신이보고있는 성능을 특징으로 적이 있습니까? 여기에 Complete Works of William Shakespeare 훨씬 더 성능이 좋은 당신이 의미하는 것보다 것 같다 그들

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

에 대한 쿼리는 무엇입니까?

> 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 

패턴과 텍스트의 길이 (요소 수)가 모두 선형이어야합니다. 그것은 더 빨리 grepl 이상입니다 - I의 나의 셰익스피어

> 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

사용 stringi 패키지를 잘못 기억 보인다. 벤치 마크를 확인하십시오! @ Martin-Morgan 게시물의 텍스트를 사용했습니다.

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]])) 
}