背景

正则表达式匹配引擎，需将正则表达式对应的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的执行时间。