前言：了解風(fēng)控

• 什么是風(fēng)控？
  簡單的說就是風(fēng)險(xiǎn)控制。風(fēng)控是一個(gè)很籠統(tǒng)的概述，不同的行業(yè)、不同的場景，所需要做的風(fēng)控手動(dòng)也有很大的區(qū)別，比如金融風(fēng)控、內(nèi)容風(fēng)控、活動(dòng)風(fēng)控等等。不同的場景下也需要不同的風(fēng)控策略。

什么風(fēng)險(xiǎn)，怎么控制？

• 其實(shí)這里的風(fēng)險(xiǎn)就是一種可能，一種作弊場景。而控制就是面對這種作弊場景的一種或多種解決方案。

  
  
  image.png
  
  

  除此之外，還有信貸風(fēng)控、金融風(fēng)控、活動(dòng)營銷風(fēng)控、網(wǎng)絡(luò)欺詐（殺豬盤）等等

1、內(nèi)容(合規(guī))反作弊：

1.1、生活中的內(nèi)容風(fēng)控：

image.png

1.2、背景：

• 隨著移動(dòng)互聯(lián)網(wǎng)的蓬勃發(fā)展，人們獲取信息資訊的渠道變多，用戶互動(dòng)的方式多樣化，每天產(chǎn)生的內(nèi)容信息成倍增長，監(jiān)管的難度跟著變大、力度變大。

• 近年來相繼有多家互聯(lián)網(wǎng)平臺(tái)因內(nèi)容違規(guī)、傳播迷信、版權(quán)問題、低俗、造假、與社會(huì)主義核心價(jià)值觀不符等等問題被國家監(jiān)管部門點(diǎn)名、約談、下架、關(guān)停等處罰。

  1、2019年06月網(wǎng)易云音樂下架整該，下架原因“內(nèi)容低俗、色情傳播、版權(quán)問題等”

  2、2019年07月小紅書下架整改，下架原因“內(nèi)容涉嫌違規(guī)，筆記代寫、刷單成風(fēng)、數(shù)據(jù)造假、謠言泛濫等問題”

• 除此之外，還有嗶哩嗶哩、喜馬拉雅、荔枝FM、企鵝FM等等多個(gè)平臺(tái)被勒令下架整改，可見國家對內(nèi)容資訊傳播把控的力度之大。

1.3、目的功能：

• 旨在將之家APP有關(guān)內(nèi)容、圖片、音視頻的業(yè)務(wù)進(jìn)行統(tǒng)一接入，統(tǒng)一管控，統(tǒng)一處理。引入機(jī)器識別，減少人力成本。同時(shí)使內(nèi)容的管控更方便更準(zhǔn)確，業(yè)務(wù)對接更快捷，減少站內(nèi)出現(xiàn)敏感的內(nèi)容，減少在內(nèi)容審核方面的人力物力投入，減少因?yàn)椤皟?nèi)容紅線”導(dǎo)致的整改下架問題，積極響應(yīng)監(jiān)管部門號召，為營造一個(gè)良好，健康，積極的網(wǎng)絡(luò)環(huán)境出一份力。

  
  
  image.png
  
  

  另外還包括水軍識別、灌水識別、刷量識別、反扒識別等等

1.4、名詞解釋：

image.png

1.5、場景：

• 異步場景->(不要求風(fēng)控直接響應(yīng)，而是采用一種異步的方式將要打標(biāo)的內(nèi)容傳給風(fēng)控即可，這種場景一般適用于評論回復(fù)和發(fā)帖交流場景，比如論壇、評論、文章之類。一般分為“先發(fā)后審”和“先審后發(fā)”兩種處理機(jī)制)
• 實(shí)時(shí)場景->(要求風(fēng)控直接響應(yīng)，并且要求快速，這種場景一般適用于IM聊天和直播彈幕之類場景。要求實(shí)時(shí)性比較高)

更多場景：

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

1.6、原料：**文本內(nèi)容、圖片、音頻、視頻

• 內(nèi)容
• 圖片->圖文轉(zhuǎn)換(文字抽取)->內(nèi)容
• 音頻->音頻轉(zhuǎn)換(文字轉(zhuǎn)換)->內(nèi)容
• 視頻-編解碼\視頻切幀\水印處理等->圖片->掃描->內(nèi)容 FFmpeg教程

