敏感词项目中柔性字符串匹配问题

背景问题

在给定文本中排查一个固定字符串并不是一件很难的事情，但是倘若给定的字符串库十分庞大，以及涉及到多种字词组合的时候，性能和效率都成了不得不考虑的问题。对此，算法团队做了一些系统的工作，并将其用于对果壳网现有敏感词项目的改进。

敏感词的排查是所有社交网络都会面临的一个任务，对于固定的字符串，直观的想法可以是从列表中挨个取出所有的敏感词，再将它们与全文做一一比对，这样的思路虽然可行，但是在面对不断扩大的敏感词列表，既丑陋又笨拙。除此之外，线上还有一些动名词组合的情况需要考虑，即动词和名词分别可以出现，但是当它们以一种可以被识别的形式出现，并传达确定意义的时候，那就理应得到屏蔽。

对于固定的字符串，如何最快速地将它们全部抓出来；对于动名词组合，如何在做到不放过一条漏网之鱼的情况下尽量避免误伤，都是亟待解决的问题。

对于固定的敏感词匹配，可以粗略地为字符串匹配问题，不过在正式解决之前，我们先来对这个问题再次做个定义。

对问题的重定义

一个字符串是一个定义在有限字母集合 $\sum$ 上的字符序列。例如 $ABCDABC$ 就是字母表 $\sum = \{A,B,C,D\}$ 上的一个字符串。那么字符串匹配问题实际上就是在一个大的字符串 $T$ 中搜索某个特定的字符串 $p$ 出现的位置。为方便表述，在这里我们不妨把 $T$ 称作文本，$p$ 称作模式串，长度为 $m$，以及 $T$ 和 $p$ 都定义在同一个字母表 $\sum$ 上。对于单个的字符串问题，根据搜索模式串的方式的不同，一般来说可以归结为三种思路：

基于前缀：从文本中挨个读字符，每读一个字符就更新相应的变量，检查是否存在一个可能的匹配。这种思路中最为典型的就是大名鼎鼎算法 KMP 以及后来居上的 Shift-Or。

基于后缀：先设定一个滑动的窗口 $W$，滑动窗口沿着文本 $T$ 移动，对于任意位置上的窗口，在窗口中从后向前搜索窗口中的文本和模式串 $p$ 的公共后缀。BM 算法就是使用了这种思想，但是一般情况下，BM 的一个简化版本 Horspool 性能更好，同时也有着非常广泛的应用，通常我们的浏览器、编辑器中的搜索功能都是它的实现。

基于子串：和第二种方法类似，这里也使用了滑动窗口的概念，也是从后向前搜索。有区别的地方是，搜索目标变成了是窗口中文本的最长后缀，显然它同时也是模式串 $p$ 的一个子串。最早使用这个思想的算法是 BDM，如果模式串 $p$ 稍短，可以将它改进为 BNDM。

鉴于基于前缀的搜索比较慢，以及基于子串的搜索方法只适合非常长的字符串，而这与我们的敏感词匹配要求并不复合，因此我们选择基于后缀的搜索方法。

前面提到这种基于后缀的搜索算法的基本思路是要设定一个滑动的窗口，然后让它沿着文本移动进行匹配，事实上这种方法最大的难点也就在于如何安全地移动窗口，以避免错过正确的匹配。

Boyer-Moore 算法

我们先设定三个移动窗口函数 $d_1,d_2,d_3$ 来用来分别对应后面提到的移动窗口时候面对的三种不同的情况。这里我们不妨假设已经读入了一个既是窗口中文本的后缀，也是模式串 $p$ 的子串的字符串 $p_0$，以及恰好下面即将读入的文本中的字符串 $\alpha$ 与 $p$ 中的下一个字符 $\beta$ 不一样。

我们先来看第一种情况，后缀 $p_0$ 在模式串 $p$ 的多个位置有出现，假设最右出现的位置为 $j$，这里不包括在模式串末尾的情况。此时我们已经匹配好的后缀 $p_0 = p_{j-|p_0|+1}…p_j$，以及安全的移动方法是，将窗口往右移动 $m-j$ 个字符，才能使得文本中的 $p_0$ 与 $p$ 下一个 $p_0$ 的出现的位置对齐。对于 $p$ 的每一个后缀，都需要计算它到它下一次出现位置之间的距离，这个距离我们就用前面定义的窗口移动函数 $d_1$ 来表示。显然的一个特例是，如果 $p_0$ 在 $p$ 中只出现一次，那么此时 $d_1(p_0) = m$。

