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

来源：计算机工程与应用杂志2018年第20期北京时间：

作者：付 哲1，2，李 军2

单位：1.清华大学 自动化系，北京 100084 ；2.清华大学 信息技术研究院，北京 100084

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

关键词：正则表达式匹配,有穷自动机,算法,评测