正则表达式匹配算法（提升匹配速度类）总结

一点小tips：

维基百科关于FSM、DFA、NFA的介绍
有限状态机（Finite State Machine：FSM）又称有限状态自动机或简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。
在计算理论中，确定有限状态自动机或确定有限自动机（英：deterministic finite automaton；简称：DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态有可能就是先前那个状态）。
在计算理论中，非确定有限状态自动机或非确定有限自动机(NFA)是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机(DFA)，它的下一个可能状态是唯一确定的。尽管 DFA 和 NFA 有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定 NFA，都可以构造一个等价的 DFA，反之亦然: 通过使用幂集构造。两种类型的自动机只识别正则语言。非确定有限自动机有时被称为有限类型的子移位(subshift)。非确定有限状态自动机可推广为概率自动机，它为每个状态转移指派概率。

基于推测的方法

SPPM 2011

基于枚举的方法

Efficient Parallelization of Regular Expression Matching for Deep Inspection (2016)

算法依据

随着字符串向后匹配，激活状态会越来越少(状态汇聚)
相同的激活状态可以合并

思路

与MapReduce模型类似，程序可以分为3个步骤：映射、匹配和还原
- 从所有起始状态的集合开始，每个线程根据每个数据块的输入独立计算出子结果，然后将所有线程的子结果依次加入进行还原，得到最终的匹配结果
设计“中间状态单元“（MSU）的数据结构，以比特形式记录各数据块的匹配历史信息

算法细节

Mapping(1-7): n是线程数

对每个线程的MSU进行初始化
- 第一个线程的MSU只有一个就是DFA中state0 对应的MSU
- 剩下线程的开始状态是根据全部DFA状态构建的MSU

Matching(8-12):

每个线程的字符逐个匹配
- 对于第一个线程正常进行状态转移
- 对于剩下的线程来说
  - 枚举MSU，进行状态转移，MSU.id变为转移后的值
  - 合并转移后id相同的MSU：MSU.mapping变为id相同MSU的mapping的并集(如下图)

Reduceing(16-25): 如下图

对每个线程的结果进行合并：
- 第一个线程的最终状态就是线程1最终的MSU，将其设置为MSU_final
- 对剩下线程来说，枚举MSU，如果MSU.mapping && MSU_final.id 不为0，则说明上一个线程的最终状态最终将转移到该MSU
- 更新MSU_final.id为新的id
循环到最后的时候就是最终到达的状态

Combining SIMD and Many/Multi-core Parallelism for Finite State Machines with Enumerative Speculation(2017) 基于规则+枚举

摘要及贡献

提出了枚举式推测算法，该方法不是像投机执行中那样对单一状态进行投机，也不是像枚举执行中那样对所有可能的状态进行枚举，而是对几种可能状态的转换进行投机，减少了投机方法的预测开销和枚举方法中大量的冗余工作。在枚举式猜测中，一个简单的回溯方法产生一组猜测状态，以实现高猜测成功率。
1）FSM的冗余工作和并行性（推测成功率）之间有一个权衡；
2）在多个推测状态下，推测成功率对块大小不敏感。