基于状态约束的大规模正则表达式匹配算法
2013-08-07贺炜郭云飞扈红超
贺炜,郭云飞,扈红超
(国家数字交换系统工程技术研究中心,河南 郑州 450002)
1 引言
近年来,作为网络信息过滤、文字处理等应用中的关键组成部分,正则表达式匹配技术得到了快速发展。正则表达式匹配技术作为实现大规模模式匹配的主要手段,广泛应用于二进制序列分析、扩展标记语言处理及入侵检测系统中[1,2]。目前正则表达式匹配主要通过不确定性有限自动机(NFA,nondeterministic finite automata)以及确定性有限自动机(DFA, deterministic finite automata)来实现。
假设需要对k(k>1)条正则表达式完成匹配,其中,第i(i=1,2,…,k )条正则表达式中包含ni个字符。将k条正则表达式通过McNaughton-Yamada构造法转化为NFA后,会产生个NFA状态[3],每输入一个字符,都需要对这些状态进行并行检测。上述特性导致基于NFA的正则表达式匹配在处理过程中的时间复杂度较高。虽然NFA能够通过硬件结构的加速来提高处理速率,但硬件加速方案通常缺少灵活性并且很难做到实时更新[4]。
针对NFA的缺点,另外一种解决方案是将NFA转化为DFA。通过将NFA中各个状态之间所有的有效转移存储在状态转移表(STT, state transition table)中,DFA可在硬件或软件平台中得到较好的实现。但是,基于DFA的正则表达式匹配也存在一些问题[5]。
1) 状态数爆炸:在最坏情况下,对于有n个状态的NFA,其最小等价DFA的状态数将达到O(2n)数量级。
2) 压缩时间代价:尽管STT可以通过消除相似状态冗余来压缩,但是现有压缩算法的时间复杂度至少为O(n2)。
NFA的空间特性较好,时间特性较差,而DFA相反,两者都不能很好地满足实际网络应用的需求。因此,快速高效是大规模正则表达式匹配的首要目标。……
