基于膨胀系数的正则表达式分组算法

• 作者: 唐学文 杨正益 王美阳
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 膨胀系数 正则表达式 分组算法 DFA
• 年，卷（期）: 2014,（7）
• 所属期刊栏目: 信息安全
• 页码范围: 129-132
• 页数: 4页
• 分类号: TP393.08
• 字数: 2708字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2014.07.029

摘要

确定性有限自动机（ Deterministic Finite Automata ， DFA）匹配速度远快于非确定性有限状态自动机（ Non-determinis-tic Finite state Automata ， NFA），但大量正则表达式转换为DFA时会引起状态爆炸而占用巨大的存储空间。首先定义膨胀系数（ Expansion Coefficient ， EC）来描述正则表达式的膨胀特性，然后在膨胀系数这一概念基础上，提出一种高效的分组算法---IGA（ Improved Grouping Algorithm ）算法对正则表达式进行有效分组，将容易引起状态爆炸的正则表达式相互隔离，从而节省存储空间。实验结果表明，与原有算法相比，在相同分组数目时IGA算法平均能够减少25％的状态数。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐学文	重庆大学信息与网络管理中心	35	203	8.0	12.0
2	杨正益	重庆大学软件学院	11	76	6.0	8.0
3	王美阳	重庆大学计算机学院	2	8	1.0	2.0