对四种正则表达式分组算法的评估

在前几篇文章中介绍了Yu算法，IGA算法，Becchi算法和REG_NAGA算法，我们从分组之间DFA状态数是否平衡，是否度量正则表达式间膨胀影响，分组时的度量方式，是否对分组的匹配顺序进行调度四个方面来评估下这几个算法，通过下图来展现：

在前几篇博文中我们可以知道，Yu算法和IGA算法会设定一个阈值，当当前分组中的状态数达到阈值以后会重新建立分组，他们的，而IGA与Yu算法不同的是IGA引入了公式来衡量正则表达式膨胀影响。而Becchi算法和REG_NAGA算法都没有考虑这两个因素，REG_NAGA算法通过遗传算法来达到局部最优解。
通过比较发现,虽然这几个算法对特征模式集构造的 DFA 存储空间进行优化, 但是大多数正则表达式分组算法不能保持分组之间的状态数平衡,而能够保证分 组状态数平衡的算法通常需要在分组时消耗更多的计算量进行分组与正则表达式 间相互影响关系的评估,总的来说,现有正则表达式算法还存在如下不足:
(1) 分组过程所用的时间过长,需要比较大的计算量。
(2) 分组时对于特征模式集中不同结构的正则表达式没有进行区分。
(3) 在分组过程中,有一部分算法不能保持各分组之间状态数的平衡。