正则表达式匹配引擎性能分析

计算机与现代化 ›› 2011, Vol. 7 ›› Issue (7): 105-107,.doi:

正则表达式匹配引擎性能分析

邓凯元1，姜磊2

1．北京信息科技大学光电信息与通信工程学院，北京 100101； 2．中国科学院计算技术研究所，北京 100190

收稿日期:2011-05-09 修回日期:1900-01-01 出版日期:2011-07-15 发布日期:2011-07-15

Performance Analysis of Different Regular Expressions Matching Engines

DENG Kai-yuan1, JIANG Lei2

1.School of Photoelectric Information and Communication Engineering, Beijing Information Science and Technology University, Beijing 100101, China；2.Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

Received:2011-05-09 Revised:1900-01-01 Online:2011-07-15 Published:2011-07-15

摘要/Abstract

摘要： 正则表达式具有强大的描述能力，在计算机领域，正则表达式匹配技术应用十分广泛。目前，已经有多个正则表达式匹配引擎，在实际应用中，对于不同的匹配规则集和正则语法，不同的匹配引擎会有不同的性能表现。本文通过对PCRE、Greta、Boost、RE2四种常用正则表达式匹配引擎的性能测试，给出在不用的正则语法情况下的匹配速度，并深入分析不同坏境下适用的正则表达式匹配引擎。对实际系统设计中正则表达式库的选择有指导意义。

关键词: 正则表达式, PCRE, 模式匹配, NFA, DFA

Abstract: With the remarkable descriptive power, regular expression matching is in wide use in the field of computer science. Dozens of regular expression matching engines has been developed. In the practical applications, for different rule sets and grammars, these engines exhibit different performance. By giving detailed performance experiments of four regular expression libraries, PCRE, Greta, Boost and RE2, this paper shows different matching speeds of these four engines. Further, it gives how to select proper regular expression engines in various environments. And the experiment results and analysis can serve as guideline in the future system design.

Key words: regular expression, PCRE, pattern matching, NFA, DFA

邓凯元姜磊. 正则表达式匹配引擎性能分析[J]. 计算机与现代化, 2011, 7(7): 105-107,.

DENG Kai-yuan;JIANG Lei. Performance Analysis of Different Regular Expressions Matching Engines[J]. Computer and Modernization, 2011, 7(7): 105-107,.

[1]	主令恒1, 2, 顾丹鹏1, 2, 唐松强1, 2, 陈肖勇1, 2. 一种多层级二分图最大匹配问题的快速算法[J]. 计算机与现代化, 2024, 0(06): 59-63.
[2]	梁珺秀,许建秋. 基于时空标签轨迹的范围模式匹配查询[J]. 计算机与现代化, 2018, 0(08): 79-.
[3]	夏琨1，丁波1，刘俊1，刘子豪1，林亮成2. 基于内容分析的网络协议指纹识别[J]. 计算机与现代化, 2018, 0(05): 121-.
[4]	张春，袁天宁. 针对动车组全生命周期集成管理的多源异构数据融合框架设计[J]. 计算机与现代化, 2017, 0(10): 36-41.
[5]	陈冲,蒋夏军. 一种支持通配符查询的XML模式匹配算法[J]. 计算机与现代化, 2016, 0(4): 65-73.
[6]	唐炼，王小龙. 基于模式匹配的无线网络安全配置核查工具[J]. 计算机与现代化, 2015, 0(10): 98-102.
[7]	王美阳1，唐学文2，杨正益3. 基于膨胀系数的正则表达式分组算法[J]. 计算机与现代化, 2014, 0(7): 129-132.
[8]	张婧婧;李勇伟;达新民. 基于16位单片机语音识别技术的应用与研究[J]. 计算机与现代化, 2012, 203(7): 176-178.
[9]	周冬初;鞠凤娟;郭东珲 . 基于Struts2框架校验数据及整合正则表达式的实现方法[J]. 计算机与现代化, 2011, 1(1): 85-3.
[10]	敖小玲黄晋. Hibernate缓存机制研究与应用[J]. 计算机与现代化, 2010, 1(9): 68-72.
[11]	常捷. 利用CLR实现SQL Server 2005复杂字符串格式的验证[J]. 计算机与现代化, 2010, 1(10): 186-188.
[12]	苏秀芝;楼新远. 正则表达式与XML配置文件相结合的数据提取[J]. 计算机与现代化, 2009, 169(9): 30-31.
[13]	孙勤红;朱颖文. 正则表达式在计算机类教材知识点提取的应用[J]. 计算机与现代化, 2009, 1(7): 111-112,.