在大型數據集上進行高效的子字符串搜索

Question

我有一個大型數據集tPro1（〜500k points）。如下所示，感興趣的變量是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，一對夫婦十幾dataponts的。它具有比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。之後它們被移除/跳過以節省無意義的重新檢查時間。
   1. 路徑s可能在tPro1中出現多次。因此，當爲s發現有效的子字符串p時，算法會遍歷數據集並查找s的所有未經檢查的實例，而不是繼續執行grepl。

我的代碼是

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）需要46secs。 2000需要1分鐘，3000：1.4分鐘。

可以做出什麼顯着的改進，還是僅僅是問題的本質？

編輯：大約有54K獨特長的路徑，並且還不是所有的長路徑的具有對應的短路徑（例如在tPro1有>root>strange>path，而在sub1沒有形式>root>strange的路徑）

編輯2：在下面的rosscova的回答下，時間從可能的永恆性下降到279.75秒！

Answer 1

事實上，sub是如此之小，可以幫助很多在減少必要的迭代次數。儘管我仍然在這裏使用一個循環，但這是比你得到的更有效的方法。

首先，設置一些測試數據。如您指定使用相同的尺寸：

set.seed(123) 

sub <- sapply(seq_len(24), function(x) { 
    paste(sample(c(letters, ">"), 
        12, 
        replace = TRUE, 
        prob = c(rep(1, 26), 8)), 
      collapse = "") 
}) 
head(sub, 3) 
# [1] "puhyz>lymjbj" "rn>yc>fbyrda" "qsmop>byrv>k" 

使用sub創建tPro1這樣有子找到適當的。

tPro1 <- paste0(sample(sub, 
         5E5, 
         replace = TRUE), 
       sample(c(">hello", ">adf", ">;kjadf"), 
         5E5, 
         replace = TRUE) 
) 
head(tPro1, 3) 
# [1] "bjwhrj>j>>zj>adf" "b>>>zpx>fpvg>hello" ">q>hn>ljsllh>adf" 

現在使用while循環。遍歷sub，在每次迭代中獲得儘可能多的匹配。如果我們到達sub的末尾，或者所有值都已填充，請停止迭代。

results <- vector("character", length(tPro1)) 
i <- 1L 
system.time(
    while(sum(results == "") > 0L && i <= length(sub)) { 
     results[ grep(sub[i], tPro1) ] <- sub[i] 
     i <- i + 1L 
    } 
) 
# user system elapsed 
# 4.655 0.007 4.661 

輸出結果。

output <- data.frame(tPro1 = tPro1, results = results, stringsAsFactors = FALSE) 
head(output, 3) 

#        tPro1     results 
# 1 >>ll>ldsjbzzcszcniwm>>em>;kjadf >>ll>ldsjbzzcszcniwm>>em 
# 2 ijka>ca>>>ddpmhilphqlt>c>;kjadf ijka>ca>>>ddpmhilphqlt>c 
# 3 zpnsniwyletn>qzifzjtrjg>>;kjadf zpnsniwyletn>qzifzjtrjg> 

所以這不是一個完全矢量化的解決方案，但它確實爲您節省了一些時間。對於您正在使用的相同大小的數據集，我們降至4.6秒。

編輯：傻我，我使用sub幾千個值長。將sub的尺寸縮小爲幾十像之後，就可以讓它快得多！

編輯：用你已經證明它的數據，你可能需要先創建tPro1和sub載體：

tPro1.vec <- tPro1$Path 
sub <- Sub1$Path 

results <- vector("character", length(tPro1.vec)) 
i <- 1L 
while(sum(results == "") > 0L && i <= length(sub)) { 
    results[ grep(sub[i], tPro1.vec) ] <- sub[i] 
    i <- i + 1L 
} 

Answer 2

鑑於兩個數據集（在data.table形式）：

library(data.table) # for data manipulation 
library(stringi) # for string manipulation 

>dt1 
           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 

> dt2 # introduced column name `names` 

         names 
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 

dt1b<-cbind(t(dt1[,stri_split(Path,fixed=">")]),dt1[,.(Row,rm)])[,V1:=NULL] 
dt2b<-data.table(t(dt2[,stri_split(str = names,fixed=">")]))[,V1:=NULL] 

>dt1b 
     V2 V3 V4 V5 V6  V7 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 

和

>dt2b 
     V2 V3 V4 V5 V6 V7 
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  root 

最後，我通過比較dt1b的每一行的dt2b的每一行：

sub1<-subset(dt1b, select = grep("^V+", names(dt1b),perl = TRUE,value = TRUE)) 

創建（包含列表）所有寶ssible比較

l1<-lapply(seq(1:nrow(sub1)),function(x) {l1<-lapply(seq(1:nrow(dt2b)),function(y) {l2<-data.table(t(sub1[x] %in% dt2b[y]));names(l2)<-paste0(dt2b[y]);return(l2)}); names(l1)<-paste(sub1[x],collapse=" ");return(l1)}) 

