高性能正则表达式匹配算法综述

• 作者: 付哲 李军
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 正则表达式匹配 有穷自动机 算法 评测
• 年，卷（期）: 2018,（20）
• 所属期刊栏目: 热点与综述
• 页码范围: 1-13
• 页数: 13页
• 分类号: TP393
• 字数: 12782字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1808-0339

摘要

深度检测在维护网络安全、保证服务质量等方面扮演着重要的角色.正则表达式匹配算法作为高性能深度检测的核心技术,具有重要的研究价值和实践意义.随着网络流量不断增长、规则数目持续增多以及网络结构日趋灵活和动态,现有的正则表达式匹配算法面临着匹配速度、内存占用和更新能力等多方面的挑战.介绍了正则表达式匹配算法的研究背景,从空间压缩、匹配加速、新型自动机设计以及规则拆分和分组四个角度入手,分类总结了学术界具有影响力的研究成果.通过基于真实网络流量的评测,比较了几种经典匹配算法在不同规则集上的匹配速度、内存占用和预处理时间等性能指标,并给出了不同需求场景下高效正则表达式匹配算法的选择建议,归纳了高性能正则表达式匹配算法的下一步发展方向.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李军	清华大学信息技术研究院	43	353	11.0	18.0
2	付哲	清华大学自动化系	1	19	1.0	1.0