1.7、業(yè)務(wù)：論壇、口碑、問答、車友圈、搜索、汽車百科、旅行家等等

1.8、方案設(shè)計(jì)：

• 根據(jù)前期的技術(shù)調(diào)研和市面上解決方案的了解，最終決定以敏感詞匹配為主（AC自動(dòng)機(jī)），NLP處理為補(bǔ)充，外加其他手段（算法模型、頻率、黑白名單等等）進(jìn)行綜合處理，將機(jī)器審核與人工復(fù)審相結(jié)合。機(jī)審作為初步的處理，快速響應(yīng)業(yè)務(wù)及用戶，人審作為對機(jī)審的誤傷矯正。（一條內(nèi)容必須先過機(jī)審，再過人審核，人工審核是非必要的，只是作為機(jī)審誤傷的一種修正措施）

• 以下為敏感詞匹配解決方案：

詞庫設(shè)計(jì)：（參照下圖）各個(gè)業(yè)務(wù)方維護(hù)各自敏感詞庫，各詞庫將詞分類，不同詞庫下詞類性質(zhì)等級不同（黑名單、灰名單）。每個(gè)詞庫下包含若干個(gè)詞條，即：具體的敏感詞。每個(gè)詞條下包含若干個(gè)誤傷白名單，用于減少某些語境下通過敏感詞匹配帶來的機(jī)審誤傷。

業(yè)務(wù)方請求接口或MQ將要打標(biāo)的內(nèi)容輸送至風(fēng)控，風(fēng)控打標(biāo)系統(tǒng)將內(nèi)容去匹配碰撞該業(yè)務(wù)方下對應(yīng)的敏感詞庫，打標(biāo)后通過業(yè)務(wù)方提供的本業(yè)務(wù)回調(diào)接口對業(yè)務(wù)方進(jìn)行打標(biāo)結(jié)構(gòu)回傳，業(yè)務(wù)方接到回傳結(jié)果自行處理，同時(shí)機(jī)器打標(biāo)完之后需要將打標(biāo)內(nèi)容存至風(fēng)控，用于內(nèi)容審核系統(tǒng)讀取。審核人員通過內(nèi)容審核系統(tǒng)進(jìn)行二次人工復(fù)審，對誤傷內(nèi)容進(jìn)行修正處理。通過定時(shí)的離線統(tǒng)計(jì)產(chǎn)出周報(bào)，對敏感詞進(jìn)行微調(diào)處理，以達(dá)到降低誤傷，提高機(jī)審準(zhǔn)確率的目的。

1、詞庫類型：涉政、涉恐、涉黃、辱罵、廣告、相似文本、輿情、聯(lián)系方式、車黑車拖等等（分等級-黑、灰名單）
2、標(biāo)簽：通過、刪除、待審、僅自己可見（描述內(nèi)容的狀態(tài)）
3、內(nèi)容輸入：業(yè)務(wù)ID、主貼ID、回復(fù)ID、內(nèi)容、IP、userID、回調(diào)地址、sign、時(shí)間戳、擴(kuò)展字段等等
4、內(nèi)容輸出：除原內(nèi)容外+ label、casecode、keyword等等
5、審核方式：機(jī)器審核(必要的)+人工復(fù)審的方式（先機(jī)審再人審）

image.png

1.9、核心解決方案：**基于敏感詞匹配+誤傷白名單

• 核心->AC自動(dòng)機(jī) （字典樹+失敗指針）, 用來處理多模式串匹配的文本算法。簡單的說就是敏感字符串匹配，將要檢測的內(nèi)容字符串與所維護(hù)的敏感詞集合去匹配。

• 輔助->文本相似算法、水軍模型、NLP、頻率計(jì)算、其他數(shù)據(jù)資產(chǎn)等等

• AC自動(dòng)機(jī)算法：百度百科-AC自動(dòng)機(jī)算法 -> 主要依靠構(gòu)造一個(gè)有限狀態(tài)機(jī)（類似于在一個(gè)trie樹中添加失敗指針）來實(shí)現(xiàn).這些失敗指針使得匹配失敗時(shí)不回溯，避免重復(fù)匹配前綴。

• 余弦相似度算法：百度百科-余弦相似度算法 - > 通過計(jì)算兩個(gè)向量的夾角余弦值來評估其相似性（指向相等=1、反方向=-1、垂直=0）。其他文本相似度算法

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

