如何高效基于子串过滤任意字符串集合？

核心问题 #

我的核心问题是如何针对任意子串集合过滤任意字符串集合。

具体场景 #

我拥有大量包含UUID的文件名列表，需要从中过滤掉指定UUID列表中的条目。数据集规模从n=10到1,000,000不等，匹配率覆盖0%-100%。

现有方法及性能问题 #

我当前采用的朴素方法如下：将待过滤的UUID用|拼接成单个正则表达式，使用stringr::str_detect检测每个字符串是否匹配，进而过滤。该方法在小数据量下速度较快，但数据量增大后性能急剧恶化。

代码实现 #

# 创建用于抽样的UUID池
uuid_list <- uuid::UUIDgenerate(n = 1e5)

filter_from_string <- function(n) {
  
  # 抽取n个UUID作为目标数据集
  uuid_population <- sample(uuid_list, n)
  
  # 生成包含UUID的长字符串（模拟文件名）
  data_strings <- 
    paste0(
      "Here_are_some_strings_with_associated_UUIDs_",
      uuid_population,
      "_and_additional_metadata.json"
    )
  
  # 抽取10%的UUID作为待过滤的目标子串
  uuid_sample <- sample(uuid_population, n/10)
  
  # 拼接正则表达式："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

# 转换为毫秒单位查看结果
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

# 查看相对耗时
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

测试显示，数据量每扩大10倍，耗时增长远超过10倍，n=10000时耗时是n=10的数千倍。

优化与疑问 #

针对该特定场景，我已找到优化方案：提取字符串中的UUID后进行精确匹配。但我好奇当无明显模式可利用时，如何处理任意字符串与子串的过滤问题。

内容的提问来源于stack exchange，提问作者Brian