SBOM算法的全称是Set Backward Oracle Matching，是一种基于子串的，使用了Factor Oracle自动机的，字符串多模匹配算法。因为这种算法的资料比较少，所以这里详细的介绍一下。

老规矩，代码实现直接跳转至最后一章。

1. 基于子串

举个简单的例子，

0	1	2	3	4	5	6	7	8	9	10	11
A	B	C	D	F	F	G	H	I	J	K	L
F	G	F	A	E	F	G

当前已经匹配了的内容串部分是FG，称之为u。不匹配的字符是F，称之为σ。我们认为既然在σ处匹配失败了，所以σu就不再是模式串的子串了。更进一步的，模式串在内容串中任意匹配区域，都不会出现σu。所以，我们就可以移动模式串越过σ的位置，像下面这样。

0	1	2	3	4	5	6	7	8	9	10	11
A	B	C	D	F	F	G	H	I	J	K	L
					F	G	F	A	E	F	G

但可以看出，这种简陋的规则是存在漏洞的，可能会遗漏部分匹配结果。所以，我们需要做一些改进。

2. Factor Oracle自动机

因为上一节中，我们发现那种基于原理的，简陋的匹配规则是存在漏洞的。所以为了解决，我们就可以使用Factor Oracle自动机。跟Aho-Corasick算法使用的自动机类似，Factor Oracle自动机也是基于Tire Tree的。用模式串announce来举例子，先反序构造其Tire Tree状态转移图:

然后先不介绍Factor Oracle自动机的构造方法，看一下最终的状态转移图:

我们发现相较于最初的Tire Tree，多了一些节点间的跳转路径。那这些路径的构造，就是构造Factor Oracle自动机的核心。其构造规则大致是这样的:

2.1 前置定义

1) 如果状态节点m，可以通过输入值α，转移到状态节点n，那P(n)=α
2) 对于每个状态n，将它与另一个状态m(m<n)关联，称m为n的供给状态，并用S(n)=m表示，其中的S称为供给函数。
3) S(0)=𝚹

需要注意的是，𝚹无实际意义，仅作为标记。同时，供给函数S并不反映在状态转移图上。

2.2 构造步骤

从状态节点1开始，逐个检查直至最后一个状态节点。假设已经检查过状态节点i-1，并且开始检查状态节点i，这时就沿着状态节点i-1的供给函数开始回溯。具体的做法是，先把变量k初始化为S(i-1)，然后执行下面的步骤:

step1: 如果k=𝚹，那么S(i)=0，停止执行
step2: 如果k!=𝚹，并且状态k不存在P(i)转移，那么构造从状态k到状态i的转移路径，转移路径的标号为P(i)。然后k=S(k)，并跳转至step1
step2: 如果k!=𝚹，并且状态k存在P(i)转移，目的状态为j，那么S(i)=j，停止执行

2.3 案例推演

还是用模式串announce举例子，其每一步的推演大致是这样的：

i=1, P(i)=e, k=S(0)=𝚹
step1: S(1)=0

i=2, P(i)=c, k=S(1)=0
step2: build 0-c->2, k=S(0)=𝚹
step1: S(2)=0

i=3, P(i)=n, k=S(2)=0
step2: build 0-n->3, k=S(0)=𝚹
step1: S(3)=0

i=4, P(i)=u, k=S(3)=0
step2: build 0-u->4, k=S(0)=𝚹
step1: S(4)=0

i=5, P(i)=o, k=S(4)=0
step2: build 0-o->5, k=S(0)=𝚹
step1: S(5)=0

i=6, P(i)=n, k=S(5)=0
step3: j=k-P(i)->=3, S(6)=3

i=7, P(i)=n, k=S(6)=3
step2: build 3-n->7, k=S(3)=0
step3: j=k-P(i)->=3, S(7)=3

i=8, P(i)=a, k=S(7)=3
step2: build 3-a->8, k=S(3)=0
step2: build 0-a->8, k=S(0)=𝚹
step1: S(8)=0

3. SBOM算法

因为需要使用Factor Oracle自动机，所以SBOM算法的构造、使用过程，主要分成下面三步。

3.1 构造Factor Oracle自动机

SBOM算法中，对于Factor Oracle自动机的使用有些特殊。并非是使用整个模式串来构造，而是根据最短的那个模式串的长度，剪裁得到每个模式串的前缀，用来构造自动机。以模式串announce、annual、annually举例子，最短的模式串是annual，长度为6。所以截取每个模式串得到的前缀就是announ、annual。相应的，先构造其Tire Tree，得到的状态转化图是这样:

