背景

正则表达式匹配引擎的实现方式分为NFA（非确定有穷自动机，Non-deterministic finite automaton）和DFA（确定有穷自动机，Deterministic finite automaton）两类。由于NFA的状态数量与正则串长度成正比，因此大量开源库采用了NFA的执行方式，比如JDK regex、joni。也有一部分正则库在NFA翻译为DFA的理论基础上，采用了处理速度较快的DFA执行匹配任务,比如re2、hyperscan。由于DFA较NFA具有极高的空间复杂度，进而影响了DFA在复杂正则表达式情形下的完美使用，大部分DFA正则引擎均有错误回退NFA的自我保护机制。并且，DFA的状态跳转采用的是字节格式，由于存在函数调用和字符集转换，正则表达式连续字符高频出现时，DFA反而比优化的NFA执行效率低。

本文，针对高频的连续字符构建了一种较优的NFA，同时选取较为合理的“有限自动机状态转移”数据结构，增加了内存空间压缩比例，提高了NFA到DFA转换速度，且具有较高的匹配性能，实现了一种高性能单模正则表达式引擎。

怎么实现的？

本文提出了一种高性能单模正则表达式引擎，采用较优的NFA，提升了高频连续字符的匹配效率。采用了合理的“有限自动机状态转移”存储数据结构，提高了内存空间利用率，加快了NFA转化为DFA执行速度。系统模块设计分为四部分：初始NFA构造、NFA空间压缩、优化NFA到DFA转换、DFA空间压缩。

   A）初始NFA构造，用于构造执行效率较快的“Init-NFA”。

    采用解析模式遍历正则串的字符构建“Init-NFA”，将连续字符串则构造为同一个节点SliceNode，并且在此构造过程中无需将字符转换为字节，由此避免了不必要的状态跳转，因此NFA执行模式以此“初始NFA”为基础执行。

   B）NFA空间压缩，用于构造压缩比例较高的“NFA状态转移”存储数据结构。本步骤保持NFA状态数目不变，只针对NFA状态之间的跳转关系做优化。

现将“Init-NFA”中的各个跳转的字符集转为字节，依次可以限定状态数组的最大长度。经过此步骤连续字符串对应的SliceNode会拆分为多个NFA节点。

传统的NFA二维矩阵存储结构，行表示NFA状态，列表示跳转字符。但是，正则表达式中的跳转字符可以分为两类：第一类是单个跳转字符，比如：ab；第二类是跳转字符区间（包含多个连续字符），比如：[a-h]。

基于上述理论，NFA状态跳转边分“单个跳转字符”和“跳转字符区间”两种情况分别存储，其中“跳转字符区间”可以合并为一条存储记录。但是，“无效跳转字符”及“无效跳转字符区间”无须记录，“NFA状态之间的跳转关系”采用链式列表存储。

然后，将上述的“单个跳转字符”和“跳转字符区间”的存储结构合并到“有序数组列表”，单个跳转字符可能对应多个目的NFA状态。此“有序数组列表”不仅可以缩短“NFA到DFA”转换时间，而且可以提高“基于NFA匹配技术”的执行效率。

基于马尔科夫链原理，NFA中越靠近起始的状态，匹配的概率越高。同时，为了保证较好的压缩率，只对NFA的前三层采用“单个跳转字符”数组表示。当匹配NFA时，此类状态可以直接跳转，无需执行额外的操作，NFA的整体匹配性能接近于“单个跳转字符”数组。

   C）优化NFA到DFA转换，用于合并NFA状态之间的跳转关系，进而改善“子集构造法”的性能，优化NFA到DFA转换效率。

NFA到DFA转换过程中，有很大一部分时间用于查询当前跳转字符对应的“活跃NFA状态集”是否已经存在。但是，DFA状态的跳转边往往是有限的，并且存在极大的重复概率。至少大部分情况下正则表达式为BASE64所含的64个常用字符，重复率近似为64/256=25%。

预处理DFA状态包含的“活跃NFA状态集”，多个连续的跳转字符具有相同的“跳转活跃NFA状态集”，只需执行一次“Radix树检索”，极大减少了“Radix树检索次数”，进而缩小了NFA到DFA的执行时间。

   D）DFA空间压缩，用于构造压缩比例较高的“DFA状态转移”存储数据结构。本步骤保持DFA状态数目不变，只针对DFA状态之间的跳转关系做优化。

传统的DFA二维矩阵存储结构，行表示DFA状态，列表示跳转字符。但是，DFA的跳转字符可以分为两类：第一类是单个跳转字符跳转到目的DFA状态，并且这个跳转字符与相邻跳转字符目的DFA状态不同；第二类是跳转字符区间（包含多个连续字符）具有相同的目的DFA状态。

基于上述理论，DFA状态跳转边分“单个跳转字符”和“跳转字符区间”两种情况分别存储，其中“跳转字符区间”可以合并为一条存储记录。同时，为了加快DFA匹配速度，“无效跳转字符”及“无效跳转字符区间”也须记录，“DFA状态之间的跳转关系”采用有序数组列表存储。

同样，基于马尔科夫链原理，DFA中越靠近起始的状态，匹配的概率越高。同时，也为了保证较好的压缩率，只对DFA的前三层采用“单个跳转字符”数组表示。当匹配DFA时，此类状态可以直接跳转，无需执行额外的操作，DFA的整体匹配性能接近于“单个跳转字符”数组。                                                       

有哪些实际价值？

1）NFA执行效率高：将连续字符串转换为SliceNode，保持了原有字符集，较少了NFA状态数量，避免了冗余的函数调用及字符集转换，提升了执行效率。

2）NFA/DFA空间利用率高：采用合理的数据结构，优化了“有限自动机状态转移”存储结构，压缩了内存空间。

3）NFA转DFA执行时间短：合理压缩合并了NFA状态之间的跳转关系，提高了“子集构造法”性能，缩短了NFA转换为DFA的执行时间。