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

Minimal Solution of System of Regular Expression Equations

作　　者：韩光辉[1] 曾诚[2] 

机构地区：[1]武汉商业服务学院信息工程系,湖北武汉430056 [2]武汉大学软件工程国家重点实验室,湖北武汉430072

出　　处：《电脑与信息技术》2011年第5期1-4,共4页Computer and Information Technology

基　　金：国家自然科学基金(项目编号:60873083);湖北省教育科学"十一五"规划课题(项目编号:2010B338)

摘　　要：网络安全检测中,正则表达式匹配是深度包检测的主要手段,匹配算法则是其关键技术。目前,正则表达式匹配算法可以大体分为转换压缩、状态压缩和字母表压缩三类。文章讨论正则表达式方程组最小解及其求解算法,证明了正则表达式方程组的最小解的存在性和基于Gauss消元法的求解算法的正确性,给出了最小解的构造,分析了求解算法的时间复杂度,为规则压缩奠定了理论基础。tkegular expression matching algorithm for deep packet inspection is a main means and a key technology in network security inspection. Large-scale regular expression matching algorithms can be divided into conversions merging, state merging and alphabet merging at present. For theoretical foundation of rule merging, in this paper, minimal solution of system of regular expression equations and its solving algorithm are discussed. Existence of the minimal solution and correctness of the solving algorithm based on Gaussian elimination are proved, structure of the minimal solution is described. Time complexity of the solving algorithm is analyzed.

关 键 词：正则表达式方程组 最小解 求解算法 时间复杂度 

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构]