再说第二种情况，此时后缀 $p_0$ 不出现 $p$ 中的其他位置。此时考虑情况如下图，即 $p_0$ 的一个后缀 $p_0’$ 同时也是 $p$ 的一个前缀。显然，在这种情况下，如果直接移动整个窗口的大小是很危险的动作，可能会错过正确的匹配。于是我们需要对模式串的所有后缀计算第二个函数 $d_2$，即对于 $p$ 的每一个后缀 $p_0, p_1,…p_i,…,p_n$ 来说，$p_i$ 会存在一个 $p_i’$，它是 $p$ 的前缀和 $p_i$ 的后缀的重合体中长度最长的那个。

最后再来说存在的第三种情况，当我们的搜索窗口从后向前移动时，在文本字符 $\alpha$ 处不能成功匹配。此时如果用第一种情况下的 $d_1$ 进行窗口移动，并且 $p$ 中对应的字符并不是 $\alpha$，而是 $\beta$，那么将会对新的搜索窗口多一次验证，这显然是冗余的。我们的第三种移动函数 $d_3$ 也就应运而生了。$d_3$ 可以用来保证下一次验证时文本字符 $\alpha$ 与 $p$ 中的 $\alpha$ 对齐。我们不妨将 $d_3(\alpha$) 记作 $\alpha$ 在 $p$ 中最右的位置到末尾的距离。当然，倘若 $\alpha$ 在 $p$ 中并没有出现，那么 $d_3(\alpha) = m$。

有了这三种情况的拆分，BM 算法整体就相对好理解了。回到开始，即将读入的文本中的字符串 $\alpha$ 与 $p$ 中的下一个字符 $\beta$ 不一样，窗口移动的距离就由这三个函数来决定：

比较 $d_1(p_0$) 与 $d_2(p_0’$)，将它们中较大的那一个用作窗口移动的距离，因为我们期望的是 $p_0$ 和它在 $p$ 中下一次出现的位置对齐；
取上面的结果，并与 $m-d_2(p_0$) 来作比较，将它们中较小的用作窗口移动的距离，这是很显然的，因为 $m-d_2(p_0$) 已经是最大可以接受的安全距离。

BM 的搜索时间复杂是 $O(mn$)，总的来说还算不错，但是比较麻烦的地方在于需要计算 $d_1, d_2, d_3$，下面介绍它的一个简化版本，也是它应用最多的一个版本，Horspool。

Horspool 算法

Horspool 相对于 BM 最大的简化的地方是使用了一个统计上的经验，即，在面对字母表的 $\sum$ 较大的时候，$d_3$ 总是有很大概率产生最大的移动距离。基于此，我们不妨就让 $d_3$ 能够产生更大的移动距离。不妨用下图来说明，对于每个移动的搜索窗口，Horspool 将窗口中文本字符串 $T$ 的最后一个字符（图中的 $\theta$）和模式串 $p$ 的最后一个字符 $p[-1]$ 进行比较。如果它们相等，则需要进行验证。过程是首先在搜索窗口中从后向前对 $T$ 和 $p$ 进行比较，直到出现完全相等（匹配成功），或者第一个不匹配（图中 $\alpha$ 和 $\beta$），然后，无论是否成功，窗口的下一个移动距离是依据 $p$ 中 $\theta$ 的位置：下面对算法整体的流程简述：

输入：模式串 $p = p_1p_2…p_m$；目标文本 $T = t_1t_2…t_n$；
输出：窗口指针位置 $pos$；
步骤：
1. 数据预处理阶段，主要是做一些存储。对所有 $c \in \sum$，有 $d[c] \leftarrow m$；对所有 $j \in 1,2,…,m-1$，有 $d[p_j] \leftarrow m-j$；
2. 搜索阶段。首先将当前位置 $pos$ 置为0，检查 $pos \leqslant n-m$，倘若是，那么 $j \leftarrow m$；然后去 3，如果否，跳转到 5；
3. 检查 $j>0$ 且 $ t_{pos} == p_j$，倘若是，有 $j \leftarrow j-1$，然后去 4；如果否，跳转到 5；
4. 检查如果 $j == 0$，然后记录下匹配位置 $pos+1$，跳转到 5；
5. 窗口位置移动，即当前位置的指针执行移动：$pos \leftarrow pos+d[t_{pos+m}]$，后跳转 2；

