3.网络流分析

图 | 4 网络流分析

该章介绍multi-string及FA匹配算法，该算法利⽤SIMD进⾏加速。 

multi-string匹配算法

该算法名称为FDR；算法分为两个步骤，如图：

图 | 5 FDR匹配的两个阶段

⾸先采⽤Extended Shift-or Matching算法对已经分解的Str进⾏匹配；对于已经匹配的候选项再交由FA匹配算法进⾏匹配。

Shift-or Matching

shift-or Matching算法是⼀个简单的算法；如图：

图 | 6 经典shift-or matching算法

对于需要匹配的字符串，需要维护两个状态st-mask，及sh-mask(‘c’)；

对于候选的匹配字符串，如果’c’在字符串中，那么sh-mask(‘c’)的bit位除了对应其出现再字符串的位置为0外其他位都为1；

如图6中，匹配字符串为”aphp”,’p’出现在了字符串的第2及4位，那么sh-mask(‘p’)=11110101

st-mask初始状态为11111111

对于新的字符输⼊‘x’： 

st-mask=((st-mask≪1) | sh-mask(‘x’) 

当st-mask的匹配字符串长度对应的bit位为0则表示匹配成功了。

shift-or Matching算法有比较高的运行效率。但同时存在两个缺点：1.只支持单个字符串的匹配；2.不能使⽤SIMD指令进⾏提效。

为了克服这两个缺点，使用算法如下:

Multi-string shift-or matching

为了⽀持多字符串的同时匹配，修改了数据结构。

⾸先，将字符串划分到n个bucket中，每个bucket编号为0-n-1;假设，每个字符串只属于⼀个bucket；

第⼆步，将st-mask及sh-mask扩⼤n倍； 

sh-mask(‘x’)初始化为全1 ;

如果’x’出现在了第n个bucket的第k位，那么sh-mask(‘x’)第k个位置上的第n为置位0；同时对于长度小于最大的字符串长度的bucket，需要增加补充位。

图 | 7 sh-mask示例

此处的第k个位置和shift-or Matching算法的区别，在于此处从右边开始计数；st-mask |= (sh-mask(‘x’) ≪ (k bytes))。如下示例