r - 比较两个大字符串向量花费的时间太长(删除停用词)

Question

我正在尝试为机器学习准备数据集。在此过程中，我想删除(停止)出现次数很少的单词(通常与错误的 OCR 读数有关)。目前我有一个包含大约 1 个我想删除的 mio 单词的单词列表。

但是，使用此设置处理我的数据集需要很长时间。

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# 中的 Dictionary 做了一个测试，它在几分钟内完成。

Answer 1

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