• 字符串的匹配按匹配的方式大致可分為兩種：單字符串匹配、多字符串匹配
  第一種：單字符串匹配（即：在主串中查找一個(gè)模式串是否存在）
  例：在“我是中國人，我愛中國”這句話中查找“中國”

相關(guān)算法：BF、RK、BM、KMP

1、BF：(Brute Force-暴力匹配算法)，模式串和主串的匹配過程（正序匹配），看作模式串在主串中不停地往后滑動(dòng)的過程，并且以步長為1右移，直到匹配到。
時(shí)間復(fù)雜度：O(n*m)
場景：Java python的字符串indexOf都使用的這種暴力匹配的方式，雖然其效率不高，但是在日常開發(fā)中，絕大多數(shù)對比的字符串都不會(huì)太長，并且匹配到會(huì)跳出，而不是每次都全部匹配

2、RK: （Rabin-Karp算法），是BF算法的升級版，在BF算法的基礎(chǔ)上引入hash算法，在匹配之前，先對比hash值，只有出現(xiàn)hash碰撞的時(shí)候才會(huì)去逐個(gè)比對字符，以減少字符之間的匹配次數(shù)。
時(shí)間復(fù)雜度：最好O(n) 最壞O(n*m)

3、BM: 在BF算法的基礎(chǔ)上提升了滑動(dòng)步長，減少了匹配次數(shù)。主要采用“壞字符規(guī)則”和“好后綴規(guī)則”。
時(shí)間復(fù)雜度：最好O(n/m) 最壞O(n*m)
場景：介于優(yōu)秀的檢索效率，BM算法經(jīng)常被使用在工程軟件上的快速查找功能上

4、KMP:（Knuth Morris Pratt算法）是BF的一種優(yōu)化，以減少失敗后的回溯提升效率。實(shí)質(zhì)上KMP與BM本質(zhì)是一樣的。在模式串和主串匹配的過程中，當(dāng)遇到壞字符后，對于已經(jīng)比對過的好前綴，能否找到一種規(guī)律，將模式串一次性滑動(dòng)很多位。每當(dāng)從某個(gè)起始位置開始一趟比較后，在匹配過程中出現(xiàn)失配，不回溯i
時(shí)間復(fù)雜度：O(m+n)
場景：工程軟件、統(tǒng)計(jì)軟件上

image.png

• 壞字符規(guī)則

壞字符：從模式串的末尾往前倒著匹配（逆序匹配），當(dāng)我們發(fā)現(xiàn)某個(gè)字符無法匹配的時(shí)候。我們把這個(gè)沒有匹配的字符叫作壞字符。

滑動(dòng)步長：當(dāng)發(fā)生不匹配的時(shí)候，我們把壞字符對應(yīng)的模式串中的字符下標(biāo)記作 si。如果壞字符在模式串中存在，我們把這個(gè)壞字符在模式串中的下標(biāo)記作 xi。如果不存在，我們把 xi 記作 -1。那模式串往后移動(dòng)的位數(shù)就等于 si-xi

image.png

• 好后綴規(guī)則

好后綴：從模式串的末尾往前倒著匹配（逆序匹配），當(dāng)我們發(fā)現(xiàn)某個(gè)字符可以匹配的時(shí)候。我們把這個(gè)沒有匹配的字符叫作好后綴。

滑動(dòng)步長：我們把已經(jīng)匹配的 bc 叫作好后綴，記作{u}。我們拿它在模式串中查找，如果在模式串中找到了另一個(gè)跟{u}相匹配的子串{u}，那我們就將模式串滑動(dòng)到子串{u}與主串中{u}對齊的位置。如果在模式串中找不到另一個(gè)等于{u}的子串，我們就直接將模式串，滑動(dòng)到主串中{u}的后面，因?yàn)橹暗娜魏我淮瓮蠡瑒?dòng)，都沒有匹配主串中{u}的情況

image.png

如何選擇規(guī)則才能更效率？
我們需要分別計(jì)算出兩者的滑動(dòng)步長，取其中大的作為滑動(dòng)的位數(shù)即可

• KMP算法：是對暴力匹配算法的一種優(yōu)化，旨在匹配中遇到壞字符串時(shí)，將前邊已經(jīng)匹配好的好字符串找規(guī)律，以達(dá)到一次滑動(dòng)多位，并且主串i不回溯的效果以減少匹配次數(shù)提高效率。

  
  
  image.png

