前言：了解风控

• 什么是风控？
  简单的说就是风险控制。风控是一个很笼统的概述，不同的行业、不同的场景，所需要做的风控手动也有很大的区别，比如金融风控、内容风控、活动风控等等。不同的场景下也需要不同的风控策略。

什么风险，怎么控制？

• 其实这里的风险就是一种可能，一种作弊场景。而控制就是面对这种作弊场景的一种或多种解决方案。

  
  image.png
  

  除此之外，还有信贷风控、金融风控、活动营销风控、网络欺诈（杀猪盘）等等

1、内容(合规)反作弊：

1.1、生活中的内容风控：

image.png

1.2、背景：

• 随着移动互联网的蓬勃发展，人们获取信息资讯的渠道变多，用户互动的方式多样化，每天产生的内容信息成倍增长，监管的难度跟着变大、力度变大。

• 近年来相继有多家互联网平台因内容违规、传播迷信、版权问题、低俗、造假、与社会主义核心价值观不符等等问题被国家监管部门点名、约谈、下架、关停等处罚。

  1、2019年06月网易云音乐下架整该，下架原因“内容低俗、色情传播、版权问题等”

  2、2019年07月小红书下架整改，下架原因“内容涉嫌违规，笔记代写、刷单成风、数据造假、谣言泛滥等问题”

• 除此之外，还有哔哩哔哩、喜马拉雅、荔枝FM、企鹅FM等等多个平台被勒令下架整改，可见国家对内容资讯传播把控的力度之大。

1.3、目的功能：

• 旨在将之家APP有关内容、图片、音视频的业务进行统一接入，统一管控，统一处理。引入机器识别，减少人力成本。同时使内容的管控更方便更准确，业务对接更快捷，减少站内出现敏感的内容，减少在内容审核方面的人力物力投入，减少因为“内容红线”导致的整改下架问题，积极响应监管部门号召，为营造一个良好，健康，积极的网络环境出一份力。

  
  image.png
  

  另外还包括水军识别、灌水识别、刷量识别、反扒识别等等

1.4、名词解释：

image.png

1.5、场景：

• 异步场景->(不要求风控直接响应，而是采用一种异步的方式将要打标的内容传给风控即可，这种场景一般适用于评论回复和发帖交流场景，比如论坛、评论、文章之类。一般分为“先发后审”和“先审后发”两种处理机制)
• 实时场景->(要求风控直接响应，并且要求快速，这种场景一般适用于IM聊天和直播弹幕之类场景。要求实时性比较高)

更多场景：

• 同盾 https://dun.163.com/
• 蚁盾 https://sec.xiaodun.com/?r=pp

1.6、原料：**文本内容、图片、音频、视频

• 内容
• 图片->图文转换(文字抽取)->内容
• 音频->音频转换(文字转换)->内容
• 视频-编解码\视频切帧\水印处理等->图片->扫描->内容 FFmpeg教程

1.7、业务：论坛、口碑、问答、车友圈、搜索、汽车百科、旅行家等等

1.8、方案设计：

• 根据前期的技术调研和市面上解决方案的了解，最终决定以敏感词匹配为主（AC自动机），NLP处理为补充，外加其他手段（算法模型、频率、黑白名单等等）进行综合处理，将机器审核与人工复审相结合。机审作为初步的处理，快速响应业务及用户，人审作为对机审的误伤矫正。（一条内容必须先过机审，再过人审核，人工审核是非必要的，只是作为机审误伤的一种修正措施）

• 以下为敏感词匹配解决方案：

词库设计：（参照下图）各个业务方维护各自敏感词库，各词库将词分类，不同词库下词类性质等级不同（黑名单、灰名单）。每个词库下包含若干个词条，即：具体的敏感词。每个词条下包含若干个误伤白名单，用于减少某些语境下通过敏感词匹配带来的机审误伤。

业务方请求接口或MQ将要打标的内容输送至风控，风控打标系统将内容去匹配碰撞该业务方下对应的敏感词库，打标后通过业务方提供的本业务回调接口对业务方进行打标结构回传，业务方接到回传结果自行处理，同时机器打标完之后需要将打标内容存至风控，用于内容审核系统读取。审核人员通过内容审核系统进行二次人工复审，对误伤内容进行修正处理。通过定时的离线统计产出周报，对敏感词进行微调处理，以达到降低误伤，提高机审准确率的目的。

