Быстрое совпадение частичных строк в R

Для вектора строк texts и вектора шаблонов patterns, я хочу найти любой шаблон соответствия для каждого текста.

Для небольших наборов данных это легко сделать в R с помощью 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
  # ...
})

Это решение правильно, но оно не масштабируется. Даже с умеренно большими наборами данных (~ 500 текстов и шаблонов) этот код смущающе медленный, решая всего около 100 случаев в секунду на современной машине, что смешно, учитывая, что это грубое частичное совпадение строк без регулярного выражения (установлено с fixed=TRUE). Даже создание параллели lapply не решает проблему. Есть ли способ переписать этот код эффективно?

Спасибо, Mulone

Ответы

Ответ 1

Использовать пакет stringi - он даже быстрее, чем grepl. Проверьте контрольные показатели! Я использовал текст сообщения @Martin-Morgan

require(stringi)
require(microbenchmark)

text = readLines("~/Desktop/pg100.txt")
pattern <-  strsplit("all the world 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]]))
}

Ответ 2

Вы точно охарактеризовали свою проблему и производительность, которую видите? Вот Произведения Уильяма Шекспира и запрос против них

text = readLines("~/Downloads/pg100.txt")
pattern <- 
    strsplit("all the world 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

Мы ожидаем линейного масштабирования с длиной (числом элементов) шаблона и текста. Кажется, я неправильно помню своего Шекспира

> 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 whole strength"       
[7] "    Of all his people and freeze up their zeal,"                     
[8] "    the world end after my name-call them all Pandars; let all"