IM全文检索技术(五)：vivo敏感词匹配系统的技术实践

本文作者vivo互联网服务器团队Liang Kangwu有修订。1、引言编者注本文虽不是专门的全文检索技术文章但文中涉及到的字词匹配算法等等都是一脉相承所以也同样收录到了“IM全文检索技术”技术专题中希望能给你启发。谛听系统是vivo的内容审核平台保障了vivo各互联网产品持续健康的发展。谛听支持审核多种内容类型但日常主要审核的内容是文本下图是一个完整的文本审核流程包括名单匹配、敏感词匹配、AI机器审核、人工审核四个环节。待审核文本需要顺次通过名单匹配、敏感词匹配、AI机器审核三个流程若结果为嫌疑则需要人工审核否则将直接给出确定的结果。敏感词匹配功能可以迅速地匹配文本中的敏感词汇算法平均耗时为50ms因其简单、快速、直接、灵活的特点成为了审核人员对抗垃圾文本的利器。然而身处信息爆炸时代的网民们非常“优秀”他们源源不断的发明各种新词、谐音词来绕过敏感词检测。例如某些用户会使用“啋票”、“采漂”等词汇来规避敏感词“彩票”其中“啋票”不仅是谐音词还包含多音字常规的模式匹配算法很难保证完全命中。这不仅给运营规则带来挑战也对匹配算法的精准度、漏杀率提出了要求。本文将从算法选型入手结合两个实际场景来介绍谛听系统的敏感词匹配算法。包括底层算法选型思路和两种实际场景下提升敏感词精准度、降低漏杀率的方案。2、系列文章本文是专题系列文章中的第5篇《IM全文检索技术(一)微信移动端的全文检索优化之路》《IM全文检索技术(二)微信移动端的全文检索多音字问题解决方案》《IM全文检索技术(三)网易云信Web端IM的聊天消息全文检索技术实践》《IM全文检索技术(四)微信iOS端的最新全文检索技术优化实践》《IM全文检索技术(五)vivo敏感词匹配系统的技术实践》* 本文3、敏感词匹配算法选型敏感词匹配功能依托于模式匹配算法。模式匹配的定义是给定一个子串在某个字符串中找出与该子串相同的所有子串。其中给定的子串被称为模式串被匹配的字符串被称为目标串。基于多个模式串进行匹配的算法被称为多模式匹配算法目前成熟的多模式匹配算法有AC自动机和WM。3.1 多模式匹配算法对比谛听的敏感词匹配业务有如下特点1词库量大需要维护和加载百万级别的词库模式串2敏感词与业务特性、国家政策相关性强无法统一约定长度、前缀等特征。WM算法对模式串的长度和前缀存在一定的要求可能会影响业务的使用。虽然AC自动机加载耗时长内存占用大但敏感词加载并不频繁且服务器内存资源充足所以我们最终选用AC自动机作为底层算法。3.2 AC自动机算法介绍AC自动机算法Aho–Corasick算法是一种字符串搜索算法可以同时将目标串与所有模式串进行匹配算法均摊情况下具有近似于线性的时间复杂度。AC自动机的匹配原理有两个核心概念Trie字典树、Fail指针。下面以模式串集合{“she”, “he”, “shers”, “his”, “era”}为例来介绍这两个概念。AC自动机算法启动时需要将所有的模式串加载到内存中构建成一个Trie字典树。例如下图是以模式串集合{“she”, “he”, “shers”, “his”, “era”}构建的字典树树中每个节点代表一个字符从根节点到某一个节点的路径即可表示一个模式串且红色节点表示一个字符串的终结例如图中最右边子树上的三个节点可代表模式串“era”。从字典树的根节点出发可以快速的查找到某个模式串。此外拥有相同前缀的模式串会合并到同一个子树中例如中间子树表示模式串“he”、 “his”这两个字符串分别是“h”节点的一个分支。AC自动机在搜索这类字符串时可以节省匹配的次数。AC自动机在Trie树的基础上为每个节点加入了Fail指针上图使用虚线画出了部分节点的Fail指针未画出虚线的节点其Fail指针指向根节点。算法在某个节点匹配失败时可以通过该指针转移到其他包含相同前缀的分支上继续匹配。例如匹配目标串“shis”时对于前两个字符“sh”Trie字典树匹配到左边字数的“h”节点上由于该节点的子节点是字符“e”与目标串的下一个字符“i”不匹配因此算法通过Fail指针转移到中间子树的“h”节点上继续匹配最终命中字符串“his”。上述的Trie字典树与Fail指针组成了AC自动机的数据模型。AC自动机匹配目标串时会按顺序从目标串中取出字符从Trie字典树的根节点出发在子结点中寻找与该字符匹配的结点若能找到则转移到该节点若找不到则转移到Fail指针指向的节点。当状态转移到图中的红色节点时就是命中了一个模式串。下图展示了AC自动机对目标串“merashisnx”进行匹配的过程。4、vivo的谛听系统谛听系统基于AC自动机算法构建了一套敏感词匹配服务将敏感词作为模式串文本内容作为目标串可以实现常用的中、英文敏感词匹配。但是实际的业务有很多细分的场景普通的AC自动机算法已不能满足业务使用需求因此我们探索了组合敏感词匹配和拼音敏感词匹配两种匹配方式下面分别介绍。5、技术实践1组合敏感词常规的敏感词匹配算法通常匹配单个词或者短句但某些词单独出现时并不违规只有在与几个特定的词同时出现时才能判定为违规。组合敏感词的匹配算法依然基于AC自动机算法。由于AC自动机只能判断单个词的命中情况因此我们将组合敏感词分割成单个敏感词并维护各敏感词与组合间的映射关系在AC自动机算法运行结束后只有某个组合对应的敏感词全部命中时才能判断该组合敏感词命中。为此我们需要给AC自动机添加一些前置和后置的处理步骤具体步骤如下1将组合敏感词分割为单个敏感词并记录敏感词与组合的映射关系2将分割后的组合敏感词添加到AC自动机的Tire树中3运行AC自动机匹配文本4遍历匹配结果将匹配的结果根据映射关系映射到相应的组合上5记录组合的命中情况得到最终匹配结果。在步骤4中算法将匹配的词映射到组合中并标记对应的词命中。步骤5会根据各组合中单词的命中情况来判断该组合是否命中由于在步骤4中组合敏感词均被标记为命中因此可判断该组合命中。6、技术实践2拼音敏感词6.1 概述在评论、弹幕等创作自由度很高的场景中某些用户为了规避机器审核会使用一些多音字、同音字来表达敏感词汇例如用“啋票”来代表“彩票”等。由于多音字、同音字变化较多将一个词的所有谐音词都穷举出来是很困难的。因此我们实现了拼音敏感词的匹配方案将中文文本转换为拼音再匹配通过读音匹配敏感词即可保证命中所有的同音字运营直接配置敏感词的拼音例如“CAI PIAO”即可命中“啋票”、“彩票”、“采漂”等词汇。6.2 匹配流程常规的AC自动机算法是逐字符匹配的因此Trie树上每个节点存储一个字符但拼音敏感词需要按照音节匹配因此我们将Trie树的节点数据类型由char改为String。示例如下拼音敏感词的匹配关键在于将汉字准确的转换为拼音这一点在多音字的场景下尤为重要。由于多音字的读音是受语境影响的现有的技术条件很难确保能将多音字准确的转换为拼音而上文提到同音词“啋票”是用户自行造的词算法无法准确的识别语境可能转换得到“CAI PIAO”、“XIAO PIAO”两种不同的结果。如果拼音转换不精准则拼音敏感词也无法准确命中。因此我们不依赖算法识别多音字的读音而是将文本内容的所有读音都列出来匹配一遍就可以避免避免拼音转换不精准的问题。下图展示了文本内容与拼音的对应关系由于存在多音字因此存储拼音的数组从一维扩展到了二维更像是“图”的数据结构下文将其称为拼音图。拼音图的起始节点和终止节点之间存在多条路径这些路径对应了多音字的所有排列组合情况为了避免漏杀我们需要使用AC自动机将这些路径都匹配一遍。从第二节的匹配流程可以看出目标串是一维数组因此AC自动机在匹配文本时通常采用顺序遍历的方式。而在拼音敏感词中由于目标串采用二维数组存储是一种类似于“图”的数据结构不再适合使用顺序遍历的方式因此需要采用图的遍历算法。图的遍历算法中最常用的就是深度优先遍历DFS和广度优先遍历BFS。由于词语是前后关联的为了使算法更符合人类思考习惯我们选择了DFS。DFS算法使用栈存储节点信息在当前分支遍历完成后通过栈中的信息回溯到上一个分支处继续遍历。由于Trie树的状态位与拼音图的节点是相关的在DFS回溯时Trie树也需要同步回溯因此需要将Trie树状态位与拼音图的节点信息一起保存到DFS栈中。下图展示了拼音敏感词的匹配流程6.3 终止条件与剪枝策略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”节点的深度D1“YOU”节点的深度D2。从Trie树根节点到某一个节点的路径上经过的字符连接起来为该节点对应的模式串因此节点的深度D即为模式串的长度。当D B时表明当前正在匹配的模式串长度短于拼音图中当前节点的分支路径长度所以当前的模式串与当前的路径无关。总结一下剪枝所需的条件为1拼音图中下一节点已被遍历2拼音图的分支路径长度B Trie树节点的深度D。7、写在最后谛听系统基于AC自动机实现了普通敏感词、组合敏感词、拼音敏感词的匹配其中组合敏感词和拼音敏感词还可以结合成为拼音组合敏感词覆盖了大部分的文本审核场景减轻了机审、人审的压力。另外在政策风向发生变化时敏感词匹配功能为运营同事提供了一种快速变更审核策略的手段使谛听的文本审核能力更加灵活。目前谛听线上已经配置了数量超过100万的敏感词极大程度的保障了公司的内容安全。未来我们将结合业务使用场景继续优化敏感词匹配的能力提升精准度和命中率1一方面我们可以采用某种方式实现“非”的逻辑这样可以在配置敏感词时排除bad case提升命中的精准度2另一方面我们可以实现敏感词的模糊命中提升敏感词的命中率。8、相关资料[1] 零基础IM开发入门(一)什么是IM聊天系统[2] 新手入门一篇就够从零开发移动端IM[3] IM消息ID技术专题(七)深度解密vivo的自研分布式ID服务(鲁班)[4] 阿里IM技术分享(七)某鱼IM的在线、离线聊天数据同步机制优化实践[5] 探探的IM长连接技术实践技术选型、架构设计、性能优化[6] IM开发干货分享浅谈IM系统中离线消息、历史消息的最佳实践[7] 得物自研移动端弱网诊断工具的技术实践分享[8] 如何保障分布式IM聊天系统的消息有序性即消息不乱[9] 社交场景下的统一即时通讯im消息流交互层模块化技术实践[10] 直播系统聊天技术(八)vivo直播系统中IM消息模块的架构实践[11] 得物从0到1自研客服IM系统的技术实践之路[12] 海量用户IM聊天室的架构设计与实践[13] 一套分布式IM即时通讯系统的技术选型和架构设计[14] 陌陌技术分享陌陌IM在后端KV缓存架构上的技术实践[15] 来看看某信十年前的IM消息收发架构你做到了吗[16] 携程技术分享亿级流量的办公IM及开放平台技术实践[17] 转转平台IM系统架构设计与实践(一)整体架构设计[18] 支持百万人超大群聊的Web端IM架构设计与实践[19] 转转客服IM聊天系统背后的技术挑战和实践分享[20] B站IM消息系统的新架构升级实践[21] 如何保障分布式IM聊天系统的消息有序性即消息不乱[22] 即时通讯IM离线消息该怎么存全面盘点主流存储方案即时通讯技术学习- 移动端IM开发入门文章《新手入门一篇就够从零开发移动端IM》- 开源IM框架源码https://github.com/JackJiang2011/MobileIMSDK备用地址点此本文同步发布于 http://www.52im.net/thread-4923-1-1.html