有多个初始状态的 DFA

时间：2022-09-05 00:22:32

请关注我们的技术创业项目 Terark，领先的数据技术提供商


最近做了一项工作：允许一个 DFA 有多个起始状态（可以称作根: root）。引入这个概念有很多好处，主要体现在 DFA Union 中，这个操作通过 NFA 到 DFA 的转化来完成，算法思想很简单：

创建一个 NFA，该 NFA 只有初始状态是非确定 (non-DFA) 状态：初始状态只有 ε 转移，这些 ε 转移指向所有要被 Union 的 DFA 的初始状态，然后将该 NFA 转化为 DFA。

因为 NFA 转化 DFA 是 NSpace 的，虽然很多数情况下只有线性复杂度，我们仍然希望尽可能减小这个复杂度。


对于多正则表达式匹配（Multiple Regular Expression Matching）的 DFA

在创建多正则表达式匹配的 DFA 的过程中，就有一个 DFA 的 Union 操作，在这个过程中，如果状态膨胀失去控制，需要使用某种方式对正则表达式集合进行分组，以便抑制这种状态膨胀。分组后会生成多个 DFA ，但是为了应用程序接口方便统一，将这多个 DFA 揉进一个 DFA 对象，每个分组的 DFA 就需要一个不同的初始状态(根)。

改善 DFA Union 的性能

有相同 Tail 的多个 DFA

如果用 adfa_build 分别创建了多个不同的 ADFA(Acyclic DFA, 无环自动机)，在随后的某个时间点，想将这多个 ADFA 进行合并，仍然是 DFA 的 Union 操作，这种情况下 NFA 转 DFA 过程中的状态膨胀总是线性的，虽然如此，NFA 转 DFA 的过程中仍然需要大量内存。

虽然之前我也曾想过 DFA 包含多个初始状态(根)的可能性，但一直没有深入思考，这次经过仔细思考，发现：对于(所有的) DFA 最小化算法，从理论上讲，完全没有必要限制为单根 DFA，不管有多少个根，算法都能正常工作！唯一需要注意的是，最小化前后的根，在某些应用中需要一一对应起来。

最小化之前的多根 DFA 可以完全是独立的，唯一的要求是所有 DFA 的状态 ID 属于同一个 ID 空间，这很简单，工程上用同一个 DFA 对象来表达即可，对于 分离的多个 DFA 对象，只需要实现一个 DFA 包装器，将多个分离的 DFA 的状态 ID 重新映射即可。

如此，就完成了执行多根 DFA 最小化的所有准备。最小化完成之后，这些多个 DFA 会共享一些相同的尾部，一般情况下，头部不会共享；不过极端情况下，例如 DFA1 是 DFA2 的子集，那么，从 DFA2 的根就能到达 DFA1 的根，此时整个 DFA1 就被完全共享了。

执行 DFA Union

所有的尾部都被最小化了，然后再用 NFA 转化 DFA 的方式执行最小化，这样，大大减小了 NFA 转 DFA 的时间和内存消耗。


动态 DFA 匹配多个正则表达式

细节可参考：多正则表达式匹配 (Multiple Regular Expression Matching) 中的动态 DFA 算法

主要有两点：

  1. 多个子 DFA 在 regex_build 时使用最小化算法得到一个包含多个根，一个尾的 DFA
  2. 动态 DFA 是多个子 DFA 的并集，因为并集的完全 DFA 无法构造出来（状态的指数爆炸），动态地从DFA并集的NFA构造并集的部分DFA
  3. 用正则表达式集合的并集的动态DFA搜索到具体匹配的正则表表达式ID之后，从该ID的根出发，去抽取括号部分

实现

在实现这个概念的过程中，对我的 adfa_minimize 做了一些重构，同时也进行了一些优化。



标签：

相关文章