融合有向圖的文本敏感詞過濾模型

劉 瑩 楊超宇

（安徽理工大學經(jīng)濟與管理學院 安徽淮南 233000）

由于互聯(lián)網(wǎng)信息爆炸式增長，帶有暴力傾向、不健康色彩的詞或不文明語，涉及軍事、政治、經(jīng)濟等各方面[1-3]的非法信息也會在網(wǎng)絡中傳播。因此對互聯(lián)網(wǎng)網(wǎng)頁內容的監(jiān)控、過濾必不可少。

目前，許多學者針對敏感詞的過濾和敏感詞變體的識別進行研究。文獻[4]提出了基于改進的Trie樹和DFA的敏感詞過濾算法，通過排列組合的數(shù)學原理擴充中文詞庫，構建敏感詞樹存儲DFA的所有狀態(tài)，解決了在敏感詞過濾技術中的人工干擾、分詞障礙等關鍵問題。文獻[5]提出了基于決策樹的敏感詞變形體識別算法，該算法針對詞的拼音、詞的簡稱和詞的拆分三種敏感詞變形體的分析，對敏感詞庫進行擴充，構建敏感詞樹，該算法提高了敏感詞變形體的識別效率。文獻[6]中，作者提出了一種基于Aho-Corasick，并結合Trie樹的多模式匹配算法，該算法在匹配速度、匹配查全率和空間利用率方面都有很好的效果，但是無法處理敏感次變形體。文獻[7]提出基于改進音形碼的中文敏感詞檢測算法，算法綜合考慮漢字讀音及字形特點，并對漢字相似度算法改進。文獻[8]在Trie樹的基礎上進行改進，以實現(xiàn)對普通敏感詞的識別的同時，也將敏感詞變形體識別出來。

目前算法大都基于敏感詞庫構建Trie樹，并結合相關匹配算法實現(xiàn)對敏感詞的過濾。缺點是當敏感詞的前綴不同時，無法使用敏感詞共同前綴的敏感詞相同關鍵字會出現(xiàn)在不同的敏感詞分支中，造成存儲的冗余。在敏感詞庫中的敏感詞數(shù)量較大時，會花費更多的時間、空間存儲重復出現(xiàn)的敏感詞關鍵字，造成不同前綴敏感詞的節(jié)點重復構建。如：混蛋、滾蛋、王八蛋。這三個敏感詞沒有相同的前綴，但有相同的后綴。因此，三棵敏感詞樹存儲了相同的“蛋”字節(jié)點。這些節(jié)點會使敏感詞樹的子樹數(shù)、樹的層數(shù)、樹的深度增加。存儲敏感詞樹時會占用和大量的空間，算法需要花費較長的時間去構建敏感詞樹。

針對敏感詞Trie樹各個分支上可能存在大量的重復節(jié)點的問題，提出了基于有向圖和DFA的敏感詞過濾算法（DG-DGA）。算法通過有向圖存儲敏感詞，減少了重復敏感詞關鍵字的存儲，提高敏感詞的檢索速度。

一、相關技術

基于漢明距離的相似度。漢明距離是指在數(shù)據(jù)傳輸差錯控制編碼中兩個相同長度的二進制字符串對應位不同的數(shù)量。以h（x,y）表示兩個字符串x,y之間的漢明距離。h（x,y）是對兩個字符串x，y進行異或運算后，結果為1的個數(shù)。文獻[7]提出了敏感詞中漢字的漢基于音形碼的相似度算法，并考慮了漢字拼音和字形在相似度中的貢獻比，相似度S為：

其中，hp表示拼音部分漢明距離，hx表示字形部分漢明距離，l1為音碼的二進制長度，l2為形碼的二進制長度，b1和b2為音碼部分和形碼部分在最終相似度計算中所占的貢獻比，且滿足b1+b2=1，計算公式為：

本篇文章著重考慮讀音相似的敏感詞，因此漢字拼音上的相似度，充分考慮拼音聲母、韻母、聲調對相似度的影響，著重考慮拼音和聲調對相似度的貢獻比，對相似度公式進行改進。相似度S為：

其中，hp表示拼音字母部分漢明距離，hs表示拼音聲調部分漢明距離，lp為拼音字母部分的二進制長度，

ls為拼音聲調部分的二進制長度，bp和bs為拼音字母部分和拼音聲調部分在最終相似度計算的貢獻比，且滿足bp+bs=1，計算公式為：

當兩個字差別越大，相似度S越接近0，當兩個字讀音越相似，相似度S越接近1，當兩個字相同時，相似度S等于1。

