vivo 敏感詞匹配系統的設計與實踐

• 2021 年 12 月 6 日
• 筆記
• 敏感詞, 服務器, 架構設計, 模式匹配

一、前言

諦聽系統是vivo的內容審核平台，保障了vivo各互聯網產品持續健康的發展。諦聽支持審核多種內容類型，但日常主要審核的內容是文本，下圖是一個完整的文本審核流程，包括名單匹配、敏感詞匹配、AI機器審核、人工審核四個環節。待審核文本需要順次通過名單匹配、敏感詞匹配、AI機器審核三個流程，若結果為嫌疑則需要人工審核，否則將直接給出確定的結果。

敏感詞匹配功能可以迅速地匹配文本中的敏感詞彙，算法平均耗時為50ms，因其簡單、快速、直接、靈活的特點，成為了審核人員對抗垃圾文本的利器。然而身處信息爆炸時代的網民們非常「優秀」，他們源源不斷的發明各種新詞、諧音詞來繞過敏感詞檢測。例如某些用戶會使用「啋票」、「采漂」等詞彙來規避敏感詞「彩票」，其中「啋票」不僅是諧音詞，還包含多音字，常規的模式匹配算法很難保證完全命中。這不僅給運營規則帶來挑戰，也對匹配算法的精準度、漏殺率提出了要求。

本文將從算法選型入手，結合兩個實際場景來介紹諦聽系統的敏感詞匹配算法。其中第二節介紹了底層算法選型思路，第三節介紹了兩種實際場景下提升敏感詞精準度、降低漏殺率的方案。

二、算法選型

敏感詞匹配功能依託於模式匹配算法。模式匹配的定義是，給定一個子串，在某個字符串中找出與該子串相同的所有子串。其中給定的子串被稱為模式串，被匹配的字符串被稱為目標串。基於多個模式串進行匹配的算法被稱為多模式匹配算法，目前成熟的多模式匹配算法有AC自動機和WM。

2.1 多模式匹配算法對比

諦聽的敏感詞匹配業務有如下特點：

1）詞庫量大，需要維護和加載百萬級別的詞庫（模式串）；

2）敏感詞與業務特性、國家政策相關性強，無法統一約定長度、前綴等特徵。

WM算法對模式串的長度和前綴存在一定的要求，可能會影響業務的使用。雖然AC自動機加載耗時長，內存佔用大，但敏感詞加載並不頻繁，且服務器內存資源充足，所以我們最終選用AC自動機作為底層算法。

2.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」進行匹配的過程。

三、諦聽系統實踐

諦聽系統基於AC自動機算法構建了一套敏感詞匹配服務，將敏感詞作為模式串，文本內容作為目標串，可以實現常用的中、英文敏感詞匹配。但是實際的業務有很多細分的場景，普通的AC自動機算法已不能滿足業務使用需求，因此我們探索了組合敏感詞匹配和拼音敏感詞匹配兩種匹配方式，下面分別介紹。

3.1 組合敏感詞

常規的敏感詞匹配算法通常匹配單個詞或者短句，但某些詞單獨出現時並不違規，只有在與幾個特定的詞同時出現時，才能判定為違規。例如「澳門」、「博彩」、「網站」，這幾個詞，單獨出現都是沒問題的，但是在這句話中：「歡迎登錄澳門XX博彩官方網站」，就是違規的賭博廣告。針對這樣的場景，我們實現了「組合敏感詞」匹配方案，運營人員可以將這幾個詞配置成一個組合「澳門+博彩+網站」，只有這三個詞同時出現時，敏感詞服務才會判定這個組合命中。

組合敏感詞的匹配算法依然基於AC自動機算法。由於AC自動機只能判斷單個詞的命中情況，因此我們將組合敏感詞分割成單個敏感詞，並維護各敏感詞與組合間的映射關係，在AC自動機算法運行結束後，只有某個組合對應的敏感詞全部命中時，才能判斷該組合敏感詞命中。為此我們需要給AC自動機添加一些前置和後置的處理步驟，具體步驟如下：

• 將組合敏感詞分割為單個敏感詞，並記錄敏感詞與組合的映射關係；

• 將分割後的組合敏感詞添加到AC自動機的Tire樹中；

• 運行AC自動機，匹配文本；

• 遍歷匹配結果，將匹配的結果根據映射關係映射到相應的組合上；

• 記錄組合的命中情況，得到最終匹配結果。

假設目前存在組合敏感詞「澳門+博彩+網站」、「博彩+廣告」、「華人圈+賭博」、「賭博+廣告」，以及普通敏感詞「暴政」，則在步驟1中，我們將組合敏感詞分割為單個敏感詞：「澳門」、「網站」、「博彩」、「廣告」、「賭博」、「華人圈」、「暴政」，並建立圖中所示的映射關係。將這些詞添加到AC自動機後，對文本「歡迎登錄澳門XX博彩官方網站」進行匹配時，會命中單個敏感詞「澳門」、「網站」、「博彩」。在步驟4中，算法將匹配的詞映射到組合中，並標記對應的詞命中。例如根據「博彩」，可取到組合「澳門+博彩+網站」、「博彩+廣告」，則分別標記這兩個組合中的「博彩」已命中。步驟5會根據各組合中單詞的命中情況，來判斷該組合是否命中，由於在步驟4中組合敏感詞「澳門+博彩+網站」的三個詞均被標記為命中，因此可判斷該組合命中。

3.2 拼音敏感詞

在評論、彈幕等創作自由度很高的場景中，某些用戶為了規避機器審核，會使用一些多音字、同音字來表達敏感詞彙，例如用「啋票」來代表「彩票」等。由於多音字、同音字變化較多，將一個詞的所有諧音詞都窮舉出來是很困難的。因此我們實現了拼音敏感詞的匹配方案，將中文文本轉換為拼音再匹配，通過讀音匹配敏感詞，即可保證命中所有的同音字，運營直接配置敏感詞的拼音，例如「CAI PIAO」，即可命中「啋票」、「彩票」、「采漂」等詞彙。

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，提升命中的精準度。另一方面，我們可以實現敏感詞的模糊命中，提升敏感詞的命中率。

作者：vivo互聯網服務器團隊-Liang Kangwu