regex - 子序列搜索

Question

我有大量列表(总共 35 MB)，我想搜索子序列:每个术语必须按顺序出现，但不一定连续出现。所以 1, 2, 3 匹配每个

1, 2, 3, 4, 5, 6
1, 2, 2, 3, 3, 3

但不是

6, 5, 4, 3, 2, 1
123, 4, 5, 6, 7

( , 是分隔符，而不是要匹配的字符。)

如果没有在数万或数十万个序列上运行正则表达式(例如 /1, ([^,]+, )*2, ([^,]+, )*3/)，我如何确定哪些序列是匹配的？我可以预处理序列，尽管内存使用需要保持合理(例如，在现有序列大小的恒定因子内)。最长的序列很短，不到 1 KB，因此您可以假设查询也很短。

Answer 1

这让我想起了生物信息学中的序列比对，您尝试将一小段 DNA 与大型数据库进行匹配。不同之处在于您可能使用更大的字母表，以及您对任意长间隙的容忍度增加。

您可能会在查看现有工具和算法(特别是 Smith-Waterman 和 BLAST)时找到一些灵感。