確定有限狀態(tài)自動機。確定有限狀態(tài)自動機（DFA），能夠實現(xiàn)狀態(tài)轉移的自動機，給定一個自動機狀態(tài)和一個輸入符，經(jīng)映射后，將轉移到下一個自動機狀態(tài)[9-12]。

D=（K，Σ，M，S，F(xiàn)），其中D為五元組；K為有窮、非空的狀態(tài)集合；Σ為有窮、非空的輸入符號集合；M為轉換函數(shù)，是在K×Σ→K上的映射，如，M(ki,a)=kj，(ki∈K,kj∈K)表示：當前狀態(tài)為ki，輸入符為a時，經(jīng)過映射，轉換為下一個狀態(tài)kj，并把kj稱作ki的一個后繼狀態(tài)；S（S∈K）是唯一的初始狀態(tài)；F（F?K）是非空的終止狀態(tài)的集合。

如果輸入為a，b，則假設DFA狀態(tài)轉移圖如圖1所示：

圖1 狀態(tài)轉移圖

本文通過有向圖將敏感詞庫中的敏感詞聯(lián)系起來，每個敏感詞關鍵字都是節(jié)點，通過節(jié)點的指向關系表現(xiàn)敏感詞中每個字的前后順序。在敏感詞有向圖中檢測敏感詞時，以DFA的機理實現(xiàn)狀態(tài)轉移。以敏感詞的起始關鍵字作為初始狀態(tài)S的元素，以待判斷的字作為輸入，確定狀態(tài)轉移的指向，從而轉換為下一個狀態(tài)，直到到達終止狀態(tài)F，即敏感詞最后一個字，此時一個敏感詞被成功檢測出來。

二、改進的敏感詞過濾模型

（一）基于有向圖和DFA的敏感詞算法設計。一個有向圖D是指一個有序三元組(V(D)，A(D)，ψD)，其中V(D)表示有向圖D的節(jié)點點集合；A(D)表示有向圖D的邊的集合；ψD為關聯(lián)函數(shù)，它使A(D)中的每一條邊對應于V(D)中的一個有序節(jié)點對[13-16]。對于敏感詞有向圖，一個節(jié)點表示一個敏感詞關鍵字，其特點如下：

a)所有節(jié)點關鍵字都是獨一無二的，不存在兩個相同的節(jié)點字符。

b)具有相同關鍵字的敏感詞共享該關鍵字節(jié)點。

c)每個節(jié)點記錄了起始和結束標志，以及以該節(jié)點字符結尾的所有敏感詞起始字符。

d)節(jié)點的度越大，說明這個敏感詞關鍵字在敏感詞庫里出現(xiàn)的頻率越高。

e)若節(jié)點只有入度，沒有出度，說明該節(jié)點的關鍵字是敏感詞的最后一個字。

f)若節(jié)點只有出度，沒有入度，說明該節(jié)點的關鍵字是敏感詞的第一個字。

g)在原有敏感詞有向圖的任意位置添加敏感詞節(jié)點。

有向圖中每個敏感詞關鍵字節(jié)點表示DFA的一個狀態(tài)，每條邊的指向關系表示出敏感詞關鍵字之間的關系。假設敏感詞為：“王八蛋、混蛋、混球、滾蛋、滾邊去”，每個節(jié)點都有起始標志isStart、結尾標志isEnd、起始節(jié)點集合starts。當節(jié)點作為起點時，起始標志設為1；當節(jié)點為尾節(jié)點，結尾標志為1。由于“王”“混”“滾”均為敏感詞的起始關鍵字，因此這三個關鍵字的節(jié)點的起始標志isStart=1。由于“蛋”“球”“去”均為敏感詞的最末關鍵字，因此這三個關鍵字的節(jié)點的結尾標志isEnd=1。并且，以“蛋”為結尾關鍵字的敏感詞有“王八蛋、混蛋、滾蛋”，因此該節(jié)點的起始節(jié)點集合starts存儲了這三個敏感詞的的起始關鍵字。則構建的敏感詞有向圖如圖2所示：

圖2 敏感詞有向圖

（二）敏感詞有向圖構建算法。敏感詞有向圖構建算法將敏感詞庫中的敏感詞以有向圖的形式存儲，敏感詞庫中的每個字在有向圖中以節(jié)點表示，且重復出現(xiàn)的字以同一個節(jié)點表示。構建敏感詞有向圖的具體描述如下：