結果

 l1[1:2] 
    [[1]] 
    [[1]]$`root aaaa bbbb cccc dddd hello` 
     root aaaa bbbb cccc dddd  
    1: TRUE TRUE TRUE TRUE TRUE FALSE 

    [[1]]$<NA> 
     root aaaa bbbb eeee ffff  
    1: TRUE TRUE TRUE FALSE FALSE FALSE 

    [[1]]$<NA> 
     root aaaa bbbb gggg hhhh  
    1: TRUE TRUE TRUE FALSE FALSE FALSE 

    [[1]]$<NA> 
     root iiii jjjj kkkk llll mmmm 
    1: TRUE FALSE FALSE FALSE FALSE FALSE 

    [[1]]$<NA> 
     root iiii jjjj kkkk nnnn  
    1: TRUE FALSE FALSE FALSE FALSE FALSE 

    [[1]]$<NA> 
     root oooo pppp qqqq  root 
    1: TRUE FALSE FALSE FALSE FALSE FALSE 



    [[2]] 
    [[2]]$`root aaaa bbbb cccc dddd greetings` 
     root aaaa bbbb cccc dddd  
    1: TRUE TRUE TRUE TRUE TRUE FALSE 

    [[2]]$<NA> 
     root aaaa bbbb eeee ffff  
    1: TRUE TRUE TRUE FALSE FALSE FALSE 

    [[2]]$<NA> 
     root aaaa bbbb gggg hhhh  
    1: TRUE TRUE TRUE FALSE FALSE FALSE 

    [[2]]$<NA> 
     root iiii jjjj kkkk llll mmmm 
    1: TRUE FALSE FALSE FALSE FALSE FALSE 

    [[2]]$<NA> 
     root iiii jjjj kkkk nnnn  
    1: TRUE FALSE FALSE FALSE FALSE FALSE 

    [[2]]$<NA> 
     root oooo pppp qqqq  root 
    1: TRUE FALSE FALSE FALSE FALSE FALSE 

所以部分現在你可以有一個得分每dt1b例如排0/6（甚至不接近），...，5/6（幾乎相同），6/6（完全相同）。

IDEA（編輯）

這裏是我的想法：

l2<-lapply(seq_along(1:length(l1)),function(x) { 
    z=rbindlist(t(l1[[x]][1:nrow(dt2b)]),fill = TRUE) 
    z=cbind(z,score=apply(z,1,sum,na.rm=TRUE)) 
    setorder(z,-score) 
    z[,V1:=NULL] 
    z<-cbind(t(rep(names(l1[[x]][1]))),z) 
    names(z)[1]<-"initialString" 
    return(z) 
}) 


    > l2[1:2] 
[[1]] 
        initialString root aaaa bbbb cccc dddd eeee ffff gggg hhhh iiii jjjj kkkk llll mmmm nnnn score 
1: root aaaa bbbb cccc dddd hello TRUE TRUE TRUE TRUE TRUE NA NA NA NA NA NA NA NA NA NA  5 
2: root aaaa bbbb cccc dddd hello TRUE TRUE TRUE NA NA FALSE FALSE NA NA NA NA NA NA NA NA  3 
3: root aaaa bbbb cccc dddd hello TRUE TRUE TRUE NA NA NA NA FALSE FALSE NA NA NA NA NA NA  3 
4: root aaaa bbbb cccc dddd hello TRUE NA NA NA NA NA NA NA NA FALSE FALSE FALSE FALSE FALSE NA  1 
5: root aaaa bbbb cccc dddd hello TRUE NA NA NA NA NA NA NA NA FALSE FALSE FALSE NA NA FALSE  1 

[[2]] 
         initialString root aaaa bbbb cccc dddd eeee ffff gggg hhhh iiii jjjj kkkk llll mmmm nnnn score 
1: root aaaa bbbb cccc dddd greetings TRUE TRUE TRUE TRUE TRUE NA NA NA NA NA NA NA NA NA NA  5 
2: root aaaa bbbb cccc dddd greetings TRUE TRUE TRUE NA NA FALSE FALSE NA NA NA NA NA NA NA NA  3 
3: root aaaa bbbb cccc dddd greetings TRUE TRUE TRUE NA NA NA NA FALSE FALSE NA NA NA NA NA NA  3 
4: root aaaa bbbb cccc dddd greetings TRUE NA NA NA NA NA NA NA NA FALSE FALSE FALSE FALSE FALSE NA  1 
5: root aaaa bbbb cccc dddd greetings TRUE NA NA NA NA NA NA NA NA FALSE FALSE FALSE NA NA FALSE  1 

...或者通過保持與最大score列行，（這可以通過實現：return(z)變成在return(z[score==max(score)])以上l2 lapply()）和rbindlist(t(l2[1:length(l2)]))：

     initialString root aaaa bbbb cccc dddd eeee ffff gggg hhhh iiii jjjj kkkk llll mmmm nnnn score 
1:  root aaaa bbbb cccc dddd hello TRUE TRUE TRUE TRUE TRUE NA NA NA NA NA NA NA NA NA NA  5 
2: root aaaa bbbb cccc dddd greetings TRUE TRUE TRUE TRUE TRUE NA NA NA NA NA NA NA NA NA NA  5 
3: root aaaa bbbb cccc dddd example TRUE TRUE TRUE TRUE TRUE NA NA NA NA NA NA NA NA NA NA  5 
4:  root iiii jjjj kkkk llll mmmm TRUE NA NA NA NA NA NA NA NA TRUE TRUE TRUE TRUE TRUE NA  6 
5: root iiii jjjj kkkk nnnn testing TRUE NA NA NA NA NA NA NA NA TRUE TRUE TRUE NA NA TRUE  5 

列initialString現在豪lds最初的字符串。以下各列將其分解爲子字符串及其相似度得分

Answer 3

以下代碼應該很快解決您的問題。

library(data.table) 
library(stringi) 

Pro0 <- data.table(tPro1) 

for (i in 1:length(Sub1$Short_path)) { 
    Pro0[stri_detect_fixed(Path, Sub1$Short_path[i]), Short_path:=Sub1$Short_path[i]] 
} 

使用這種方法，我只需在一秒內將14個較短的路徑名與230k個路徑名相關聯。

這是我用來創建數據集tPro1和Sub1的對應你的那些代碼：

tPro1 <- data.table('Path' = list.files(path = '/usr', full.names = TRUE, recursive = TRUE)) 
Sub1 <- data.table('Short_path' = list.files(path = '/usr', full.names = TRUE)) 

Answer 4

利用模糊匹配，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)