背景
正则表达式匹配引擎,需将正则表达式对应的NFA(非确定有穷自动机,Non-deterministic finite automaton)转换为DFA(确定有穷自动机,Deterministic finite automaton),然后采用处理速度较快的DFA执行匹配任务。然而,DFA较NFA具有极高的空间复杂度,进而影响了DFA在大规模复杂正则表达式情形下的完美使用。目前有限自动机状态转移采用二维矩阵存储结构,行表示有限制动机状态,列表示跳转字符。但是基于二维矩阵存储结构进行的有限自动机压缩算法,压缩比例较低,有限自动机空间利用率较低。
本文,选取较为合理的“有限自动机状态转移”数据结构,增加了内存空间压缩比例,提高了NFA到DFA转换速度,且具有较高的匹配性能,实现了一种新颖的高性能有限自动机空间压缩算法。
怎么实现的?
本文提出了一种高效的有限自动机空间压缩算法,采用了合理的“有限自动机状态转移”存储数据结构,提高了内存空间利用率,加快了NFA转化为DFA执行速度。系统模块设计分为三部分:NFA空间压缩、优化NFA到DFA转换、DFA空间压缩。
A)NFA空间压缩,用于构造压缩比例较高的“NFA状态转移”存储数据结构。本步骤保持NFA状态数目不变,只针对NFA状态之间的跳转关系做优化。
传统的NFA二维矩阵存储结构,行表示NFA状态,列表示跳转字符。但是,正则表达式中的跳转字符可以分为两类:第一类是单个跳转字符,比如:ab;第二类是跳转字符区间(包含多个连续字符),比如:[a-h]。
基于上述理论,NFA状态跳转边分“单个跳转字符”和“跳转字符区间”两种情况分别存储,其中“跳转字符区间”可以合并为一条存储记录。但是,“无效跳转字符”及“跳转字符区间”无须记录,“NFA状态之间的跳转关系”采用链式列表存储。
然后,将上述的“单个跳转字符”和“跳转字符区间”的存储结构合并到“有序数组列表”,单个跳转字符可能对应多个目的NFA状态。此“有序数组列表”不仅可以缩短“NFA到DFA”转换时间,而且可以提高“基于NFA匹配技术”的执行效率。
基于马尔科夫链原理,NFA中越靠近起始的状态,匹配的概率越高。同时,为了保证较好的压缩率,只对NFA的前三层采用“单个跳转字符”数组表示。当匹配NFA时,此类状态可以直接跳转,无需执行额外的操作,NFA的整体匹配性能接近于“单个跳转字符”数组。
B)优化NFA到DFA转换,用于合并NFA状态之间的跳转关系,进而改善“子集构造法”的性能,优化NFA到DFA转换效率。
NFA到DFA转换过程中,有很大一部分时间用于查询当前跳转字符对应的“活跃NFA状态集”是否已经存在。但是,DFA状态的跳转边往往是有限的,并且存在极大的重复概率。至少大部分情况下正则表达式为BASE64所含的64个常用字符,重复率近似为64/256=25%。
预处理DFA状态包含的“活跃NFA状态集”,多个连续的跳转字符具有相同的“跳转活跃NFA状态集”,只需执行一次“Radix树检索”,极大减少了“Radix树检索次数”,进而缩小了NFA到DFA的执行时间。
C)DFA空间压缩,用于构造压缩比例较高的“DFA状态转移”存储数据结构。本步骤保持DFA状态数目不变,只针对DFA状态之间的跳转关系做优化。
传统的DFA二维矩阵存储结构,行表示DFA状态,列表示跳转字符。但是,DFA的跳转字符可以分为两类:第一类是单个跳转字符跳转到目的DFA状态,并且这个跳转字符与相邻跳转字符目的DFA状态不同;第二类是跳转字符区间(包含多个连续字符)具有相同的目的DFA状态。
基于上述理论,DFA状态跳转边分“单个跳转字符”和“跳转字符区间”两种情况分别存储,其中“跳转字符区间”可以合并为一条存储记录。同时,为了加快DFA匹配速度,“无效跳转字符”及“跳转字符区间”也须记录,“DFA状态之间的跳转关系”采用有序数组列表存储。
同样,基于马尔科夫链原理,DFA中越靠近起始的状态,匹配的概率越高。同时,也为了保证较好的压缩率,只对DFA的前三层采用“单个跳转字符”数组表示。当匹配DFA时,此类状态可以直接跳转,无需执行额外的操作,DFA的整体匹配性能接近于“单个跳转字符”数组。
有哪些实际价值?
1)NFA/DFA空间利用率高:采用合理的数据结构,优化了“有限自动机状态转移”存储结构,压缩了内存空间。
2)NFA转DFA执行时间短:合理压缩合并了NFA状态之间的跳转关系,提高了“子集构造法”性能,缩短了NFA转换为DFA的执行时间。