S1：以一個敏感詞為單位把敏感詞庫中的所有敏感詞添加到名為keyWordList的列表中，新建字典變量entrance存儲所有敏感詞關鍵字的字符節(jié)點，構建字典變量root存放所有敏感詞起始關鍵字節(jié)點，并執(zhí)行S2；

S2：循環(huán)執(zhí)行以下操作，當keyWordList到達末尾時循環(huán)結束，構建敏感詞樹也結束，若循環(huán)未結束，則執(zhí)行S2.1；

S2.1：依次從keyWordList中取出一個敏感詞，放在名為keyWord的變量中，keyword的長度為len_chars，執(zhí)行S2.2；

S2.2：循環(huán)執(zhí)行以下操作，若循環(huán)未結束，則執(zhí)行S2.2.1，若結束，跳轉執(zhí)行S2.1；

S2.2.1：定義變量i表示當前敏感詞的第i個位置，當前敏感詞關鍵字為chars[i]，執(zhí)行S2.2.2；

S2.2.2：判斷當前字符chars[i]是否在有向圖entrance中，如果不在，則新建節(jié)點node，并以該字符為鍵，以該節(jié)點node為值，添加到字典entrance中，并繼續(xù)執(zhí)行S2.2.3；

S2.2.3：若i＞0,即為不為敏感詞起始關鍵字，則將該節(jié)點指向上一節(jié)點；繼續(xù)執(zhí)行S2.2.4；

S2.2.4：若為敏感詞最后一個關鍵字，則執(zhí)行S2.3，否則跳轉執(zhí)行S2.2.1;

S2.3：將敏感詞起始關鍵字節(jié)點的isStart標志設置為1，敏感詞末尾關鍵字節(jié)點的isEnd標志設置為1，將起始關鍵字節(jié)點添加到末尾關鍵字節(jié)點的starts列表中，以起始關鍵字字符為鍵，以起始關鍵字節(jié)點為值，添加到字典root中，跳轉執(zhí)行S2.1。

根據(jù)以上算法描述，敏感詞庫中的所有敏感詞都被存儲到敏感詞有向圖中，且可以在原有敏感詞有向圖的任意位置添加敏感詞節(jié)點。若新的敏感詞中的關鍵字在有向圖中已經(jīng)存在，那么，只需要修改對應關鍵字的isStart標志、isEnd標志，將起點頂點添加到末點頂點的starts中即可。

（三）敏感詞檢測算法設計。構建敏感詞有向圖后，根據(jù)設定的敏感程度閾值，將原文本中的詞與敏感詞有向圖比對，進行基于音碼的拼音敏感程度的計算，若敏感程度大于設定的閾值，那么則認為該詞為敏感詞，并進行敏感詞的過濾。

音碼編碼。本文采用四位音碼的方式展現(xiàn)每個字的拼音特征，分別是聲母、韻母補位、韻母、聲調，并將其采用格雷碼對

其進行編譯成二進制數(shù)序列，音碼結構如圖3所示：

圖3 音碼結構

本文將所有每位聲母、韻母補位、韻母、聲調都分配一個十進制數(shù)字表示，再將該數(shù)字轉化為六位格雷碼，由于格雷碼任意相鄰的兩位編碼只有一位二進制數(shù)不同。因此，發(fā)音相近的拼音聲母及韻母設置的數(shù)字間隔更小，使其計算相似度更高，如“z”和“zh”，“an”和“ang”。由于聲母、韻母和聲調的十進制表示和對應的格雷碼編碼如表1～4所示。

表1 聲母編碼

表2 韻母補位編碼

表3 韻母補位編碼

表4 聲調編碼

通過以上編碼規(guī)則，可以將漢字轉化為相應的格雷碼，例如，“淮”字的拼音為“huai”，聲調為“陽平”。由于聲母“h”的格雷碼為“011111”，韻母補位“u”的格雷碼為“001101”，韻母“ai”的格雷碼為“001011”，聲調“陽平”的格雷碼為“000011”，則“淮”字格雷碼為“011111001101001011000011”。

基于相似度的敏感詞檢測算法。構建敏感詞有向圖后，將原文本中的待檢測漢字與敏感詞有向圖中特定節(jié)點漢字比對，分別根據(jù)兩漢字的拼音得到對應的格雷碼，再根據(jù)改進的拼音相似度計算公式計算兩個漢字的相似度，判斷該相似度是否大于設定的相似度閾值，若大于，則認為該待檢測漢字與節(jié)點漢字相符，繼續(xù)判斷下一個待檢測漢字和下一節(jié)點漢字的相似度?；谙嗨贫鹊拿舾性~檢測算法描述為：

