算法尽可能快地选择正确的RegEx

Question

Django web框架使用正则表达式来调度传入的请求。
假设应用程序非常庞大，并且有很多正则表达式，比如数百个。

对于任何传入的请求，我如何确定哪些正则表达式尽快匹配？逐个遍历列出的正则表达式是疯狂的。

Answer 1

一个选项是构造一个可以并行匹配所有正则表达式的确定性自动机。一种方法如下：

1. 使用许多标准转换算法之一将每个正则表达式转换为非确定型自动机。
2. 向这些自动机的所有开始状态引入一个新的开始状态，并带有ε-转换。这有效地创建了一个自动机，并行运行所有正则表达式自动机。确保以不同的方式在NFA中标记每个接受状态，以便清楚地了解每个接受状态对应的正则表达式。
3. 使用子集构造，将此NFA简化为DFA。在这个过程中，当把一个状态标记为接受状态时，请记住哪个自动机认为状态为接受状态。
4. 生成DFA的表驱动实现。

现在，每当你收到新邮件时，您可以运行表驱动的这一信息，从而有效地并行运行，并返回其正则表达式，如果有的话，比赛的每一个正则表达式DFA。由于生成的DFA可能非常大，因此在内存中可能会产生大量成本，但匹配任何传入正则表达式的时间与要匹配的字符串大小是线性关系。

Answer 2

如果您对应用程序有控制权，为什么不包含一些元数据来指示要使用的正则表达式的类型？您可以使用该元数据来选择正确的RegEx。

Answer 3

将正则表达式合并为一个，方法是将它们连接在一起|并命名组：（？< 1> regex1的）|（？< 2> regex2）|？（< 3> regex3 ...

测试输入一次，并确定哪个正则表达式通过检查指定的组相匹配

。