1、暴力匹配的回溯問題->引出KMP

假設(shè)現(xiàn)在我們有這樣一個(gè)問題：有一個(gè)文本串S=“s1s2s3 …sn”，和一個(gè)模式串P=“p1p2p3 …pn”，現(xiàn)在要查找P在S中的位置，怎么查找呢？

a、如果用暴力匹配的思路，我們假設(shè)現(xiàn)在文本串S匹配到 i 位置，模式串P匹配到 j 位置，則有：
b、如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++，繼續(xù)匹配下一個(gè)字符；
c、如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相當(dāng)于每次匹配失敗時(shí)，i 回溯到本次失配起始字符的下一個(gè)字符，j 回溯到0。

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

第一次匹配中，i從0開始，j從0開始。當(dāng)i=2，j=2時(shí)匹配失敗，此時(shí)i回溯到1，j回溯到0。

image.png

第二次匹配中，i從1開始，j從0開始。當(dāng)i=1，j=0時(shí)匹配失敗，此時(shí)i回溯到2，j回溯到0。

image.png

image.png

第四次匹配中，i從3開始，j從0開始。當(dāng)i=3，j=0時(shí)匹配失敗，此時(shí)i回溯到4，j回溯到0。

image.png

image.png

image.png

結(jié)論：可見，如果i已經(jīng)匹配了一段字符后出現(xiàn)了失配的情況，i會(huì)重新回溯，j又從0開始比較。這樣浪費(fèi)的大量的時(shí)間。從第四次匹配開始，我們可以發(fā)現(xiàn)：i=3和j=0，i=4和j=0以及i=5和j=0是不必進(jìn)行的，因?yàn)閺牡谌尾糠制ヅ溥^程中我們可以得出，主串中第3，4，5個(gè)字符必然是‘b’，‘c’，‘a(chǎn)’（即與模式串的第1，2，3個(gè)字符分別對應(yīng)相等），而模式的首字符是‘a(chǎn)’，它分別與‘b’，‘c’不等，與‘a(chǎn)’相等。如果將模式向右滑動(dòng)3個(gè)字符繼續(xù)進(jìn)行i=6和j=1時(shí)的字符比較，很明顯會(huì)加快進(jìn)程。這樣就引出了我們的KMP算法，不回溯i，加快匹配效率

image.png

針對以上現(xiàn)象，我們發(fā)現(xiàn)，在移動(dòng)的過程中，“abca”是好前綴，“b”是壞后綴。

image.png

我們可以想想，現(xiàn)在模式串中匹配上的串是“abca”，我們的滑動(dòng)是將最前邊的"a"和最后邊的"a"重合。如果匹配上的串是“abab”呢，很明顯我們的滑動(dòng)是需要將最前邊的"ab"和最后邊的"ab"重合。所以說，具體滑動(dòng)多少跟主串沒有關(guān)系，跟模式串自身有關(guān)系。我們可否提前維護(hù)一下模式串中這樣一種重疊關(guān)系來為KMP在比較時(shí)的滑動(dòng)做支撐。

2、KMP算法 ：KMP 算法就是在試圖尋找一種規(guī)律：在模式串和主串匹配的過程中，當(dāng)遇到壞字符后，對于已經(jīng)比對過的好前綴，能否找到一種規(guī)律，將模式串一次性滑動(dòng)很多位。每當(dāng)從某個(gè)起始位置開始一趟比較后，在匹配過程中出現(xiàn)失配，不回溯i，而是利用已經(jīng)得到的部分匹配結(jié)果，將一種假想的位置定位“指針”在模式上向右滑動(dòng)盡可能遠(yuǎn)的一段距離到某個(gè)位置后，繼續(xù)按規(guī)則進(jìn)行下一次的比較。

image.png

其實(shí)，我們只需要拿好前綴本身，在它的后綴子串中，查找最長的那個(gè)可以跟好前綴的前綴子串匹配的。（其實(shí)就是找好前綴的最長公共前后子綴串）

假設(shè)最長的可匹配的那部分前綴子串是{v}，長度是 k。我們把模式串一次性往后滑動(dòng) j-k 位，相當(dāng)于，每次遇到壞字符的時(shí)候，我們就把 j 更新為 k，i 不變，然后繼續(xù)比較。

