基于改進Trie樹的變形敏感詞過濾算法

葉情

（四川大學計算機學院，成都 610065）

0 引言

隨著互聯網的飛速發展，我們在享受網絡科技帶來便利的同時，各種非法言論（如反政治、暴力血腥、黃賭毒等）經常在網絡中蔓延，不可避免地受到這些信息的侵害。盡管有關部門已經采取一系列監控管理措施來優化網絡環境，但仍有不法分子通過各種手段在網絡中散播不利于網絡環境的言論，嚴重影響社會主義的精神文明建設。為改善網絡環境、減少不良信息傳播，在從法律、道德等方面進行約束的同時，還必須通過技術手段對網絡信息進行過濾，優化網絡環境。

目前，國內外對于敏感詞的識別研究形成了較為成熟的體系，并且廣泛應用于各大網絡平臺中。例如網易的易盾敏感詞過濾系統能有效識別出文本中的敏感詞。由于中文存在字詞結構復雜、語義多變、詞庫量大等特點，因此對于變形敏感詞的過濾處理存在較大困難。目前，對變形敏感詞的研究還處于起步階段，相關研究成果較少。文獻[10]針對變形敏感詞提出一種新的過濾算法，將文本中的特殊字符進行預處理轉為中文字符再進行檢測，該方法能檢測出一類特定敏感詞，提高了文本檢測的精度。文獻[11]采用機器學習的方法，將Bigram、詞干等作為特征值來對文本信息做分類處理，以檢測出變形敏感詞。文獻[7]提出一種基于語言的字符串匹配算法，該算法可以有效地識別發音相似的敏感詞，但對于其他類型的敏感詞缺乏分析。

基于以上研究，本文對常見變形敏感詞進行歸納分類，提出一種基于改進Trie樹的變形敏感詞過濾算法，不僅可以過濾普通敏感詞，對變形敏感詞的識別也起到了良好的效果。

1 敏感詞過濾算法預處理

1.1 變形敏感詞處理

經過對變形敏感詞的研究與分析，對現有的變形敏感詞進行了分類總結，將變形敏感詞大致分為以下3類：

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

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

第三類：經過拆分、繁體化的敏感詞，例如：“三去車侖工力”、“口馬口非”、“進寶”等。

1.2 文本分立預處理

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

對于英文字符串，常見的漢語拼音有409種組合。本文通過以正則匹配為核心進行拼音串識別，具體正則表達式如圖1所示，如果是拼音字符串，將正確分立成單個拼音；如果不能分立成拼音，則分立為單個英文字符。

圖1 正則表達式

1.3 基于中文的Trie樹構建

Trie樹的結點一般由英文字符組成，因此Trie樹一個節點一般具有26個子節點。而中文則不同，常見漢字有將近7000多個，若按照英文的Trie樹構建中文敏感詞Trie樹，將大大增加查找難度。因此，本文對英文Trie樹結構進行改進，以適應中文敏感詞Trie樹的構建。

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

圖2 中文敏感詞Trie樹

2 敏感詞過濾算法的具體實現

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

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

對于第一類敏感詞，特殊符號可能僅代替其中一個敏感詞字符，也可能僅僅是間隔其中的漢字，起到干擾作用，因此在匹配時分兩種情況進行模糊匹配。

例如敏感詞“法輪*法”，其匹配過程如圖3所示，當成功匹配“法輪”兩個字符后，下一個待匹配的字符為“*”。若“*”不替代敏感詞中的任何字符，則直接比較下個字符“法”與下層節點即第4層節點的字符，發現無法匹配。再將“法”與下一層即第5層節點的字符對比，發現剛好匹配，而這個匹配的節點同時為葉節點和終節點，所以本輪匹配結束。因此，我們認為檢測文本中的“法輪*法”與敏感詞庫中的“法輪大法”相匹配。同理，“法輪*功”則與“法輪功”匹配。

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

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

對于第二類變形詞，當遇到連續拼音串時，本文基于最大匹配原則，采用此正則表達式對拼音串進行分割，例如“Yeqing”可正確分割成“Ye qing”。在對拼音進行匹配時，由于匹配情況較為復雜，需要額外空間存儲節點，規定用pinYin數組存儲拼音串，用pre數組存儲待定匹配節點，用node數組存儲已匹配的節點。由于一個拼音可能對于多個漢字，因此在檢測拼音串時，pre數組存儲該拼音對應的所有節點。若上輪存在成功匹配的節點，則存入node中,本輪匹配將從pre數組中的子節點出發，直至匹配到終端節點為止。

算法1查找某個文本分立單元相匹配的所有子節點

3 實驗及結果分析

3.1 數據集處理

本實驗的環境為Intel i5處理器，8GB內存，編程語言為Java。實驗中敏感詞庫的敏感詞來源于國內幾大權威網站的敏感詞庫以及部分網絡新詞匯整理歸納而成。詞庫中的敏感詞一共4700個，在實驗過程中，詞庫會不斷進行更新。

首先對一個給定文本片段的敏感詞進行檢測，對比本文敏感詞檢測算法與文獻[7]中的ST-DFA算法的檢測結果如圖4所示。從結果中可看出，本文的敏感詞檢測算法對于變形敏感詞的過濾精度高于ST-DFA算法。

圖4 敏感詞檢測對比結果

為了進一步檢驗該算法的正確性，從全網數據庫中隨機抽取了含有疑似敏感詞的1000篇文本作為測試數據集。為了方便后續的結果統計，人工地將1000篇文章根據含有敏感詞類型進行分類匯總，其中普通敏感詞一共1376個，變形敏感詞274個，為減小實驗誤差，需要將變形詞的原型敏感詞加入詞庫中。對敏感詞檢測結果分可為兩種情況,正確肯定（True Posi?tive，TP）：預測為真，實際為真；錯誤肯定（False Posi?tive，FP）：預測為真，實際為假。并通過計算該算法的查準率和查全率驗證其效率，其計算公式如下：

3.2 實驗結果分析

為了提高實驗效率，將數據集隨機整合為4組數據進行測試，第一組包含250篇，第二組包含300篇，第三組300篇，第四組150篇.并計算四組數據的查準率和查全率如表1所示。

表1 敏感詞過濾結果

圖5 敏感詞過濾結果

此外，對實驗中的變形敏感詞過濾結果進行分析，對于變形敏感詞的查全率和查準率，公式（1）、（2）同樣適用。其結果如表2所示。

表2 變形敏感詞過濾結果

圖6 變形敏感詞過濾結果

通過對以上實驗數據分析，敏感詞的平均查全率為 97.65%，相比 ST-DFA算法查全率 95.46%高2.19%，平均查準率上為96.26%，較ST-DFA算法高1.23%。在對變形敏感詞的過濾的平均查全率到達了92.49%，達到了較高的變形敏感詞過濾效果。

4 結語

本文通過對網絡中普遍存在的變形敏感詞進行了分類匯總，根據其特點構建一棵改進的Trie樹。并通過對文本進行文本預處理，采用變形敏感詞匹配等算法進行文本過濾。通過多次實驗表明，該算法不僅能有效地檢測出文本中在敏感詞庫中存在的敏感詞，還能檢測出各類變形敏感詞，提高了文本檢測的精度和廣度。下一步工作將對變形敏感詞進行更加細化、規范的分類，進一步提高變形詞過濾的精度。