劉 瑩 楊超宇

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

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

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

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

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

一、相關(guān)技術(shù)

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

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

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

其中，hp表示拼音字母部分漢明距離，hs表示拼音聲調(diào)部分漢明距離，lp為拼音字母部分的二進(jìn)制長(zhǎng)度，

ls為拼音聲調(diào)部分的二進(jìn)制長(zhǎng)度，bp和bs為拼音字母部分和拼音聲調(diào)部分在最終相似度計(jì)算的貢獻(xiàn)比，且滿足bp+bs=1，計(jì)算公式為：

當(dāng)兩個(gè)字差別越大，相似度S越接近0，當(dāng)兩個(gè)字讀音越相似，相似度S越接近1，當(dāng)兩個(gè)字相同時(shí)，相似度S等于1。

確定有限狀態(tài)自動(dòng)機(jī)。確定有限狀態(tài)自動(dòng)機(jī)（DFA），能夠?qū)崿F(xiàn)狀態(tài)轉(zhuǎn)移的自動(dòng)機(jī)，給定一個(gè)自動(dòng)機(jī)狀態(tài)和一個(gè)輸入符，經(jīng)映射后，將轉(zhuǎn)移到下一個(gè)自動(dòng)機(jī)狀態(tài)[9-12]。

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

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

圖1 狀態(tài)轉(zhuǎn)移圖

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

二、改進(jìn)的敏感詞過濾模型

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

a)所有節(jié)點(diǎn)關(guān)鍵字都是獨(dú)一無二的，不存在兩個(gè)相同的節(jié)點(diǎn)字符。

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

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

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

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

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

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

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

圖2 敏感詞有向圖

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

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

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

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

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

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

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

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

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

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

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

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

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

其進(jìn)行編譯成二進(jìn)制數(shù)序列，音碼結(jié)構(gòu)如圖3所示：

圖3 音碼結(jié)構(gòu)

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

表1 聲母編碼

表2 韻母補(bǔ)位編碼

表3 韻母補(bǔ)位編碼

表4 聲調(diào)編碼

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

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

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

S1.1：判斷第i個(gè)字符是否為標(biāo)點(diǎn)符號(hào)，如果是，繼續(xù)執(zhí)行S1.2，如果不是，則跳轉(zhuǎn)執(zhí)行S1.3；

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

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

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

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

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

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

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

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

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

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

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

圖4 文本敏感詞檢測(cè)過程

三、實(shí)驗(yàn)及結(jié)果分析

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

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

（二）全模式匹配實(shí)驗(yàn)分析。全模式匹配實(shí)驗(yàn)關(guān)閉相似度比較入口，只有和敏感詞庫(kù)中收錄的敏感詞相同的詞才會(huì)被過濾。

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

表5 敏感詞數(shù)目

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

表6 敏感詞查找耗時(shí)

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

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

表7 不同文本字?jǐn)?shù)的檢測(cè)時(shí)間

為了更好地將算法檢測(cè)時(shí)間在柱狀圖上顯示，對(duì)敏感詞檢測(cè)時(shí)間進(jìn)行處理。

將敏感詞檢測(cè)時(shí)間T取對(duì)數(shù)，并加上常數(shù)4，得出相對(duì)檢測(cè)時(shí)長(zhǎng)t，以檢測(cè)的相對(duì)時(shí)長(zhǎng)進(jìn)行比較，如圖5所示：

圖5 不同文本字?jǐn)?shù)的檢測(cè)時(shí)間

如表7和圖5所示，檢測(cè)相同字?jǐn)?shù)的文本時(shí)，DG-DGA所需時(shí)間遠(yuǎn)遠(yuǎn)短于DFA，因此DG-DGA的匹配速度遠(yuǎn)遠(yuǎn)高于DFA，當(dāng)待檢測(cè)文本的字?jǐn)?shù)越多，DG-DGA的速度優(yōu)勢(shì)越明顯，敏感詞檢測(cè)效率越高。

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

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

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

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

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

四、結(jié)語

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