注意：這里還隱含了一個(gè)意思即“找最長公共前子后綴是在模式串中找，跟主串無關(guān)”

image.png

通過上邊的比較，我們發(fā)現(xiàn)，其實(shí)KMP算法就是提前維護(hù)了模式串子串的公共前后子綴的數(shù)組，這個(gè)數(shù)組記錄了模式串中每一種子綴下的最大公共前后綴的長度，一般我們稱之為next[]數(shù)組，也叫跳出函數(shù)。它是KMP算法的核心，直接決定了滑動(dòng)的位數(shù)，這個(gè)數(shù)組需要在比對前對模式串進(jìn)行預(yù)計(jì)算得出。那么如何得出呢？

算法流程：

• 規(guī)定i是主串S的下標(biāo)，j是模式P的下標(biāo)?，F(xiàn)在假設(shè)現(xiàn)在主串S匹配到 i 位置，模式串P匹配到 j 位置。
• 如果j = -1，則i++，j++，繼續(xù)匹配下一個(gè)字符；
• 如果S[i] = P[j]，則i++，j++，繼續(xù)匹配下一個(gè)字符；
• 如果j != -1，且S[i] != P[j]，則 i 不變，j = next[j]。此舉意味著失配時(shí)，接下來模式串P要相對于主串S向右移動(dòng)j - next [j] 位。（其實(shí)就是上邊的j-k）
  可能大家看到上邊的流程會(huì)有疑惑？
• 1、next是什么？怎么來的？
  首先我們來解釋一個(gè)名詞：最長公共前后綴。假設(shè)有一個(gè)串P=“p0p1p2 …pj-1pj”。如果存在p0p1…pk-1pk = pj-kpj-k+1…pj-1pj，我們就說在P串中有一個(gè)最大長度為k+1的公共前后綴。
• 2、如何找前后綴？
  找前綴時(shí)，要找除了最后一個(gè)字符的所有子串。
  找后綴時(shí)，要找除了第一個(gè)字符的所有子串。

假如現(xiàn)在有模式串P=abaabca，各個(gè)子串的最大公共前后綴長度如下表所示：

image.png

這樣，公共前后綴最長長度就會(huì)和串P的每個(gè)字符產(chǎn)生一種對應(yīng)關(guān)系：

image.png

這個(gè)表的含義是在當(dāng)前字符作為最后一個(gè)字符時(shí)，當(dāng)前子串所擁有的公共前后綴最長長度。例如當(dāng)c作為最后一個(gè)字符時(shí)，當(dāng)前子串a(chǎn)baabc并沒有公共前后綴。

其實(shí)就是能夠維護(hù)pattern[i]的真后綴的最長前綴長度的數(shù)組（其實(shí)就是維護(hù)最長公共前后綴的長度數(shù)組）

next數(shù)組：通過上邊這個(gè)表來引出next數(shù)組，next 數(shù)組的值是除當(dāng)前字符外（注意不包括當(dāng)前字符）的公共前后綴最長長度，相當(dāng)于把上表做一個(gè)變形，將表中公共前后綴最長長度全部右移一位，第一個(gè)值賦為-1。例如c對應(yīng)next值的意義是，c之前（不包括c）的子串a(chǎn)baab所擁有的公共前后綴最長長度為2，我們稱next數(shù)組中的值為失效函數(shù)值，也就是c的失效函數(shù)值為2。

image.png

• 3、理解了next數(shù)組，那就來體驗(yàn)一下KMP算法的流程：現(xiàn)在有主串S：ababcabcacbab，模式串P：abcac。i從0開始，j也從0開始。
  根據(jù)上述方法可以知道，P的中每個(gè)字符對應(yīng)的失效函數(shù)值為：

  
  
  image.png
  
  

  第一次匹配中，i從0開始，j從0開始。當(dāng)i=2，j=2時(shí)匹配失敗，此時(shí)i不動(dòng)，next[j]=next[2]=0，接下來模式串P要相對于主串S向右移動(dòng) j - next [j] = 2 位，j回溯到0。

  
  
  image.png
  
  第二次匹配中，i從2開始，j從0開始。當(dāng)i=6，j=4時(shí)匹配失敗，此時(shí)i不動(dòng)，next[j]=next[4]=1，接下來模式串P要相對于主串S向右移動(dòng) j - next [j] = 3位，j回溯到1。
  
  image.png
  
  第三次匹配中，i從6開始，j從1開始。當(dāng)i=10，j=5時(shí)匹配成功，返回i - j = 5。
  
  image.png