多字符串匹配

回到开头，我们的问题其实是在一个给定的敏感词列表中进行排查，即表中的所有字符串都不能在文本中出现，即字符串集匹配，或者多字符串匹配问题。

其实单字符出匹配问题可以很自然地扩展到这样的多字符串匹配问题，$P = \{p_1,p_2,…,p_r\}$ 就是一组我们要搜索的字符串。在系统分析这个问题之前，我们先不妨做一些定义： $p_i$ 是定义在一个有限字母表 $\sum$ 上的字符串，$p_i=p_{i1}p_{i2}...p_{im_i}$。记 $|P|$ 为 $P$ 中所有字符串长度之和，即 $|P| = \sum_{i=1}^{r}|p^i|=\sum_{i=1}^{r}m_i$，同时 $l_{min}$ 和 $l_{max}$ 分别是 $P$ 中最短和最长模式串的长度，目标文本 $T = t_1t_2…t_n$。

注意 $P$ 中的少数字符串可能是集合中其他字符串的前后缀，例如涉枪涉爆类别中既有「枪弩」也有「气枪弩」，也就是说如果「枪弩」被匹配成功，显然「气枪弩」也是会被匹配出来。因此，模式串总的出现次数最大可能为 $rn$。那么我们真正的目标实际上是所有满足 $p_i=t_{j-|p_i|+1}…t_j$ 的整数对 $(i,j)$。

其实对于多字符串匹配的一个最简单的思路就是使用前面的单字符串匹配方法，遍历整个集合即可。但是这样会直接搜索的时间复杂度为 $O(rn$)，以及还有数据预处理阶段的大量时间。显然这么做是笨拙的，也是低效的，我们下面对前面使用的单字符串匹配算法进行一定的扩展，以达到性能上的优化。

虽然单字符串匹配问题中的三种思路都是可以扩展，但是对于我们的问题后缀搜索效率最高，故将我们的主要工作重心放在基于后缀的字符串匹配问题的扩展上。

Trie Tree

我们先介绍一种称之为前缀树的数据结构，或者叫字典树，trie tree，之所以要先介绍它首先是因为它能够帮助理解后面的推导与演算，还有一个重要的原因是前缀树在非常多的字符串问题中扮演了极其重要的角色。

那我们就这个项目举例来看，假设集合 $P = \{p_1,p_2,…,p_r\}$ 对应的前缀树结构其实是一棵有向的有根树，每个从根节点开始到叶子节点结束的路径上的所有标号构成的字符串，都对应着集合 $P$ 中的某一个元素 $p_i$，反过来，集合 $P$ 中的每一个元素也都对应着前缀树中的一条从 root 到叶子节点的路径。对于前缀树来说，倘若一个结点 $q$ 对应这一个 $P$ 中的某个元素，那我们我们就将它称之为可以接受的状态，函数 $F(q$) 包含了 $q$ 所对应的集合 $P$ 中的所有字符串。下图就是一个简单例子，是 $P = \{tee, tea, teacher\}$ 所对应的 trie 结构。

自动机

在计算机科学中，自动机这个词其实意义很多。我们下面单就字符串匹配领域来说说自动机，照例，我们先给出一些定义。

一个有限状态自动机 $\mathcal{A}$，或者简称做自动机，一般是由五个元素组成：

一个有限的状态集合 $\mathcal{Q}$
一个初始状态 $\mathcal{s} \in \mathcal{Q}$
一个输入字母表 $\sum$（非空有限的状态集合）
一个可以被接受的状态的集合 $\mathcal{F} \subseteq \mathcal{Q}$
一个状态转移函数 $\delta: \mathcal{Q} \times \sum \rightarrow \mathcal{Q}$（例如：$ \delta (q,\sigma) = p,(p,q \in \mathcal{Q}, \sigma\in\sum$）

这样，自动机 $\mathcal{A} = (\mathcal{Q}, \sum, \mathcal{s}, \mathcal{F}, \delta$) 就用这样的五元组来表示。

在实际应用中，根据状态转移函数的形式大抵可以分为两类：一类称之为非确定的有限自动机，它的状态转移函数 $\delta$ 将某一个状态 $q$ 通过一个给定字符 $\sigma$ 关联到多于1个的状态，即

$$\delta(q,\sigma) = \{q_1,q_2,…,q_k\}, k>1$$

或者某些状态装一能被标记为 $\varepsilon$。此时，我们的状态转移函数 $\sigma$ 就可以用三元组：

$$\Delta = \{(q,\sigma,q’)\}, q\in\mathcal{Q}, \sigma\in\sum,q’ \in \delta(q,\sigma)\}$$