1、词库类型：涉政、涉恐、涉黄、辱骂、广告、相似文本、舆情、联系方式、车黑车拖等等（分等级-黑、灰名单）
2、标签：通过、删除、待审、仅自己可见（描述内容的状态）
3、内容输入：业务ID、主贴ID、回复ID、内容、IP、userID、回调地址、sign、时间戳、扩展字段等等
4、内容输出：除原内容外+ label、casecode、keyword等等
5、审核方式：机器审核(必要的)+人工复审的方式（先机审再人审）

image.png

1.9、核心解决方案：**基于敏感词匹配+误伤白名单

• 核心->AC自动机 （字典树+失败指针）, 用来处理多模式串匹配的文本算法。简单的说就是敏感字符串匹配，将要检测的内容字符串与所维护的敏感词集合去匹配。

• 辅助->文本相似算法、水军模型、NLP、频率计算、其他数据资产等等

• AC自动机算法：百度百科-AC自动机算法 -> 主要依靠构造一个有限状态机（类似于在一个trie树中添加失败指针）来实现.这些失败指针使得匹配失败时不回溯，避免重复匹配前缀。

• 余弦相似度算法：百度百科-余弦相似度算法 - > 通过计算两个向量的夹角余弦值来评估其相似性（指向相等=1、反方向=-1、垂直=0）。其他文本相似度算法

1.10、那些常见的字符串算法：

• 字符串的匹配按匹配的方式大致可分为两种：单字符串匹配、多字符串匹配
  第一种：单字符串匹配（即：在主串中查找一个模式串是否存在）
  例：在“我是中国人，我爱中国”这句话中查找“中国”

相关算法：BF、RK、BM、KMP

1、BF：(Brute Force-暴力匹配算法)，模式串和主串的匹配过程（正序匹配），看作模式串在主串中不停地往后滑动的过程，并且以步长为1右移，直到匹配到。
时间复杂度：O(n*m)
场景：Java python的字符串indexOf都使用的这种暴力匹配的方式，虽然其效率不高，但是在日常开发中，绝大多数对比的字符串都不会太长，并且匹配到会跳出，而不是每次都全部匹配

2、RK: （Rabin-Karp算法），是BF算法的升级版，在BF算法的基础上引入hash算法，在匹配之前，先对比hash值，只有出现hash碰撞的时候才会去逐个比对字符，以减少字符之间的匹配次数。
时间复杂度：最好O(n) 最坏O(n*m)

3、BM: 在BF算法的基础上提升了滑动步长，减少了匹配次数。主要采用“坏字符规则”和“好后缀规则”。
时间复杂度：最好O(n/m) 最坏O(n*m)
场景：介于优秀的检索效率，BM算法经常被使用在工程软件上的快速查找功能上

4、KMP:（Knuth Morris Pratt算法）是BF的一种优化，以减少失败后的回溯提升效率。实质上KMP与BM本质是一样的。在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位。每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i
时间复杂度：O(m+n)
场景：工程软件、统计软件上

image.png

• 坏字符规则

坏字符：从模式串的末尾往前倒着匹配（逆序匹配），当我们发现某个字符无法匹配的时候。我们把这个没有匹配的字符叫作坏字符。

滑动步长：当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi

image.png

• 好后缀规则

好后缀：从模式串的末尾往前倒着匹配（逆序匹配），当我们发现某个字符可以匹配的时候。我们把这个没有匹配的字符叫作好后缀。

滑动步长：我们把已经匹配的 bc 叫作好后缀，记作{u}。我们拿它在模式串中查找，如果在模式串中找到了另一个跟{u}相匹配的子串{u}，那我们就将模式串滑动到子串{u}与主串中{u}对齐的位置。如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况

image.png

如何选择规则才能更效率？
我们需要分别计算出两者的滑动步长，取其中大的作为滑动的位数即可

• KMP算法：是对暴力匹配算法的一种优化，旨在匹配中遇到坏字符串时，将前边已经匹配好的好字符串找规律，以达到一次滑动多位，并且主串i不回溯的效果以减少匹配次数提高效率。

  
  image.png

