regex - 我可以使用交替将多少个正则表达式链接在一起？

Question

我有一些大文件(数百 MB)，我需要搜索数千个 ~20 个字符的唯一字符串。

我发现使用管道交替元字符来匹配正则表达式，如 (string1|string2|string3)大大加快了搜索过程(与一次搜索一个字符串相比)。

这将如何扩展的限制是什么？我可以像这样链接多少个表达式？它会在某个时候引起某种溢出吗？有没有更好的方法来做到这一点？

编辑

为了保持我的问题简短，我没有强调我已经使用这种交替方法实现了代码的事实，我发现它很有帮助:在具有典型数据集的测试用例中，运行时间从87 分钟缩短到 18 秒——290 倍的加速，显然是用 O(n) 而不是 O(n*m)。

我的问题涉及当其他用户将来使用更大的数据集、更大的文件和更多的搜索词运行此代码时，这种方法将如何工作。最初的 O(n*m) 代码是已经使用了 13 年的现有代码，最近有人指出其运行缓慢，因为它操作的基因组相关数据集最近变得更大。

Answer 1

如果您有一个简单的正则表达式，如 (word1|word2|...|wordn)，正则表达式引擎将构建一个状态机，该状态机可以只传递一次输入以查找字符串是否匹配。

旁注:在理论计算机科学中，“正则表达式”的定义方式是单次传递总是足够的。然而，实际的正则表达式实现添加了允许构建正则表达式模式的功能，这些模式不能总是作为单次通过 ( see this example ) 来实现。

同样，对于您的正则表达式模式，引擎几乎肯定会使用单次传递。这可能比多次从内存中读取数据要快……而且几乎肯定比从磁盘多次读取数据快得多。