我的一般性问题是如何针对任意可能的子字符串集过滤任意字符串集。

我的特殊问题是，我有一长串包含UUID的文件名，还有一个我想从中过滤掉的其他UUID的列表。我的数据集在长度和最终命中匹配的比例方面可能会有所不同，从n = 10到1，000，000，命中率从0%到100%。我不认为匹配率是影响我的方法性能的一个重要因素，但我知道大小确实很重要。
下面是我的天真方法。从本质上讲，从UUID向量开始，我用|将它们连接在一起，形成一个长正则表达式，并针对它测试原始数据的每个成员。这对于小数据来说非常快，但很快就会失控。

设置：

# create a master population to choose from
uuid_list <- uuid::UUIDgenerate(n = 1e5)

filter_from_string <- function(n) {
  
  # choose a representative population
  uuid_population <- sample(uuid_list, n)
  
  # generate the longer strings
  data_strings <- 
    paste0(
      "Here_are_some_strings_with_associated_UUIDs_",
      uuid_population,
      "_and_additional_metadata.json"
    )
  
  # generate a small sample to check against
  uuid_sample <- sample(uuid_population, n/10)
  
  # check against a single long regex that looks like:
  #   "uuid1|uuid2|uuid3|..."
  filter_index <- 
    stringr::str_detect(
      data_strings,
      paste(uuid_sample, collapse = "|")
    )
  
  data_strings[!filter_index]
}

测试：

x <- 
  microbenchmark::microbenchmark(
    "n=10" = filter_from_string(10),
    "n=100" = filter_from_string(100),
    "n=1000" = filter_from_string(1000),
    "n=10000" = filter_from_string(10000),
    times = 10
  )
#> Warning in microbenchmark::microbenchmark(`n=10` = filter_from_string(10), :
#> less accurate nanosecond times to avoid potential integer overflows

# milliseconds
summary(x, "ms")[c("expr", "mean", "median")]
#>      expr         mean       median
#> 1    n=10    0.4201393    0.0713195
#> 2   n=100    1.4376527    0.4230585
#> 3  n=1000   25.4073679   25.8098075
#> 4 n=10000 2340.1810916 2313.1806605

# relative time
summary(x, "relative")[c("expr", "mean", "median")]
#>      expr        mean       median
#> 1    n=10    1.000000     1.000000
#> 2   n=100    3.421848     5.931877
#> 3  n=1000   60.473676   361.889911
#> 4 n=10000 5570.012354 32434.056051

创建于2023-05-03带有reprex v2.0.2
正如您所看到的，性能远远超过每步10倍。
我有一个修复如何在我的特定用例中加速它。我可以从字符串中提取UUID，因为它是一个已知的模式，然后对样本进行精确的相等匹配。我将在下面的答案中发布这个问题，但是我很好奇当没有明显的模式可以使用时该怎么办，而是任何字符串和可能的子字符串的种群。