基于改進(jìn)Trie樹(shù)的變形敏感詞過(guò)濾算法

葉情

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，我們?cè)谙硎芫W(wǎng)絡(luò)科技帶來(lái)便利的同時(shí)，各種非法言論（如反政治、暴力血腥、黃賭毒等）經(jīng)常在網(wǎng)絡(luò)中蔓延，不可避免地受到這些信息的侵害。盡管有關(guān)部門已經(jīng)采取一系列監(jiān)控管理措施來(lái)優(yōu)化網(wǎng)絡(luò)環(huán)境，但仍有不法分子通過(guò)各種手段在網(wǎng)絡(luò)中散播不利于網(wǎng)絡(luò)環(huán)境的言論，嚴(yán)重影響社會(huì)主義的精神文明建設(shè)。為改善網(wǎng)絡(luò)環(huán)境、減少不良信息傳播，在從法律、道德等方面進(jìn)行約束的同時(shí)，還必須通過(guò)技術(shù)手段對(duì)網(wǎng)絡(luò)信息進(jìn)行過(guò)濾，優(yōu)化網(wǎng)絡(luò)環(huán)境。

目前，國(guó)內(nèi)外對(duì)于敏感詞的識(shí)別研究形成了較為成熟的體系，并且廣泛應(yīng)用于各大網(wǎng)絡(luò)平臺(tái)中。例如網(wǎng)易的易盾敏感詞過(guò)濾系統(tǒng)能有效識(shí)別出文本中的敏感詞。由于中文存在字詞結(jié)構(gòu)復(fù)雜、語(yǔ)義多變、詞庫(kù)量大等特點(diǎn)，因此對(duì)于變形敏感詞的過(guò)濾處理存在較大困難。目前，對(duì)變形敏感詞的研究還處于起步階段，相關(guān)研究成果較少。文獻(xiàn)[10]針對(duì)變形敏感詞提出一種新的過(guò)濾算法，將文本中的特殊字符進(jìn)行預(yù)處理轉(zhuǎn)為中文字符再進(jìn)行檢測(cè)，該方法能檢測(cè)出一類特定敏感詞，提高了文本檢測(cè)的精度。文獻(xiàn)[11]采用機(jī)器學(xué)習(xí)的方法，將Bigram、詞干等作為特征值來(lái)對(duì)文本信息做分類處理，以檢測(cè)出變形敏感詞。文獻(xiàn)[7]提出一種基于語(yǔ)言的字符串匹配算法，該算法可以有效地識(shí)別發(fā)音相似的敏感詞，但對(duì)于其他類型的敏感詞缺乏分析。

基于以上研究，本文對(duì)常見(jiàn)變形敏感詞進(jìn)行歸納分類，提出一種基于改進(jìn)Trie樹(shù)的變形敏感詞過(guò)濾算法，不僅可以過(guò)濾普通敏感詞，對(duì)變形敏感詞的識(shí)別也起到了良好的效果。

1 敏感詞過(guò)濾算法預(yù)處理

1.1 變形敏感詞處理

經(jīng)過(guò)對(duì)變形敏感詞的研究與分析，對(duì)現(xiàn)有的變形敏感詞進(jìn)行了分類總結(jié)，將變形敏感詞大致分為以下3類：

第一類：添加特殊字符的敏感詞，在敏感詞之間添加非中文符號(hào)或者用符號(hào)替代敏感詞中的某個(gè)字。例如：在“法輪功”這個(gè)敏感詞之間插入非中文字符形成變形敏感詞“法@輪&&&功”、用“*”替代“法輪大法”一詞中的某個(gè)字形成變形敏感詞“法輪*法”等。

第二類：使用拼音、同音字、諧音字等將敏感詞變形，例如：“法輪 gong”、“臺(tái)獨(dú)分子”。

第三類：經(jīng)過(guò)拆分、繁體化的敏感詞，例如：“三去車侖工力”、“口馬口非”、“進(jìn)寶”等。

1.2 文本分立預(yù)處理

對(duì)文本進(jìn)行分立處理是敏感詞過(guò)濾的第一步，針對(duì)1.1介紹的三種變形敏感詞，分別采用不同的分立處理方法。對(duì)于第一類，若在敏感詞中插入多個(gè)特殊字符，將只用一個(gè)“*”代替。對(duì)于第二類中的拼音分立情況較為復(fù)雜，英文字符串可能是拼音或者英文單詞，因此在分立英文字符串時(shí)需要進(jìn)一步處理。對(duì)第三類敏感詞將直接進(jìn)行分立處理。

對(duì)于英文字符串，常見(jiàn)的漢語(yǔ)拼音有409種組合。本文通過(guò)以正則匹配為核心進(jìn)行拼音串識(shí)別，具體正則表達(dá)式如圖1所示，如果是拼音字符串，將正確分立成單個(gè)拼音；如果不能分立成拼音，則分立為單個(gè)英文字符。