1、暴力匹配的回溯问题->引出KMP

假设现在我们有这样一个问题：有一个文本串S=“s1s2s3 …sn”，和一个模式串P=“p1p2p3 …pn”，现在要查找P在S中的位置，怎么查找呢？

a、如果用暴力匹配的思路，我们假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
b、如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
c、如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯到本次失配起始字符的下一个字符，j 回溯到0。

案例：
主串：a b a b c a b c a c b a b
模式串：a b c a c

第一次匹配中，i从0开始，j从0开始。当i=2，j=2时匹配失败，此时i回溯到1，j回溯到0。

image.png

第二次匹配中，i从1开始，j从0开始。当i=1，j=0时匹配失败，此时i回溯到2，j回溯到0。

image.png
第三次匹配中，i从2开始，j从0开始。当i=6，j=4时匹配失败，此时i回溯到3，j回溯到0。
image.png

第四次匹配中，i从3开始，j从0开始。当i=3，j=0时匹配失败，此时i回溯到4，j回溯到0。

image.png
第五次匹配中，i从4开始，j从0开始。当i=4，j=0时匹配失败，此时i回溯到5，j回溯到0。
image.png
第六次匹配中，i从5开始，j从0开始。i=10，j=5，T中全部字符比较完，匹配成功，返回本次匹配起始位置下标i - j。（i=9和j=4的时候匹配成功，i和j会再加一次，所以i=10，j=5）
image.png

结论：可见，如果i已经匹配了一段字符后出现了失配的情况，i会重新回溯，j又从0开始比较。这样浪费的大量的时间。从第四次匹配开始，我们可以发现：i=3和j=0，i=4和j=0以及i=5和j=0是不必进行的，因为从第三次部分匹配过程中我们可以得出，主串中第3，4，5个字符必然是‘b’，‘c’，‘a’（即与模式串的第1，2，3个字符分别对应相等），而模式的首字符是‘a’，它分别与‘b’，‘c’不等，与‘a’相等。如果将模式向右滑动3个字符继续进行i=6和j=1时的字符比较，很明显会加快进程。这样就引出了我们的KMP算法，不回溯i，加快匹配效率

image.png

针对以上现象，我们发现，在移动的过程中，“abca”是好前缀，“b”是坏后缀。

image.png

我们可以想想，现在模式串中匹配上的串是“abca”，我们的滑动是将最前边的"a"和最后边的"a"重合。如果匹配上的串是“abab”呢，很明显我们的滑动是需要将最前边的"ab"和最后边的"ab"重合。所以说，具体滑动多少跟主串没有关系，跟模式串自身有关系。我们可否提前维护一下模式串中这样一种重叠关系来为KMP在比较时的滑动做支撑。

2、KMP算法 ：KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位。每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较。

image.png

其实，我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。（其实就是找好前缀的最长公共前后子缀串）

假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。

注意：这里还隐含了一个意思即“找最长公共前子后缀是在模式串中找，跟主串无关”

image.png

通过上边的比较，我们发现，其实KMP算法就是提前维护了模式串子串的公共前后子缀的数组，这个数组记录了模式串中每一种子缀下的最大公共前后缀的长度，一般我们称之为next[]数组，也叫跳出函数。它是KMP算法的核心，直接决定了滑动的位数，这个数组需要在比对前对模式串进行预计算得出。那么如何得出呢？

算法流程：

• 规定i是主串S的下标，j是模式P的下标。现在假设现在主串S匹配到 i 位置，模式串P匹配到 j 位置。
• 如果j = -1，则i++，j++，继续匹配下一个字符；
• 如果S[i] = P[j]，则i++，j++，继续匹配下一个字符；
• 如果j != -1，且S[i] != P[j]，则 i 不变，j = next[j]。此举意味着失配时，接下来模式串P要相对于主串S向右移动j - next [j] 位。（其实就是上边的j-k）
  可能大家看到上边的流程会有疑惑？