當(dāng)主串S與模式串P失配時(shí)，i不回溯，模式串P向右移動(dòng)j - next[j]即可

KMP的next數(shù)組告訴我們：當(dāng)模式串中的某個(gè)字符跟主串中的某個(gè)字符失配時(shí)，模式串下一步應(yīng)該跳到哪個(gè)位置。如模式串中在j 處的字符跟主串在i 處的字符匹配失配時(shí)，下一步用next [j] 處的字符繼續(xù)跟主串i 處的字符匹配，相當(dāng)于模式串向右移動(dòng) j - next[j] 位。

第二種：多字符串匹配（即：在模式串中查找多個(gè)字詞或者多段內(nèi)容是否存在）

例1：輸入“中國”，找出集合中“中國”、“中國人”、“中國軍人”、“中國海軍”、“中國地圖”等等。
例2：在“我是中國人，我愛中國”這句話中同時(shí)查找“我”、“中國”、“中國人”。

相關(guān)算法：Trie樹（字典樹）、AC自動(dòng)機(jī)

Trie樹（字典樹）：它是一個(gè)樹形結(jié)構(gòu)。一種專門處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，用來解決在一組字符串集合中快速查找某個(gè)字符串的問題。Trie 樹的本質(zhì)，就是利用字符串之間的公共前綴，將重復(fù)的前綴合并在一起。

特點(diǎn)：根節(jié)點(diǎn)不包含任何信息。每個(gè)節(jié)點(diǎn)表示一個(gè)字符串中的字符，從根節(jié)點(diǎn)到紅色節(jié)點(diǎn)的一條路徑表示一個(gè)字符串.（最后紅節(jié)點(diǎn)代表一個(gè)完整字符串的結(jié)束，一般會(huì)在這個(gè)節(jié)點(diǎn)中存儲(chǔ)一些其他信息來完成一些業(yè)務(wù)場景需求）

例：字符串：how，hi，her，hello，so，see 構(gòu)建的字典樹如下圖

image.png

image.png

使用場景：

主要使用在一些搜索場景中，比如我們熟知的goole、百度、商城的商品搜索等等，他們均是在以Tire樹基礎(chǔ)上做了優(yōu)化擴(kuò)展來實(shí)現(xiàn)搜索時(shí)的內(nèi)容提示

image.png

樹的形狀及構(gòu)建過程：

比如現(xiàn)在我們有以下字符串：how，hi，her，hello，so，see。 我們希望在里面多次查找某個(gè)字符串是否存在，如果每次查找，都是拿要查找的字符串跟這 6 個(gè)字符串依次進(jìn)行字符串匹配，那效率就比較低。我們看看Trie是怎么提升效率的。

先將字符串：how，hi，her，hello，so，see 構(gòu)建一棵Trie樹

image.png

查找過程：即將模式串進(jìn)行字符分割，然后按順序從根結(jié)點(diǎn)開始匹配。比如我們要查找字符串"he",那我們將要查找的字符串分割成單個(gè)的字符 h，e，然后從 Trie 樹的根節(jié)點(diǎn)開始匹配。

AC自動(dòng)機(jī)：其實(shí)就是樹形結(jié)構(gòu)（Trie）的一個(gè)KMP算法，核心要點(diǎn)即Trie樹加fair失敗指針。

一個(gè)英語字典我們應(yīng)該怎么存儲(chǔ)查詢效率才會(huì)更高？為什么使用Trie存儲(chǔ)而不是數(shù)組和鏈表或者其他樹？

1數(shù)組：因?yàn)槊舾性~長短不一，使用數(shù)組存儲(chǔ)不能使用索引進(jìn)行精確的查找；
2鏈表：鏈表的查詢遍歷需要從頭開始，查詢效率底下；
3其他樹：其他樹沒有Trie樹公共前綴的特點(diǎn)，并且也不適合（比如二叉樹）。

1、AC自動(dòng)機(jī)是在Trie樹基礎(chǔ)上的一個(gè)擴(kuò)展。
P {he、she、hers、his}

image.png

image.png

image.png

