| 正则表达式方程组的最小解 |
| |
| 引用本文： | 韩光辉,曾诚. 正则表达式方程组的最小解[J]. 电脑与信息技术, 2011, 19(5): 1-4 |
| |
| 作者姓名： | 韩光辉 曾诚 |
| |
| 作者单位： | 1. 武汉商业服务学院信息工程系,湖北武汉,430056
2. 武汉大学软件工程国家重点实验室,湖北武汉,430072 |
| |
| 基金项目： | 国家自然科学基金，湖北省教育科学“十一五”规划课题 |
| |
| 摘 要： | 网络安全检测中，正则表达式匹配是深度包检测的主要手段，匹配算法则是其关键技术。目前，正则表达式匹配算法可以大体分为转换压缩、状态压缩和字母表压缩三类。文章讨论正则表达式方程组最小解及其求解算法，证明了正则表达式方程组的最小解的存在性和基于Gauss消元法的求解算法的正确性，给出了最小解的构造，分析了求解算法的时间复杂度...
|
| 关 键 词： | 正则表达式方程组 最小解 求解算法 时间复杂度 |
Minimal Solution of System of Regular Expression Equations |
| |
| HAN Guang-hui,ZENG Cheng. Minimal Solution of System of Regular Expression Equations[J]. Computer and Information Technology, 2011, 19(5): 1-4 |
| |
| Authors: | HAN Guang-hui ZENG Cheng |
| |
| Affiliation: | HAN Guang-hui1,ZENG Cheng2(1.Information Engineering Department,Wuhan Commercial Service College,Wuhan 430056,China,2.State Key Laboratory of Software Engineering,Wuhan University,Wuhan 430072,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | system of regular expression equations minimal solution solving algorithm time complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