• 1、next是什么？怎么来的？
  首先我们来解释一个名词：最长公共前后缀。假设有一个串P=“p0p1p2 …pj-1pj”。如果存在p0p1…pk-1pk = pj-kpj-k+1…pj-1pj，我们就说在P串中有一个最大长度为k+1的公共前后缀。
• 2、如何找前后缀？
  找前缀时，要找除了最后一个字符的所有子串。
  找后缀时，要找除了第一个字符的所有子串。

假如现在有模式串P=abaabca，各个子串的最大公共前后缀长度如下表所示：

image.png

这样，公共前后缀最长长度就会和串P的每个字符产生一种对应关系：

image.png

这个表的含义是在当前字符作为最后一个字符时，当前子串所拥有的公共前后缀最长长度。例如当c作为最后一个字符时，当前子串abaabc并没有公共前后缀。

其实就是能够维护pattern[i]的真后缀的最长前缀长度的数组（其实就是维护最长公共前后缀的长度数组）

next数组：通过上边这个表来引出next数组，next 数组的值是除当前字符外（注意不包括当前字符）的公共前后缀最长长度，相当于把上表做一个变形，将表中公共前后缀最长长度全部右移一位，第一个值赋为-1。例如c对应next值的意义是，c之前（不包括c）的子串abaab所拥有的公共前后缀最长长度为2，我们称next数组中的值为失效函数值，也就是c的失效函数值为2。

image.png

• 3、理解了next数组，那就来体验一下KMP算法的流程：现在有主串S：ababcabcacbab，模式串P：abcac。i从0开始，j也从0开始。
  根据上述方法可以知道，P的中每个字符对应的失效函数值为：

  
  image.png
  

  第一次匹配中，i从0开始，j从0开始。当i=2，j=2时匹配失败，此时i不动，next[j]=next[2]=0，接下来模式串P要相对于主串S向右移动 j - next [j] = 2 位，j回溯到0。

  
  image.png
  第二次匹配中，i从2开始，j从0开始。当i=6，j=4时匹配失败，此时i不动，next[j]=next[4]=1，接下来模式串P要相对于主串S向右移动 j - next [j] = 3位，j回溯到1。
  image.png
  第三次匹配中，i从6开始，j从1开始。当i=10，j=5时匹配成功，返回i - j = 5。
  image.png

当主串S与模式串P失配时，i不回溯，模式串P向右移动j - next[j]即可

KMP的next数组告诉我们：当模式串中的某个字符跟主串中的某个字符失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟主串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟主串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。

第二种：多字符串匹配（即：在模式串中查找多个字词或者多段内容是否存在）

例1：输入“中国”，找出集合中“中国”、“中国人”、“中国军人”、“中国海军”、“中国地图”等等。
例2：在“我是中国人，我爱中国”这句话中同时查找“我”、“中国”、“中国人”。

相关算法：Trie树（字典树）、AC自动机

Trie树（字典树）：它是一个树形结构。一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

特点：根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串.（最后红节点代表一个完整字符串的结束，一般会在这个节点中存储一些其他信息来完成一些业务场景需求）

例：字符串：how，hi，her，hello，so，see 构建的字典树如下图

image.png
image.png

使用场景：

主要使用在一些搜索场景中，比如我们熟知的goole、百度、商城的商品搜索等等，他们均是在以Tire树基础上做了优化扩展来实现搜索时的内容提示

image.png

树的形状及构建过程：

比如现在我们有以下字符串：how，hi，her，hello，so，see。 我们希望在里面多次查找某个字符串是否存在，如果每次查找，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那效率就比较低。我们看看Trie是怎么提升效率的。

先将字符串：how，hi，her，hello，so，see 构建一棵Trie树

image.png

查找过程：即将模式串进行字符分割，然后按顺序从根结点开始匹配。比如我们要查找字符串"he",那我们将要查找的字符串分割成单个的字符 h，e，然后从 Trie 树的根节点开始匹配。

AC自动机：其实就是树形结构（Trie）的一个KMP算法，核心要点即Trie树加fair失败指针。

一个英语字典我们应该怎么存储查询效率才会更高？为什么使用Trie存储而不是数组和链表或者其他树？

1数组：因为敏感词长短不一，使用数组存储不能使用索引进行精确的查找；
2链表：链表的查询遍历需要从头开始，查询效率底下；
3其他树：其他树没有Trie树公共前缀的特点，并且也不适合（比如二叉树）。

