Сравнение двух больших строковых векторов занимает слишком много времени (удалите стоп-слова)

Я пытаюсь подготовить набор данных для машинного обучения. В процессе я хотел бы удалить (стоп) слова, которые встречаются редко (часто связанные с плохим чтением OCR). В настоящее время у меня есть список слов, содержащий около 1 млн слов, которые я хочу удалить.

Но обработка моего набора данных с этой настройкой занимает много времени.

library(stringi)
#generate the stopword list
b <- stri_rand_strings(1000000, 4, pattern = "[A-Za-z0-9]")

#remove stopstopwords form the dataset
system.time({
  a <- stri_rand_strings(10, 4, pattern = "[A-Za-z0-9]") 
  c <- a[!(a %in% b)]
  c
})

user  system elapsed 
0.14    0.00    0.14

Похоже, что «a% in% b» (далеко от) O (N). Невозможно запустить это на всем наборе данных, так как процесс не завершается в течение нескольких часов.

Существуют ли более эффективные способы сравнения двух векторов в R?

Я подозреваю, что это должно быть очень быстро, так как это поиск. Я провел тест со словарем на C#, который завершился за несколько минут.


r string stringi string-interpolation string-search
person henrikwh    schedule 15.08.2016    source источник
comment
Попробуйте с %chin% из data.table должно быть быстрее, т.е. system.time({ c <- a[!(a %chin% b)]}) # user system elapsed 0.01 0.00 0.02 по сравнению с 0.13 на основе %in%   -  person akrun    schedule 15.08.2016

Ответы (1)


arrow_upward
0
arrow_downward

stringi функция поиска, такая как stri_detect_fixed, намного быстрее, чем оператор %in%. Возможно, это поможет вам:

  1. вставьте все ваши стоп-слова, используя какой-нибудь разделитель, которого эти слова не содержат -> это создаст одну длинную строку
  2. используйте stri_detect_fixed для этой длинной строки

Это решение оказывается вдвое или даже в двадцать раз быстрее, если ваш вектор стоп-слова вставляется один раз и используется повторно.

Пример кода с тестами:

library(stringi)
require(microbenchmark)
#generate the stopword list
b <- stri_rand_strings(1000000, 4, pattern = "[A-Za-z0-9]")
a <- stri_rand_strings(10, 4, pattern = "[A-Za-z0-9]") 

#base R solution
f1 <- function(a,b){
  a[!(a %in% b)]
}

# paste inside function
f2 <- function(a,b){
  c <- stri_paste(b, collapse = ";")
  a[stri_detect_fixed(c, a)]
}

# paste before and use it later
c <- stri_paste(b, collapse = ";")
f3 <- function(a, c){
  a[stri_detect_fixed(c, a)]
}

microbenchmark(f1(a,b), f2(a,b), f3(a,c))
# Unit: milliseconds
#      expr      min        lq       mean     median         uq       max neval
#  f1(a, b) 63.36563 67.931506 102.725257 116.128525 129.665107 208.46003   100
#  f2(a, b) 52.95146 53.983946  58.490224  55.860070  59.863900  89.41197   100
#  f3(a, c)  3.70709  3.831064   4.364609   4.023057   4.310221  10.77031   100
person bartektartanus    schedule 17.02.2017