有多个初始状态的 DFA

我们已使用 terark.com 进行商业化运营

最近做了一项工作:允许一个 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 做了一些重构,同时也进行了一些优化。

 

 

我们已使用 terark.com 进行商业化运营

作者:
该日志由 csdn-whinah 于2013年11月28日发表在自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 有多个初始状态的 DFA
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。