R更快的gregexpr非常大的字符串

Question

我正在尝试gregexpr在一个大字符串中搜索"ABCD"的位置,并在同一个字符串中搜索"ABBD,ACCD,AAAD".我想将"ABCD"搜索结果和"ABBD,ACCD,AAAD"搜索结果输出到数据表的两个单独列中.

我目前的方法是单独使用gregexpr,将每个导出为1列txt文件,将每个导出为矩阵,对每个1列矩阵进行排序,使数字逐行增加,列绑定两个矩阵,并将得到的两个列矩阵转换为数据表.

在处理非常大的字符串时,这种方法似乎非常低效,并且需要很长时间才能完成.有没有办法优化程序？谢谢你的帮助!

# dummy string that is relatively short for this demo
x <- "ABCDACCDABBDABCDAAADACCDABBDABCD"

# SEARCH for 'ABCD' location
out1 <- gregexpr(pattern = "ABCD", x)
cat(paste(c(out1[[1]]), sep = "\n", collapse = "\n"), file = "~/out_1.txt")    

# SEARCH for 'A??D' location
outB <- gregexpr(pattern = "ABBD", x)
outC <- gregexpr(pattern = "ACCD", x)
outA <- gregexpr(pattern = "AAAD", x)
cat(paste(c(outA[[1]], outB[[1]], outC[[1]]), collapse = "\n"), file = "~/out_2.txt")

# Function that BINDS Matrices by column
cbind.fill <- function(...){
  nm <- list(...)
  nm <- lapply(nm, as.matrix)
  n <- max(sapply(nm, nrow))
  do.call(cbind, lapply(nm, function (x) rbind(x, matrix(, n-nrow(x), ncol(x)))))
}

# Load as Tables --> Sort by numbers increasing --> Matrices
mat1 <- as.matrix(read.table("~/out_1.txt"))
mat2.t <- (read.table("~/out_2.txt"))
mat2 <- as.matrix(mat2.t[order(mat2.t$V1),])

# Combine two matrices to create 2 column matrix 
comb_mat <- cbind.fill(mat1, mat2)
write.table(comb_mat, file = "~/comb_mat.txt", row.names = FALSE, col.names = FALSE)

Answer 1

• 不需要中间文件.
• 我会使用fixed=T参数gregexpr(),这可能会产生性能优势.来自https://stat.ethz.ch/R-manual/R-devel/library/base/html/grep.html:

如果您正在进行大量正则表达式匹配(包括非常长的字符串),则需要考虑使用的选项.通常PCRE将比默认正则表达式引擎更快,并且仍然更快固定= TRUE(特别是当每个模式仅匹配几次时).

• 您可以使用sort()立即对第二列进行排序,而不是存储中间变量,然后使用索引对其进行索引order().
• 您的cbind.fill()函数可以正常工作,但NA-padding的任务可以通过越界索引轻松完成,对于该索引,R自然会返回越界索引的NA.

因此:

x <- 'ABCDACCDABBDABCDAAADACCDABBDABCD';
out1 <- c(gregexpr('ABCD',x,fixed=T)[[1]]);
out2 <- sort(c(gregexpr('AAAD',x,fixed=T)[[1]],gregexpr('ABBD',x,fixed=T)[[1]],gregexpr('ACCD',x,fixed=T)[[1]]));
outmax <- max(length(out1),length(out2));
comb_mat <- cbind(out1[1:outmax],out2[1:outmax]);
comb_mat;
##      [,1] [,2]
## [1,]    1    5
## [2,]   13    9
## [3,]   29   17
## [4,]   NA   21
## [5,]   NA   25

然后,您可以comb_mat根据您的write.table()电话写入文件.

编辑:正如你(现在我)发现的那样,gregexpr()在大字符串上执行效果出乎意料地差,而你的237MB字符串肯定是一个大字符串.从R中的快速部分字符串匹配,我们可以使用该stringi包来加速性能.以下是如何使用stringi::stri_locate_all()来完成您的要求的演示.一些说明:

• 对于我自己的测试,我创建了自己的237MB文件,实际上大小为237,000,001字节.我基本上使用vim重复你的32字节示例字符串7,406,250次,总计237,000,000字节,额外的字节来自vim附加的LF.我命名了我的测试文件x,你可以看到我加载它data.table::fread(),因为read.table()它花了太长时间.
• 我对NA填充算法做了一些小改动.我没有使用越界索引,而是意识到我们可以将向量的长度分配给最大长度,从而为赋值运算符利用从右到左的关联性.这里的优点是我们不再需要构造索引向量1:outmax.

因此:

library('data.table');
library('stringi');
x <- fread('x',header=F)$V1;
## Read 1 rows and 1 (of 1) columns from 0.221 GB file in 00:00:03
system.time({ out1 <- stri_locate_all(x,regex='ABCD')[[1]][,'start']; });
##    user  system elapsed
##   3.687   0.359   4.044
system.time({ out2 <- stri_locate_all(x,regex='AAAD|ABBD|ACCD')[[1]][,'start']; });
##    user  system elapsed
##   4.938   0.454   5.404
length(out1);
## [1] 22218750
length(out2);
## [1] 37031250
length(out1) <- length(out2) <- max(length(out1),length(out2));
comb_mat <- cbind(out1,out2);
head(comb_mat);
##      out1 out2
## [1,]    1    5
## [2,]   13    9
## [3,]   29   17
## [4,]   33   21
## [5,]   45   25
## [6,]   61   37
tail(comb_mat);
##             out1      out2
## [37031245,]   NA 236999961
## [37031246,]   NA 236999973
## [37031247,]   NA 236999977
## [37031248,]   NA 236999985
## [37031249,]   NA 236999989
## [37031250,]   NA 236999993
nrow(comb_mat);
## [1] 37031250