圖1 正則表達(dá)式

1.3 基于中文的Trie樹(shù)構(gòu)建

Trie樹(shù)的結(jié)點(diǎn)一般由英文字符組成，因此Trie樹(shù)一個(gè)節(jié)點(diǎn)一般具有26個(gè)子節(jié)點(diǎn)。而中文則不同，常見(jiàn)漢字有將近7000多個(gè)，若按照英文的Trie樹(shù)構(gòu)建中文敏感詞Trie樹(shù)，將大大增加查找難度。因此，本文對(duì)英文Trie樹(shù)結(jié)構(gòu)進(jìn)行改進(jìn)，以適應(yīng)中文敏感詞Trie樹(shù)的構(gòu)建。

本文基于文獻(xiàn)[12]中的決策樹(shù)思想，并基于漢語(yǔ)拼音的組成，構(gòu)建了改進(jìn)的中文敏感詞Trie樹(shù)，該樹(shù)能夠支持多種變形敏感詞的查找以及特殊字符的存儲(chǔ)。由于漢語(yǔ)拼音的首字母由 23 個(gè)（去除“u”、“v”、“i”）字母組成，因此該樹(shù)的根節(jié)點(diǎn)下創(chuàng)建24個(gè)子節(jié)點(diǎn)，其中0～22號(hào)節(jié)點(diǎn)分別存儲(chǔ)首字母拼音的中文敏感詞，23號(hào)的節(jié)點(diǎn)存儲(chǔ)數(shù)字或者其他非中文和英文字符開(kāi)頭的敏感詞，并且在存入漢字及其拼音的同時(shí)標(biāo)記該節(jié)點(diǎn)是否為終端節(jié)點(diǎn)。改進(jìn)后的敏感詞Trie樹(shù)結(jié)構(gòu)如圖2所示，其中根節(jié)點(diǎn)和第一層子節(jié)點(diǎn)是固定不變的，圖中深色結(jié)點(diǎn)表示終端結(jié)點(diǎn)。

圖2 中文敏感詞Trie樹(shù)

2 敏感詞過(guò)濾算法的具體實(shí)現(xiàn)

對(duì)于存在普通敏感詞的文本，經(jīng)過(guò)文本分立處理后，可直接在詞庫(kù)中進(jìn)行過(guò)濾；在對(duì)變形敏感詞匹配過(guò)程中，針對(duì)第三類變形敏感詞，本文在構(gòu)建敏感詞庫(kù)時(shí)，已經(jīng)盡可能地將這種變形敏感詞加入，直接利用Trie樹(shù)進(jìn)行匹配即可。而對(duì)于第一類和第二類變形詞，需要特殊的匹配算法進(jìn)行過(guò)濾。

2.1 第一類變形敏感詞的最大匹配算法

對(duì)于第一類敏感詞，特殊符號(hào)可能僅代替其中一個(gè)敏感詞字符，也可能僅僅是間隔其中的漢字，起到干擾作用，因此在匹配時(shí)分兩種情況進(jìn)行模糊匹配。

例如敏感詞“法輪*法”，其匹配過(guò)程如圖3所示，當(dāng)成功匹配“法輪”兩個(gè)字符后，下一個(gè)待匹配的字符為“*”。若“*”不替代敏感詞中的任何字符，則直接比較下個(gè)字符“法”與下層節(jié)點(diǎn)即第4層節(jié)點(diǎn)的字符，發(fā)現(xiàn)無(wú)法匹配。再將“法”與下一層即第5層節(jié)點(diǎn)的字符對(duì)比，發(fā)現(xiàn)剛好匹配，而這個(gè)匹配的節(jié)點(diǎn)同時(shí)為葉節(jié)點(diǎn)和終節(jié)點(diǎn)，所以本輪匹配結(jié)束。因此，我們認(rèn)為檢測(cè)文本中的“法輪*法”與敏感詞庫(kù)中的“法輪大法”相匹配。同理，“法輪*功”則與“法輪功”匹配。

圖3 第一類變形詞匹配舉例

2.2 第二類變形敏感詞的最大匹配算法

對(duì)于第二類變形詞，當(dāng)遇到連續(xù)拼音串時(shí)，本文基于最大匹配原則，采用此正則表達(dá)式對(duì)拼音串進(jìn)行分割，例如“Yeqing”可正確分割成“Ye qing”。在對(duì)拼音進(jìn)行匹配時(shí)，由于匹配情況較為復(fù)雜，需要額外空間存儲(chǔ)節(jié)點(diǎn)，規(guī)定用pinYin數(shù)組存儲(chǔ)拼音串，用pre數(shù)組存儲(chǔ)待定匹配節(jié)點(diǎn)，用node數(shù)組存儲(chǔ)已匹配的節(jié)點(diǎn)。由于一個(gè)拼音可能對(duì)于多個(gè)漢字，因此在檢測(cè)拼音串時(shí)，pre數(shù)組存儲(chǔ)該拼音對(duì)應(yīng)的所有節(jié)點(diǎn)。若上輪存在成功匹配的節(jié)點(diǎn)，則存入node中,本輪匹配將從pre數(shù)組中的子節(jié)點(diǎn)出發(fā)，直至匹配到終端節(jié)點(diǎn)為止。

