REG-EDPI：一种启发式正则表达式分组算法

"这篇论文研究了面向高效深度包检测的启发式正则表达式分组算法，通过分析正则表达式合并确定型有限自动机（DFA）时的状态爆炸问题，将正则表达式最优分组问题转化为带权无向图的k-最大割问题。文中提出了REG-EDPI算法，采用贪婪策略构建初始解，并通过移除参数进行迭代优化，实验结果显示该算法在合理的时间内能获取更优的分组策略，具有较高的实际应用价值。该研究得到了国家自然科学基金等多个项目的资助，由赵超、王慧强等多位研究人员共同完成。" 在深度包检测（Deep Packet Inspection, DPI）领域，正则表达式被广泛用于规则匹配，以识别和分析网络流量中的特定模式。然而，当大量正则表达式组合在一起时，会引发DFA的状态数量急剧增长，导致性能下降和计算资源浪费，这被称为状态爆炸问题。为了解决这一问题，论文提出了一种新的启发式算法——REG-EDPI。 REG-EDPI算法的核心在于通过两两正则表达式的DFA状态增加数之和来评估合并后的状态复杂性。它首先使用贪婪策略来构建一个初步的正则表达式分组，然后引入移除参数进行迭代优化，以减少状态总数并提高效率。这种策略旨在找到最优的正则表达式分组，使得DFA的状态数量最小化，从而提高深度包检测的效率。 正则表达式分组问题的转化是将原问题抽象成一个带权无向图，其中每个节点代表一个正则表达式，边的权重表示两个正则表达式合并后的状态增加数。k-最大割问题的求解目标是寻找图中一个大小为k的割，使得割掉的边的权重总和最大。通过对这个问题的解决，REG-EDPI算法能够在保证检测精度的同时，有效控制DFA的状态复杂性。 实验证明，与已有的算法相比，REG-EDPI在合理的时间复杂度内能够得到更优的分组结果，这对于实际应用来说具有显著优势，尤其是在处理大规模正则表达式集合时，能够显著提升深度包检测系统的性能和响应速度。 这篇论文提出的启发式正则表达式分组算法REG-EDPI，通过创新性的方法解决了DFA状态爆炸问题，对于提升网络监控和安全防护的效率具有重要的理论和实践意义。它不仅丰富了深度包检测领域的算法设计，也为相关领域的研究提供了新的思路。