正则表达式方程组的最小解

作者：韩光辉; 曾诚

来源：电脑与信息技术, 2011, (05): 1-4.

DOI：10.19414/j.cnki.1005-1228.2011.05.001

• 正则表达式方程组
• 最小解
• 求解算法
• 时间复杂度 system of regular expression equations
• minimal solution
• solving algorithm
• time complexity

网络安全检测中,正则表达式匹配是深度包检测的主要手段,匹配算法则是其关键技术。目前,正则表达式匹配算法可以大体分为转换压缩、状态压缩和字母表压缩三类。文章讨论正则表达式方程组最小解及其求解算法,证明了正则表达式方程组的最小解的存在性和基于Gauss消元法的求解算法的正确性,给出了最小解的构造,分析了求解算法的时间复杂度,为规则压缩奠定了理论基础。

• 单位
  武汉大学; 软件工程国家重点实验室