的集合来表示。另外一类则称之为确定的有限自动机，区别在于它的状态转移函数 $\delta$ 可以用一个部分函数 $\delta：\mathcal{Q}\times\sum \rightarrow \mathcal{Q}$ 来表示，如果 $\delta(q,\sigma) = \{q’\}$，那么 $\delta(q,\sigma) = q’$，下图给出了两个例子：

上图中给出了两种自动机的模型。其中 $0$ 是初始状态，灰色表示可以被接受的终止状态。左边的是非确定性的自动机，因为从状态 $0$ 通过 $d$ 或者 $d\rightarrow a\rightarrow b$ 到达状态 $6$，即便是只通过 $d$ 的话，也可以达到 $6$ 或者 $2$。而右图则是确定性的自动机，因为对于任何一个字符，每个状态都只能转移到一个状态。

那么在这个自动机 $\mathcal{A} = (\mathcal{Q}, \sum, \mathcal{s}, \mathcal{F}, \delta$) 中，如果将从状态 $s$ 到一个可以被接受的状态路径上的标记连起来可以得到的字符串则可以被自动机 $\mathcal{A}$ 识别。

注意，在非确定的有限状态机中，是允许状态转移上被标记为空串的，我们将这样的状态转移称之为 $\varepsilon$-转移。这就意味着不必要读入一个字符也可完成一次状态转移。那么如果到达了一个 $\varepsilon$转移的原状态，那么不用读取就可以立即完成跳转，这样也是可以看做是读入了一个空串。事实上，$\varepsilon$ 转移通常用来简化这种非确定的有限状态自己懂的构造，但是总是存在一个与之等价的不含 $\varepsilon$ 转移的自动机。

但是总而言之，不管是在确定性还是非确定性的有限状态自动机中，如果将从 $s$ 到某一个状态的 $s_0$ 的路径上标记穿起来可以得到字符串 $x$，那么就说，读入 $x$ 后的状态 $s_0$ 是一个活动状态。在任何时候，确定性的有限状态自动机中，最多只有一个活动状态，而非确定性的则可能存在多个。

上图表示两个自动机中的状态转移不会构成环，这样的自动机不论确定性与否，都被称之为无环的下图两个的自动机则是有环的，一个有环的自动机可以接受的状态集合可能是无限的。

例如上图中的有环自动机，左图可以识别 $P=\{dab\}$, 也可以识别 $P=\{dab, dabaab, dabaabaab,…\}$。

基于后缀的多字符串匹配

穿插着了解了前缀树和自动机之后，我们回到上文继续讨论基于后缀的多字符串匹配问题，我们这里主要的思想是对使用后缀匹配思想单字符串的匹配算法的扩展。这样的第一个算法对 BM 的扩展， Commentz-Walter，当然也有对 Hospool 的扩展，下面我们逐一讨论。

Commentz-Walter

Commentz-Walter（以下简称 CW 算法）算法是对 BM 算法的扩展，它的应用非常广泛，例如 UNIX 下的非常著名的搜索程序 Grep 的第二个版本就是它的一个实现。

CW 算法中用前缀树来表示 $P=\{p_1,p_2,…,p_r\}$ 的反转 $P_{rv}=\{p_{1,rv},p_{2,rv},…,p_{r,rv}\}$，并用它来识别文本字符。由于这个算法性能差强人意，我们简单说说思想。在窗口移动过程中，指针 $pos$ 指向 $l_{min}$，对于 $pos$ 的每个新位置，从 $pos$ 开始，从后向前识别文本 $t_1t_2…t_{pos}$ 的最长后缀 $u$，使得 $u$ 也是某一个模式串的后缀，然后根据在多模式串集合上扩展的 BM 算法的三个函数 $d_1,d_2$ 和 $d_3$，将 $pos$ 右移。以及对于前缀树的每个状态，都需要计算 $d_1$ 和 $d_2$，当最长后缀 $u$ 在可以接受的状态集合中被识别出来并抵达状态 $q$ 时，再根据 $d_1$ 和 $d_2$ 进行移动。