S1：從原文本的第一個字符開始，循環(huán)執(zhí)行以下操作，直到原文本最后一個字符被執(zhí)完結束，定義變量ret存儲過濾后的文本字符，定義變量i表示原文本的當前位置，初始值i=0指向原文本的第一個字符位置，定義level為敏感詞有向圖的當前位置；

S1.1：判斷第i個字符是否為標點符號，如果是，繼續(xù)執(zhí)行S1.2，如果不是，則跳轉執(zhí)行S1.3；

S1.2：將第i個字符直接存入ret，并跳轉執(zhí)行S1.1；

S1.3：將第i個字符與root中所有起始節(jié)點字符分別計算相似度，將得到的最大相似度存儲在變量max_sim_root中，對應的最大相似度的節(jié)點字符存儲在變量char_max_sim_root中，該字符認為是當前檢測敏感詞的起始字符，并設定拼音相似度臨界值sim_standard為0.92，繼續(xù)執(zhí)行S1.4；

S1.4：判斷字符最大相似度max_sim_root是否大于sim_standard，如果不是，則將原文本第i個字符存入ret，并跳轉執(zhí)行S1.1，如果是，則繼續(xù)執(zhí)行S1.5；

S1.5：將敏感詞有向圖當前位置level定位到字符為char_max_sim_root的節(jié)點上，以變量start_index存儲當前檢測敏感詞的首字符在原文本中的位置，即start_index=i,執(zhí)行S1.6；

S1.6：循環(huán)執(zhí)行以下操作，若循環(huán)未結束，則執(zhí)行S1.6.1，若結束，跳轉執(zhí)行S1.1；

S1.6.1：定義變量j表示當前判斷的是原文本的第j字符位置，初始值j=i+1,繼續(xù)執(zhí)行S1.6.2；

S1.6.2：將第j個字符與當前敏感詞有向圖level位置下所有節(jié)點字符分別計算相似度，將得到的最大相似度存儲在變量max_sim中，對應的最大相似度的節(jié)點字符存儲在變量char_sim中，繼續(xù)執(zhí)行S1.6.3；

S1.6.3：判斷最大相似度max_sim是否大于sim_standard，如果不是，則將原文本第i個字符存入ret，并跳轉執(zhí)行S1.1，如果是，則繼續(xù)執(zhí)行S1.6.4；

S1.6.4：判斷起始字符char_max_sim_root節(jié)點是否為當前末點char_sim節(jié)點的起點，如果不是，則有向圖指針level指向原下一字符，并跳轉執(zhí)行S1.6.1，如果是，則將原文的敏感詞字符位置存儲“*”，將原文指針i移到當前敏感詞末字符位置，即i=j，若當前原文字符不是原文最后一個字符，并跳轉執(zhí)行S1.1，若是，則繼續(xù)執(zhí)行S2；

S2：將列表ret中的字符串連接成一個完整字符串，并返回該字符串，即過濾完成。

根據(jù)上述算法描述，將待檢測原文的逐字與敏感詞有向圖對比，直到有向圖的末點節(jié)點。若待檢測漢字的相似度都大于閾值，則可以認為這些待檢測漢字是一個敏感詞，并對其以“*”替代，進而將該敏感詞過濾。以此對讀音相似的敏感詞干擾問題進行處理。圖4是文本敏感詞檢測過程。

圖4 文本敏感詞檢測過程

三、實驗及結果分析

實驗是在WIN10系統(tǒng)下，使用編程語言是Python3.7，算法運行環(huán)境是PyCharm。

（一）數(shù)據(jù)集。敏感詞庫來自從網(wǎng)絡上下載的開源敏感詞庫，敏感詞詞庫共有1757個敏感詞，其中暴恐類敏感詞有116個，反動類敏感詞有456個，民生類敏感詞有417個，色情類敏感詞有499個，貪腐類敏感詞有218個，其他51個。根據(jù)以上敏感詞庫構建敏感詞有向圖。

（二）全模式匹配實驗分析。全模式匹配實驗關閉相似度比較入口，只有和敏感詞庫中收錄的敏感詞相同的詞才會被過濾。

1.敏感詞檢測算法過濾效率對比。該實驗將基于敏感詞Trie樹的DFA敏感詞檢測算法和本文DG-DFA算法進行對比，敏感詞對比采用完全匹配模式。該實驗的待檢測文本來自鍵盤隨機敲擊產(chǎn)生的漢字和字母組合，并從中插入751個敏感詞。插入的敏感詞及其個數(shù)如表5所示：

表5 敏感詞數(shù)目

