r - 大数据集上的高效子字符串搜索

Question

我有一个大型数据集tPro1(约 500k 点)。如下所示，感兴趣的变量是 tPro1$Path。

      Path                                  Row      rm                                              
1  >root>aaaa>bbbb>cccc>dddd>hello         1        TRUE
2  >root>aaaa>bbbb>cccc>dddd>greetings     2        TRUE
3  >root>aaaa>bbbb>cccc>dddd>example       3        TRUE
4  >root>iiii>jjjj>kkkk>llll>mmmm          4        TRUE
5  >root>iiii>jjjj>kkkk>nnnn>testing       5        TRUE

我还有一个较小的数据集，我们称之为 Sub1，包含几十个左右的数据点。它具有比 tPro1 更高级别的路径。

     [1] ">root>aaaa>bbbb>cccc>dddd"
     [2] ">root>aaaa>bbbb>eeee>ffff"
     [3] ">root>aaaa>bbbb>gggg>hhhh" 
     [4] ">root>iiii>jjjj>kkkk>llll>mmmm"
     [5] ">root>iiii>jjjj>kkkk>nnnn" 
     [6] ">root>oooo>pppp>qqqq"

我想要做的是将 tPro1 中的较长路径与 Sub1 中的较短路径关联起来。 tPro1 是 Pro0 一些关键信息的副本。输出 Pro0 将为

          Path                                  Short_path                                                    
1  >root>aaaa>bbbb>cccc>dddd>hello         >root>aaaa>bbbb>cccc>dddd
2  >root>aaaa>bbbb>cccc>dddd>greetings     >root>aaaa>bbbb>cccc>dddd
3  >root>aaaa>bbbb>cccc>dddd>example       >root>aaaa>bbbb>cccc>dddd
4  >root>iiii>jjjj>kkkk>llll>mmmm          >root>iiii>jjjj>kkkk>llll>mmmm
5  >root>iiii>jjjj>kkkk>nnnn>testing       >root>iiii>jjjj>kkkk>nnnn

我编写了一个循环，对于 Sub1 中的每个路径，grepl 都会检查每个 tPro1 以查看它是否是子字符串。对于 500k*24 点，这将是一个非常低效的过程，因此我尝试了一些优化:

1. 注意tPro1$rm。当找到子字符串时，将其设置为 false。之后它们将被删除/跳过，以节省无意义的重新检查时间。
2. Path 可能在 tPro1 中出现多次。因此，当找到 s 的有效子字符串 p 时，算法不会继续执行 grepl，而是遍历数据集并查找 s 的所有未经检查的实例。

我的代码是

start.time <- Sys.time()

for (p in Sub1$Path) {
  for (i in 1:NROW(tPro1)) {
    if (tPro1[i,3]) {
      if (grepl(p, tPro1[i,1], fixed=TRUE)) {
        # Replace all of subpath 
        for (j in i:NROW(tPro1)) {
          if (tPro1[j,1] == tPro1[i,1]) {
            Pro0[tPro1[j,2],2] <- p
            tPro1[j,3] <- FALSE
          }
        }
      }
    }
  }
  v <- unlist(tPro1[,3])
  tPro1 <- tPro1[v,]
}

end.time <- Sys.time()
time.taken <- end.time - start.time
time.taken

处理完整数据集不会在人类时间内停止(至少在我的机器上)。出于说明目的，一次执行 1000 个批处理(减少 tPro1)需要 46 秒。 2000需要1分钟，3000:1.4分钟。

有什么明显的改进可以做，或者这只是问题的本质？

编辑:大约有 54k 个唯一的长路径，而且并非所有的长路径都有相应的短路径(例如，在 tPro1 中，有 >root>strange>path，而在 sub1 中，没有 >root>strange) 形式的路径

编辑2:关注rosscova下面的答案，时间从可能永恒缩短到 279.75 秒!

Answer 1

使用模糊匹配，agrepl:

tPro1$Short_path <- Sub1$Path[ apply(sapply(Sub1$Path, function(i) agrepl(i, tPro1$Path)), 1, which) ] 

tPro1

#                                  Path Row   rm                     Short_path
# 1     >root>aaaa>bbbb>cccc>dddd>hello   1 TRUE      >root>aaaa>bbbb>cccc>dddd
# 2 >root>aaaa>bbbb>cccc>dddd>greetings   2 TRUE      >root>aaaa>bbbb>cccc>dddd
# 3   >root>aaaa>bbbb>cccc>dddd>example   3 TRUE      >root>aaaa>bbbb>cccc>dddd
# 4      >root>iiii>jjjj>kkkk>llll>mmmm   4 TRUE >root>iiii>jjjj>kkkk>llll>mmmm
# 5   >root>iiii>jjjj>kkkk>nnnn>testing   5 TRUE      >root>iiii>jjjj>kkkk>nnnn

数据

tPro1  <- read.table(text = "Path                                  Row      rm                                              
1  >root>aaaa>bbbb>cccc>dddd>hello         1        TRUE
2  >root>aaaa>bbbb>cccc>dddd>greetings     2        TRUE
3  >root>aaaa>bbbb>cccc>dddd>example       3        TRUE
4  >root>iiii>jjjj>kkkk>llll>mmmm          4        TRUE
5  >root>iiii>jjjj>kkkk>nnnn>testing       5        TRUE",
                     header = TRUE, stringsAsFactors = FALSE)


Sub1 <- data.frame(Path = c(">root>aaaa>bbbb>cccc>dddd",
                            ">root>aaaa>bbbb>eeee>ffff",
                            ">root>aaaa>bbbb>gggg>hhhh",
                            ">root>iiii>jjjj>kkkk>llll>mmmm",
                            ">root>iiii>jjjj>kkkk>nnnn",
                            ">root>oooo>pppp>qqqq"),
                   stringsAsFactors = FALSE)