$d_1(q)$ 是使得 $u = \mathcal{L}(q)$ 与某一个模式串的子串对齐的最小移动距离 $p_j \in \mathcal{P}$
$d_2(q)$ 是使得 $u = \mathcal{L}(q)$ 的一个后缀与某一个模式串的前缀相匹配的最小移动距离 $p_j \in \mathcal{P}$

那么对于 $\sum$ 中每个字符 $\alpha$ 和每一个位置 $0\leqslant k< l_{max}$，$d_3[\alpha,k]$ 是使得位置 $pos-k$ 处的字符串与模式串 $p$ 中某个字符相匹配的最小移动距离 $p_j \in \mathcal{P}$。

下面简述如何用这三个函数来计算我们所需的移动距离，我们不妨假设从文本位置 $pos$ 从后向前读入了 $k$ 个字符，并且在自动机中抵达了状态 $q$，那么移动距离 $s[q,pos,k]$ 可以由下面的公式推导而来：

$$s[q,pos,k] = min\left\{\begin{matrix} max(d_1[q],d_3[t_{pos-k},k]) \\ d_2[q] \end{matrix}\right.$$

上式是 BM 算法窗口移动的直接扩展，显然有 $d_2\leqslant l_{min}$，所以最长的跳跃距离必然不会超过 $l_{min}$。

CW 算法的时间复杂度为 $O(n \times l_{max}$)，$d_1,d_2,d_3$可以在 $O(|P|$) 的时间内计算完成。

Set Horspool

Set Horspool （下称 SH）是对单字符串的 Horspool 算法扩展，它也可以看作是 CW 算法的简化。

SH 算法的基本流程如图，假设当前文本位置 $pos$ 初始化为 $l_{min}$，从 $pos$ 开始，从后向前读入文本字符。这里使用所有模式串反转 $p_{rv}$ 构建的前缀树来完成识别过程，如果到达状态 $s_0$ 恰好属于可以接受的结束状态，就标记下一个匹配，假设当无法继续识别读入的文本字符，就根据第一个读入的文本字符 $\beta$ 来决定 $pos$ 的移动。$pos$ 移动到使得 $\beta$ 与它在前缀树中下一次出现位置对齐的地方。一个显然的特例是，如果 $\beta$ 不再重复出现，那么就直接移动 $l_{min}$ 即可。

下面简述 SH 算法的流程：

输入：模式串集 $P = \{p_1,p_2,…,p_r\}$，目标文本 $T=t_1t_2…t_n$；
输出：窗口指针位置 $pos$；
步骤：
1. 预处理阶段。$HO \leftarrow Trie(P_{rv}=\{p_{1,rv},p_{2,rv},…,p_{r,rv}\})$，其中这里的$\delta_{HO}$是状态转移函数；对于$c\in\sum$，有$d[c]\leftarrow l_{min}$；对于所有$j\in 1,2,…,r$，有$d[p_{jk}]\leftarrow min(d[p_{jk}], m_j-k), k\in 1,2,…,m_j-1$
2. 初始化当前指针位置，$pos \leftarrow l_{min}$，检查 $pos \leqslant n$，如果是，$j \leftarrow 0$，也即从 $HO$ 中拿到它的初始状态，然后跳转到 3，如果不是，跳转到 6；
3. 检查如果 $pos - j >0$ 且 $\delta_{HO}(t_{pos-j}, Current)\neq\theta$，跳转到 4，如果不是，跳转到 6；
4. 检查 $Current$ 是否是可以被接受的终止状态，如果是则记录下 $\mathcal{F}(Current, pos$)，如果不是，跳转到 5；
5. 执行状态转移 $Current \leftarrow \delta_{HO}(t_{pos-j}, Current)$，同时 $j \leftarrow j+1$；
6. 位置指针转移 $pos \leftarrow pos + d[t_{pos}]$；

SH 算法的复杂度是 $O(n\times l_{max}$)，一般来说，它只适合模式串集合很小，但是字母表 $\sum$ 却很大的场合。

Wu-Manber

SH 在多模式串的情况下其实性能很差，主要归咎于字母表 $\sum$ 中每个字符通常都以较高概率出现在某个模式串中，从而导致移动距离下降。

Wu-Manber（下称 WM）解决的思路是读入一块字符，从而降低字符块在某个模式串中出现的概率。这里我们不妨假设块的长度为 $B$。问题的难点在于，如果 $B$ 比较大，那么总共就可能会有 $|\sum|^B$ 个不同的块，对存储空间是一个不小的挑战。

WM 首先使用一个散列函数 $h_1$ 将所有可能的块散列到一个有限的表 $SHIFT$上，两个不同的块有可能被散列映射到 $SHIFT$ 的同一个位置。对于每个新的位置，如果读入一块字符 $Bl$ 而不是像 Horspool 那样只读入最后一个字符，则必须确保 $Bl$ 的移动距离 $SHIFT(h_1(Bl)$) 是安全的。为了确保这一点，算法在 $SHIFT(j$) 中存入满足 $j=h_1(Bl$) 的所有块的移动距离的最小值。具体地说，构建 $SHIFT$ 表的步骤如下：

如果块 $Bl$ 不出现在 $P$ 中的任何一个模式串中，则可以安全地向右移动 $l_{min}-B+1$ 个字符。因此，将表的每一项都初始化为 $l_{min}-B+1$。
反之，如果块 $Bl$ 出现在 $P$ 中的某一个模式串中，我们不妨把它记作 $p_i$，则需要找出 $Bl$ 在 $p_i$ 中最右出现的末尾位置 $j$，然后将 $SHIFT(h_1(Bl)$) 置为 $m_i -j$。

为了计算 $SHIFT$ 表的所有值，对于每个模式串 $p_i=p_{i1}p_{i2}…p_{im_i}$ 的每个块 $B=p_{i,j-B+1}…p_{i,j}$，都需要在 $SHIFT$ 中寻找出对应的表项 $h_1(B$)，并将 $SHIFT(h_1(Bl)$) 置为 $m_i -j$ 和它当前值中的较小的那个。

其实块长 $B$ 取决于三个因素：最短的关键词长度 $l_{min}$；模式串集合的大小以及字母表 $\sum$ 的大小。研究表明，取 $B = log_{|\sum|}(2\times l_{min} \times r$) 能够产生最好的实验结果。$SHIFT$ 的大小也是随着可用空间的大小而变化。

只要移动距离 $l>0$，就可以安全地将当前位置向右移动，当移动距离 $l = 0$ 时，当前位置的左边可能就是一个被成功匹配的模式串，那么对于这种情况，WM 巧妙地使用另一个散列表 $HASH$ 和散列函数 $h_2$，它的每个表项 $HASH(j$) 本质是一个链表结构，记录了最后一个块在 $h_2$ 的散列映射中到 $j$ 的所有模式串集合。于是这样就可以顺藤摸瓜找出那些最后一块的散列值与当前读入的文本块 $Bl$ 散列值相同的所有模式串。

搜索阶段和 SH 算法是类似的，首先将当前位置 $pos$ 初始化置为 $l_{min}$，那么对于每个当前位置 $pos$，从后向前读入 $B$ 个字符的块 $Bl$。这时倘若 $j = SHIFT(h_1(Bl)) > 0$，那么将窗口移动到位置 $pos+j$，并继续搜索；反之，如果 $SHIFT(h_1(Bl)) = 0$，那我们就用 $HASH$ 算出文本块对应的一组模式串 $HASH(h_2(Bl)$)，并逐个与文本进行比较，算法流程如下：

输入：模式串集 $P = \{p_1,p_2,…,p_r\}$，目标文本 $T=t_1t_2…t_n$；
输出：窗口指针位置 $pos$；
步骤：
1. 预处理阶段，计算 $B$，然后继续构建两个哈希表 $SHIFT$ 和 $HASH$；
2. 初始化当前指针位置，$pos \leftarrow l_{min}$，检查 $pos \leqslant n$，如果是，$i \leftarrow h_1(t_{pos-B+1}…t_{pos}$，然后跳转到 3，否则算法结束；
3. 检查 $SHIFT[i] == 0$，如果是，$list \leftarrow HASH[h_2(t_{pos-B+1}…t_{pos})]$，这里的 $list$ 装载了匹配好的模型，挨个对应着目标文本$T$，随后照例 $pos \leftarrow pos + 1$，如果不是，跳转到 4；
4. 窗口指针位置转移 $pos \leftarrow pos + SHIFT[i]$；

以上就是对于固定的敏感词列表的排查算法的研究，其中也包含了大量的实践操作，虽然它们各有优劣，但是就目前敏感词列表大小，词组长度以及字母表的长度而言，Wu-Manber 是不二的选择。

总结

虽然排查敏感词从功能上来说并不是一个十分艰巨的任务，但是我们还是对这个问题做了一个较为系统和深入的研究工作，以期从算法角度得到高效且优雅的解决方案。