然后再进一步，根据上一节中介绍的构造逻辑，得到最终的Factor Oracle自动机，其状态转化图是这样:

3.2 先期匹配

Factor Oracle自动机构造好后，我们就可以进行匹配操作了。其匹配跳转规则，和基于子串的匹配逻辑基本一致。用内容串CPM_annual_conference_announce举例子:

首先将长度为6(最短模式串的长度)的搜索窗口，最左侧和内容串的最左侧对齐。

C	P	M	_	a	n	n	u	a	l	_	c	o	n	f	e	r	e	n	c	e	_	a	n	n	o	u	n	c	e
*	*	*	*	*	*

然后从窗口的最右侧开始，依次取内容串中的字符输入到自动机中。直至字母_，自动机状态转移失败。于是我们移动窗口，越过字母_的位置。

C	P	M	_	a	n	n	u	a	l	_	c	o	n	f	e	r	e	n	c	e	_	a	n	n	o	u	n	c	e
				*	*	*	*	*	*

再次从右侧开始输入字符，直至最左侧的字符a输入结束，自动机状态跳转正常，那么表示在此处找到了其中一个可能的匹配结果，并标记下此处位置为ω(0)。标记结束后，将窗口右移一位。

C	P	M	_	a	n	n	u	a	l	_	c	o	n	f	e	r	e	n	c	e	_	a	n	n	o	u	n	c	e
					*	*	*	*	*	*

再次从右侧开始输入字符，直至字母_，自动机状态转移失败。于是我们移动窗口，越过字母_的位置。

C	P	M	_	a	n	n	u	a	l	_	c	o	n	f	e	r	e	n	c	e	_	a	n	n	o	u	n	c	e
											*	*	*	*	*	*

再次从右侧开始输入字符，直至字母r，自动机状态转移失败。于是我们移动窗口，越过字母r的位置。

C	P	M	_	a	n	n	u	a	l	_	c	o	n	f	e	r	e	n	c	e	_	a	n	n	o	u	n	c	e
																	*	*	*	*	*	*

再次从右侧开始输入字符，直至字母_，自动机状态转移失败。于是我们移动窗口，越过字母_的位置。

C	P	M	_	a	n	n	u	a	l	_	c	o	n	f	e	r	e	n	c	e	_	a	n	n	o	u	n	c	e
																						*	*	*	*	*	*

再次从右侧开始输入字符，直至最左侧的字符a输入结束，自动机状态跳转正常，那么表示在此处找到了其中一个可能的匹配结果，并标记下此处位置为ω(1)。标记结束后，将窗口右移一位。

C	P	M	_	a	n	n	u	a	l	_	c	o	n	f	e	r	e	n	c	e	_	a	n	n	o	u	n	c	e
																							*	*	*	*	*	*

再次从右侧开始输入字符，直至字母c，自动机状态转移失败。于是我们移动窗口，越过字母c的位置。但此时的移动，将使得搜索窗口超出内容串长度，所以认为搜索结束。

3.3 结果验证

通过先期匹配，我们找到了两个可能的匹配结果ω(0)、ω(1)。但因为先期匹配时使用的Factor Oracle自动机，是基于模式串前缀构造的，所以我们还需要在刚才找到的结果位置，继续向后匹配，以验证是否能够匹配完整的模式串。比如从ω(0)位置向后延伸，就无法完整匹配任意一个模式串。而从ω(1)位置向后延伸，可以完整匹配模式串announce，所以我们得出，ω(1)即为最终的匹配结果。

这一部分的逻辑，由于可能出现多个模式串共用同一前缀的情况，所以为了提升效率，可以使用Tire Tree进行结果的验证。

4. 分析对比

上一节中构造Factor Oracle自动机时，是使用剪裁后的前缀构造的。那么为什么要这么做，其原因在于，如果使用全长模式串构造的话，就无法兼容拥有相同前缀且不同长度的模式串。

同时，因为没有使用全长模式串构造自动机。所以当模式串规模较大时，自动机的构造、使用开销，以及自动机的复杂度都是低于Aho-Corasick算法的，相应的，也就是效率更高。

但是能不能说SBOM算法总是最优的呢？不能，因为当模式串规模较小的时候，自动机复杂程度较低带来的优势被弱化。反而Aho-Corasick算法，因为在匹配过程中只会对内容串读取一遍，所以其效率又反过来高于SBOM算法。

5. 代码实现

SBOM算法的Python封装实现，已经开源上传至github并支持PyPI安装。

地址点这里