由于敏感詞的查找時間會因計算機運行狀況而有細微差別，因此在計算不同算法的過濾時間時，使用控制變量的方法，且在每種算法下連續(xù)重復實驗10次，記錄每次敏感詞過濾耗時，取其平均值。敏感詞查找耗時如表6所示：

表6 敏感詞查找耗時

在敏感詞總數(shù)均為751時，基于敏感詞trie樹的DFA敏感詞檢測算法的檢測耗時約為DG-DGA算法的6倍，說明DG-DGA算法的檢測效率要遠高于基于敏感詞Trie樹的DFA敏感詞檢測算法。

2.不同文本字數(shù)過濾效果對比。該實驗在相同的條件下比較基于敏感詞Trie樹的DFA敏感詞檢測算法和DGDGA算法的檢測時間，根據(jù)待檢測文本的文本字數(shù)的不同共進行8組測試，待檢測文本的字數(shù)分別為5萬、10萬、15萬、20萬、25萬、30萬、35萬、40萬。每組測試重復進行10次，記錄每次敏感詞檢測時間，并將這10次檢測時間的平均值作為該組文本字數(shù)的檢測時間。實驗檢測結果如表7所示：

表7 不同文本字數(shù)的檢測時間

為了更好地將算法檢測時間在柱狀圖上顯示，對敏感詞檢測時間進行處理。

將敏感詞檢測時間T取對數(shù)，并加上常數(shù)4，得出相對檢測時長t，以檢測的相對時長進行比較，如圖5所示：

圖5 不同文本字數(shù)的檢測時間

如表7和圖5所示，檢測相同字數(shù)的文本時，DG-DGA所需時間遠遠短于DFA，因此DG-DGA的匹配速度遠遠高于DFA，當待檢測文本的字數(shù)越多，DG-DGA的速度優(yōu)勢越明顯，敏感詞檢測效率越高。

綜上所述，在敏感詞檢測過程中，構建敏感詞有向圖比構建敏感詞Trie更節(jié)省時間。

（三）模糊匹配模式實驗分析。不同敏感度閾值文本過濾實驗。實驗通過設定不同的相似度閾值，比較DG-DFA算法的過濾效果。待檢測文本的數(shù)據(jù)集來從敏感詞庫中抽取131各敏感詞，并人為構建讀音相近的敏感詞，共擴展敏感詞833個。在不同敏感詞閾值下進行實驗，并統(tǒng)計敏感詞個數(shù)。敏感詞閾值分別取0.5、0.6、0.7、0.8、0.9，表8是不同敏感詞閾值下的敏感詞檢測數(shù)量。

表8 不同敏感詞閾值的敏感詞檢測數(shù)量

從表8中結果可以看出，敏感詞算法在閾值為0.5時，就可以將92.6%的相似敏感詞識別出來，且敏感詞閾值為0.9時檢測出來的相似敏感詞占敏感詞閾值為0.5時的94.56%，說明算法能較好地識別敏感詞的相似讀音。

因此，融合有向圖的文本敏感詞過濾模型在構建敏感詞有向圖時，比構建敏感詞樹更節(jié)約時間；且通過漢字拼音和聲調相似度的計算，能夠有效識別讀音相似的敏感詞，能夠增強敏感詞識別效率和覆蓋程度。

四、結語

該文本敏感詞過濾模型中的DG-DFA算法融合了有向圖的思想，將敏感詞庫中的敏感詞以有向圖的方式連接。該算法將敏感詞庫中的敏感詞關鍵字存放于有向圖中，通過有向圖的邊維系每個敏感詞。與原有的DFA算法相比，DG-DFA將敏感詞樹替換成敏感詞有向圖，敏感詞中的相同關鍵字在有向圖中只存儲一次，避免了原始DFA算法敏感詞決策樹中不同前綴的敏感詞中相同關鍵字的重復存儲，節(jié)省了存儲空間。為了驗證算法的性能，進行了DFA算法和DG-DGA算法在全模式匹配下的敏感詞檢測算法過濾效率對比實驗、不同文本長度下的時間效率對比實驗，以及DG-DGA算法在不同敏感度閾值文本過濾實驗。通過實驗表明：DG-DGA算法的過濾算法的檢測速度約是DFA算法的6倍，有更高的敏感詞匹配效率；文本敏感詞過濾模型在不同文本數(shù)量下檢測敏感詞時，待檢測文本數(shù)量越大，模型的檢測優(yōu)勢越明顯，且DG-DGA算法能較好地識別敏感詞的相似讀音。