算法1查找某個(gè)文本分立單元相匹配的所有子節(jié)點(diǎn)

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

3.1 數(shù)據(jù)集處理

本實(shí)驗(yàn)的環(huán)境為Intel i5處理器，8GB內(nèi)存，編程語(yǔ)言為Java。實(shí)驗(yàn)中敏感詞庫(kù)的敏感詞來(lái)源于國(guó)內(nèi)幾大權(quán)威網(wǎng)站的敏感詞庫(kù)以及部分網(wǎng)絡(luò)新詞匯整理歸納而成。詞庫(kù)中的敏感詞一共4700個(gè)，在實(shí)驗(yàn)過(guò)程中，詞庫(kù)會(huì)不斷進(jìn)行更新。

首先對(duì)一個(gè)給定文本片段的敏感詞進(jìn)行檢測(cè)，對(duì)比本文敏感詞檢測(cè)算法與文獻(xiàn)[7]中的ST-DFA算法的檢測(cè)結(jié)果如圖4所示。從結(jié)果中可看出，本文的敏感詞檢測(cè)算法對(duì)于變形敏感詞的過(guò)濾精度高于ST-DFA算法。

圖4 敏感詞檢測(cè)對(duì)比結(jié)果

為了進(jìn)一步檢驗(yàn)該算法的正確性，從全網(wǎng)數(shù)據(jù)庫(kù)中隨機(jī)抽取了含有疑似敏感詞的1000篇文本作為測(cè)試數(shù)據(jù)集。為了方便后續(xù)的結(jié)果統(tǒng)計(jì)，人工地將1000篇文章根據(jù)含有敏感詞類型進(jìn)行分類匯總，其中普通敏感詞一共1376個(gè)，變形敏感詞274個(gè)，為減小實(shí)驗(yàn)誤差，需要將變形詞的原型敏感詞加入詞庫(kù)中。對(duì)敏感詞檢測(cè)結(jié)果分可為兩種情況,正確肯定（True Posi?tive，TP）：預(yù)測(cè)為真，實(shí)際為真；錯(cuò)誤肯定（False Posi?tive，F(xiàn)P）：預(yù)測(cè)為真，實(shí)際為假。并通過(guò)計(jì)算該算法的查準(zhǔn)率和查全率驗(yàn)證其效率，其計(jì)算公式如下：

3.2 實(shí)驗(yàn)結(jié)果分析

為了提高實(shí)驗(yàn)效率，將數(shù)據(jù)集隨機(jī)整合為4組數(shù)據(jù)進(jìn)行測(cè)試，第一組包含250篇，第二組包含300篇，第三組300篇，第四組150篇.并計(jì)算四組數(shù)據(jù)的查準(zhǔn)率和查全率如表1所示。

表1 敏感詞過(guò)濾結(jié)果

圖5 敏感詞過(guò)濾結(jié)果

此外，對(duì)實(shí)驗(yàn)中的變形敏感詞過(guò)濾結(jié)果進(jìn)行分析，對(duì)于變形敏感詞的查全率和查準(zhǔn)率，公式（1）、（2）同樣適用。其結(jié)果如表2所示。

表2 變形敏感詞過(guò)濾結(jié)果

圖6 變形敏感詞過(guò)濾結(jié)果

通過(guò)對(duì)以上實(shí)驗(yàn)數(shù)據(jù)分析，敏感詞的平均查全率為 97.65%，相比 ST-DFA算法查全率 95.46%高2.19%，平均查準(zhǔn)率上為96.26%，較ST-DFA算法高1.23%。在對(duì)變形敏感詞的過(guò)濾的平均查全率到達(dá)了92.49%，達(dá)到了較高的變形敏感詞過(guò)濾效果。

4 結(jié)語(yǔ)

本文通過(guò)對(duì)網(wǎng)絡(luò)中普遍存在的變形敏感詞進(jìn)行了分類匯總，根據(jù)其特點(diǎn)構(gòu)建一棵改進(jìn)的Trie樹(shù)。并通過(guò)對(duì)文本進(jìn)行文本預(yù)處理，采用變形敏感詞匹配等算法進(jìn)行文本過(guò)濾。通過(guò)多次實(shí)驗(yàn)表明，該算法不僅能有效地檢測(cè)出文本中在敏感詞庫(kù)中存在的敏感詞，還能檢測(cè)出各類變形敏感詞，提高了文本檢測(cè)的精度和廣度。下一步工作將對(duì)變形敏感詞進(jìn)行更加細(xì)化、規(guī)范的分類，進(jìn)一步提高變形詞過(guò)濾的精度。