1、AC自动机是在Trie树基础上的一个扩展。
P {he、she、hers、his}

image.png
2、在预处理树的时候需要采用BFS算法的遍历顺序构建fair指针。深度遍历(DFS)和广度遍历(BFS)
image.png
3、fair指针的作用就是利用其最长后缀的特性避免在字符串检索失败时进行重溯。
什么是fair指针？如何构筑？它的目的和意义是什么？如何使用？
image.png
3.1、上图黑色的线是我们构建的Trie树，红色虚线就是这个树中的失败指针。
3.2、在这个Trie树中，如果某一个节点i它的fair指针是j的话，那么就说word[j]是word[i]的最长后缀。
3.3、什么是word？对于节点6而言，word[6]就是“sh”，word[8]就是“his”。
3.4、如何理解word[j]是word[i]的最长后缀？
word[6]的失败指针是word[2], “h”是“sh”的最长后缀（真后缀，不包括本身）
word[9]的失败指针是word[4]，“he”是“she”的最长后缀
3.5、root节点的（直接）子节点的失败指针是root；后缀为空（它的任何真后缀在这个树中不存在）的节点的失败指针是root，比如：节点e、节点r、节点i。
3.6、什么是失败指针？
在了解什么是失败指针之前，我们需要先知道fafair：fafair即父亲节点的失败指针。

失败指针的判定需要借助fafair，我们要找一个节点的失败指针，首先、需要获取到该节点的fafair，其次、查看这个fafair节点有没有一个指向与该节点相同字符的儿子，如果没有其失败指针指向根结点，如果有就指向当前节点。第一层节点的失败指针是根结点。

image.png

这也是为什么在构建失败指针的时候，要采用BFS层次遍历？因为当前节点失败指针的判断需要依据父节点的失败指针fafair。

3.7、9号节点为什么有两个单词？

因为9号节点存在后缀“he”，刚好就是4号节点，并且4号节点“he”也实实在在是一个单词。（其实一个节点在记录单词的时候，不单单记录它自身的单词，还会记录它fair指针节点的单词）

我们可以这样理解，然后“she”和“he”都是敏感词，那么我们找到“she”的话，肯定也就找到“he”了

3.8、在字符串 S “ahishers” 中查找P {he、she、hers、his}

image.png

4、AC coding：构造一棵Trie树，构造失败指针和模式匹配过程

     /**
     * 采用AC自动机树形结构匹配
     */
    @Test
    public void  AcWord(){
            //编译自动机
        WordTable table = WordTable.compile(list);
        //查找
        System.out.println(table.search(content));
    }

1.11、逻辑架构设计：

image.png

1.12、内容打标流程设计：

• 1、风控运营：风控运营为业务开启接入权限（businessID、key以及词库平台和审核平台的登陆权限），业务为风控提供符合风控统一规范的回调地址（callBackUrl）
• 2、业务运营：业务运营登陆词库运营系统进行本业务下有效敏感词和黑白名单的维护运营工作
• 3、用户：普通用户的请求会进入风控打标
• 4、兼职审核人员：审核人员对机器打标后的数据进行有选择性的人工复审

image.png

1.13、人工审核：

人工审核主要是为了弥补机器打标不能结合上下文语境带来的误伤问题，通过人工的二次复审来对误伤的内容进行修复。当然，人工复审也不是审核所有内容，根据业务要求，大部分只会聚集比较敏感重要，出现误伤带来严重危害的内容。一般优先处理涉政、涉恐、涉黄、涉暴的敏感内容，其他内容根据情况酌情进行人工审核。

类型：涉政、涉恐、涉黄、辱骂、广告、相似文本、舆情、联系方式、车黑车拖等等（分等级-黑、灰名单）
标签：通过、删除、待审、仅自己可见（描述内容的状态）
衍生标签：通过->删除、通过->待审、删除->通过、删除->待审、待审->通过、待审->删除… （描述内容的变更过程，可以直接反应打标的准确性）
通过实时计算+离线统计产出审核周报及看板，对模型和敏感词进行微调，减少误删

image.png