失敗指針的判定需要借助fafair，我們要找一個(gè)節(jié)點(diǎn)的失敗指針，首先、需要獲取到該節(jié)點(diǎn)的fafair，其次、查看這個(gè)fafair節(jié)點(diǎn)有沒有一個(gè)指向與該節(jié)點(diǎn)相同字符的兒子，如果沒有其失敗指針指向根結(jié)點(diǎn)，如果有就指向當(dāng)前節(jié)點(diǎn)。第一層節(jié)點(diǎn)的失敗指針是根結(jié)點(diǎn)。

image.png

這也是為什么在構(gòu)建失敗指針的時(shí)候，要采用BFS層次遍歷？因?yàn)楫?dāng)前節(jié)點(diǎn)失敗指針的判斷需要依據(jù)父節(jié)點(diǎn)的失敗指針fafair。

3.7、9號節(jié)點(diǎn)為什么有兩個(gè)單詞？

因?yàn)?號節(jié)點(diǎn)存在后綴“he”，剛好就是4號節(jié)點(diǎn)，并且4號節(jié)點(diǎn)“he”也實(shí)實(shí)在在是一個(gè)單詞。（其實(shí)一個(gè)節(jié)點(diǎn)在記錄單詞的時(shí)候，不單單記錄它自身的單詞，還會(huì)記錄它fair指針節(jié)點(diǎn)的單詞）

我們可以這樣理解，然后“she”和“he”都是敏感詞，那么我們找到“she”的話，肯定也就找到“he”了

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

image.png

4、AC coding：構(gòu)造一棵Trie樹，構(gòu)造失敗指針和模式匹配過程

     /**
     * 采用AC自動(dòng)機(jī)樹形結(jié)構(gòu)匹配
     */
    @Test
    public void  AcWord(){
            //編譯自動(dòng)機(jī)
        WordTable table = WordTable.compile(list);
        //查找
        System.out.println(table.search(content));
    }

1.11、邏輯架構(gòu)設(shè)計(jì)：

image.png

1.12、內(nèi)容打標(biāo)流程設(shè)計(jì)：

• 1、風(fēng)控運(yùn)營：風(fēng)控運(yùn)營為業(yè)務(wù)開啟接入權(quán)限（businessID、key以及詞庫平臺(tái)和審核平臺(tái)的登陸權(quán)限），業(yè)務(wù)為風(fēng)控提供符合風(fēng)控統(tǒng)一規(guī)范的回調(diào)地址（callBackUrl）
• 2、業(yè)務(wù)運(yùn)營：業(yè)務(wù)運(yùn)營登陸詞庫運(yùn)營系統(tǒng)進(jìn)行本業(yè)務(wù)下有效敏感詞和黑白名單的維護(hù)運(yùn)營工作
• 3、用戶：普通用戶的請求會(huì)進(jìn)入風(fēng)控打標(biāo)
• 4、兼職審核人員：審核人員對機(jī)器打標(biāo)后的數(shù)據(jù)進(jìn)行有選擇性的人工復(fù)審

image.png

1.13、人工審核：

人工審核主要是為了彌補(bǔ)機(jī)器打標(biāo)不能結(jié)合上下文語境帶來的誤傷問題，通過人工的二次復(fù)審來對誤傷的內(nèi)容進(jìn)行修復(fù)。當(dāng)然，人工復(fù)審也不是審核所有內(nèi)容，根據(jù)業(yè)務(wù)要求，大部分只會(huì)聚集比較敏感重要，出現(xiàn)誤傷帶來嚴(yán)重危害的內(nèi)容。一般優(yōu)先處理涉政、涉恐、涉黃、涉暴的敏感內(nèi)容，其他內(nèi)容根據(jù)情況酌情進(jìn)行人工審核。

類型：涉政、涉恐、涉黃、辱罵、廣告、相似文本、輿情、聯(lián)系方式、車黑車拖等等（分等級-黑、灰名單）
標(biāo)簽：通過、刪除、待審、僅自己可見（描述內(nèi)容的狀態(tài)）
衍生標(biāo)簽：通過->刪除、通過->待審、刪除->通過、刪除->待審、待審->通過、待審->刪除… （描述內(nèi)容的變更過程，可以直接反應(yīng)打標(biāo)的準(zhǔn)確性）
通過實(shí)時(shí)計(jì)算+離線統(tǒng)計(jì)產(chǎn)出審核周報(bào)及看板，對模型和敏感詞進(jìn)行微調(diào)，減少誤刪

image.png