Django 网络框架使用正则表达式来分派(dispatch)传入请求。
假设应用程序很大并且有很多正则表达式,比如数百个。
对于任何传入的请求,我如何才能尽快确定匹配哪些正则表达式?一个一个地遍历列出的正则表达式是疯狂的。
最佳答案
一种选择是构造一个可以并行匹配所有正则表达式的确定性自动机。一种方法如下:
- 使用多种标准转换算法之一将每个正则表达式转换为不确定自动机。
- 向这些自动机的所有开始状态引入一个带有 ε 转换的新开始状态。这有效地创建了一个并行运行所有正则表达式自动机的自动机。确保以不同方式标记 NFA 中的每个接受状态,以便清楚每个接受状态对应的正则表达式。
- 使用子集构造,将此 NFA 简化为 DFA。在此过程中,当将状态标记为接受状态时,请记住哪个自动机认为该状态是接受状态。
- 生成 DFA 的表驱动实现。
现在,无论何时您收到一条新消息,您都可以在该消息上运行表驱动的 DFA,它有效地并行运行每个正则表达式并返回匹配的正则表达式(如果有)。这可能会占用大量内存,因为生成的 DFA 可能非常大,但匹配任何传入正则表达式的时间将与要匹配的字符串的大小成线性关系。
关于regex - 尽可能快地从众多正则表达式中选择正确正则表达式的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6618453/