3.2.1 匹配流程
常规的AC自动机算法是逐字符匹配的，因此Trie树上每个节点存储一个字符，但拼音敏感词需要按照音节匹配，因此我们将Trie树的节点数据类型由char改为String，示例：
拼音敏感词的匹配关键在于将汉字准确的转换为拼音，这一点在多音字的场景下尤为重要。由于多音字的读音是受语境影响的，现有的技术条件很难确保能将多音字准确的转换为拼音，而上文提到同音词“啋票”是用户自行造的词，算法无法准确的识别语境，可能转换得到“CAI PIAO ”、“XIAO PIAO ”两种不同的结果。如果拼音转换不精准，则拼音敏感词也无法准确命中。
因此我们不依赖算法识别多音字的读音，而是将文本内容的所有读音都列出来匹配一遍，就可以避免避免拼音转换不精准的问题。
下图展示了文本内容与拼音的对应关系，由于存在多音字，因此存储拼音的数组从一维扩展到了二维，更像是“图”的数据结构，下文将其称为拼音图。拼音图的起始节点和终止节点之间存在多条路径，这些路径对应了多音字的所有排列组合情况，为了避免漏杀，我们需要使用AC自动机将这些路径都匹配一遍。
从第二节的匹配流程可以看出，目标串是一维数组，因此AC自动机在匹配文本时，通常采用顺序遍历的方式。而在拼音敏感词中，由于目标串采用二维数组存储，是一种类似于“图”的数据结构，不再适合使用顺序遍历的方式，因此需要采用图的遍历算法。
图的遍历算法中，最常用的就是深度优先遍历（DFS）和广度优先遍历（BFS）。由于词语是前后关联的，为了使算法更符合人类思考习惯，我们选择了DFS。DFS算法使用栈存储节点信息，在当前分支遍历完成后，通过栈中的信息回溯到上一个分支处继续遍历。由于Trie树的状态位与拼音图的节点是相关的，在DFS回溯时，Trie树也需要同步回溯，因此需要将Trie树状态位与拼音图的节点信息一起保存到DFS栈中。下图展示了拼音敏感词的匹配流程。
3.2.2 终止条件与剪枝策略
DFS的终止条件是当所有节点都被遍历过，且算法会确保每个节点只会被遍历一次。但是DFS遍历时会在分支处回溯，所以往往终止的节点并不是待匹配文本的终点，很有可能AC自动机的匹配并未完成。
例如在下图所示的匹配流程中，左图是基于待匹配文本“朱朝阳和朋友”构建的拼音图，右图是基于拼音敏感词“PENG YOU”、“ZHAO YANG”、“NI MA”、“MA DE”构建的Trie树。左图的拼音图采用DFS算法遍历，算法最后访问的节点是蓝色节点“ZHAO ”，此时拼音图中所有节点均被遍历了一次，已经达到了DFS的终止条件。但右图中Trie树上的状态位处于蓝色节点“ZHAO ”的位置，并没有达到终止状态，若此时停止匹配，则会导致无法命中敏感词“ZHAO YANG ”，故算法应继续运行，直到AC自动机匹配失败为止。
因此合适的终止条件是：拼音图所有节点均被遍历 且 AC自动机匹配失败 。
由于算法需要结合DFS和AC自动机的状态来判断终止条件，因此会出现拼音图中一个节点和路径被遍历多次的情况，当待匹配文本中多音字 数量增多时，DFS遍历的路径数量会以笛卡尔积的形式增加。而这些路径中会存在一部分重复的情况，因此在遍历的过程中需要采取合适的剪枝策略，避免搜索一些重复的路径。例如下面左图所示的遍历情况，路径②上“PENG”、“ YOU”两个节点已被路径①遍历过，且对应的AC自动机状态位（参考右图）前缀并不包含当前遍历节点“HU ”，所以“PENG ”对应的敏感词与路径②无关，不必再搜索一次。我们可以针对这种场景设计了剪枝策略，需要剪枝的路径需要满足两个条件：
1）首先当前节点的下一节点已被遍历过；
2）下一节点对应的AC自动机状态与当前节点无关。
我们为拼音图中的每个节点标记一个分支路径长度B，表示当前节点与上一个最近的分支节点间的路径长度，例如节点“PENG”对应的分支路径长度为B = 2（从“HU ”到“PENG ”），节点“YOU ”的分支路径长度为B = 3（“HU ”、“PENG ”、“YOU ”）。在AC自动机的状态机中，记录Trie树上每个节点的深度D。例如状态机中“PENG ”节点的深度D =1，“YOU ”节点的深度D =2。从Trie树根节点到某一个节点的路径上经过的字符连接起来，为该节点对应的模式串，因此节点的深度D 即为模式串的长度。当D < B时，表明当前正在匹配的模式串长度短于拼音图中当前节点的分支路径长度，所以当前的模式串与当前的路径无关。
总结一下，剪枝所需的条件为：
1）拼音图中下一节点已被遍历；
2）拼音图的分支路径长度B > Trie树节点的深度D。
四、总结与展望
谛听系统基于AC自动机实现了普通敏感词、组合敏感词、拼音敏感词的匹配，其中组合敏感词和拼音敏感词还可以结合成为拼音组合敏感词，覆盖了大部分的文本审核场景，减轻了机审、人审的压力。另外，在政策风向发生变化时，敏感词匹配功能为运营同事提供了一种快速变更审核策略的手段，使谛听的文本审核能力更加灵活。目前谛听线上已经配置了数量超过100万的敏感词，极大程度的保障了公司的内容安全。
未来我们将结合业务使用场景继续优化敏感词匹配的能力，提升精准度和命中率。一方面我们可以采用某种方式实现“非”的逻辑，这样可以在配置敏感词时排除bad case，提升命中的精准度。另一方面，我们可以实现敏感词的模糊命中，提升敏感词的命中率。
