基于決策樹和DFA的老撾文敏感信息過濾算法

王藝皓 丁洪偉 王麗清 李 波 李 浩

1(云南大學信息學院 云南 昆明 650500) 2(云南大學科技處 云南 昆明 650500)

0 引 言

近年來隨著互聯網的發展和對外門戶的開放，我國與東南亞地區的交流日益頻繁，大量參差不齊的跨境語言產品涌入其中，給跨境語言網絡的輿情監管工作帶來了一定的挑戰。跨境語言網絡缺乏有效的技術和統一的管理，大量有關政治、宗教等敏感信息充斥其中，給區域穩定和社會和諧帶來了極大的威脅。由于跨境語言網絡上的敏感內容大多以文本形式呈現，因而對文本敏感信息的檢測和過濾成為了維護跨境網絡輿情安全的關鍵技術之一，其相關算法的研究則顯得尤為重要。

鑒于跨境語言的多樣性和復雜性，本文以老撾文為切入口，針對老撾文的語言特點，提出了一種面向老撾文的敏感信息過濾算法。經研究發現，老撾文有以下幾種特點：一是單詞構成復雜，一個老撾文單詞由輔音、元音和聲調共同組成，其音節字母和聲調的不同位置會對詞的含義產生影響，這給處理老撾文信息帶來了一定的難度；二是語法形式單一，老撾文屬于孤立型語言[1]，它只能通過虛詞和詞序的不同組合來表達含義，老撾文沒有像漢語那樣豐富的形式變化；三是句子詞匯切分度低，老撾文詞與詞之間沒有類似空格這樣明顯的分界符，需要選取一種合適的分詞方法對老撾文句子進行詞匯劃分；四是語料匱乏，由于老撾文沒有類似漢語、英語這樣龐大的語料集，因此它含有大量的未登錄詞，這會對分詞的精確程度產生一定的影響，進而給老撾文信息處理工作帶來了極大的挑戰。

目前，針對老撾文的敏感信息檢測和過濾技術尚沒有獨立的模型和算法，但是對于中文的敏感信息識別和過濾問題已經取得了較多的研究成果。本文在研究了老撾文語言特點的基礎上，提出了一種基于確定有窮自動機(Deterministic Finite Automaton，DFA)[2]和決策樹(Decision Tree，DT)[3]的老撾文敏感信息過濾算法LDTDFA(Laos Decision tree DFA)，實現了老撾文敏感信息的檢測、過濾和報警，并取得了較好的過濾效果。

1 相關工作

文獻[4-6]詳細介紹分析了老撾文的語言特點，為本文解決老撾文語法分析、詞匯劃分以及詞干提取提供了借鑒方法。對于老撾文分詞方面，如文獻[7]提出了最長音節匹配和命名實體相結合的混合方法，該方法雖簡單高效，但對于老撾文這樣的低資源語言來講，獲取高質量的語言資源難度較大，同時可移植性較差，不能很好地解決未登錄詞和歧義問題；文獻[8]提出了一種基于條件隨機場(Conditional Random Field,CRF)的老撾語分詞模型(LaoWS)，該模型把分詞問題當作字母序列標注任務，詞首用字母B表示，詞中用I表示，相當于將其轉化成了一個二分類問題。與基于詞典的方式[7]相比，在語料庫規模不大且測試語料相同的情況下，該模型實現了更高的準確率和召回率。所以選取一種高效率的分詞方法是保證老撾文敏感信息檢測效率的前提，更是實現老撾文敏感信息過濾的基礎。

文獻[9]提出了改進BM(Boyer Moore)算法，通過增大模式串移動的距離和失配時大的移動距離出現的概率，減少了窗口移動次數和字符比較次數，從而加快了匹配速度，提高了平均匹配效率。但是這種基于模式匹配的檢測算法應用于老撾文敏感信息的過濾中效果并不理想。

文獻[10]提出了一種敏感信息決策樹過濾算法，通過構建敏感詞決策樹的方式提高了檢測效率，并通過給出敏感詞權重的方式實現敏感信息的檢測和過濾。該方法依賴人工標記敏感級別，難以客觀地表現文本的敏感程度，而且沒有實現決策樹的實時更新以及敏感詞的屏蔽替換。

文獻[11]針對中文拼音的特點，提出一種基于確定有窮自動機(DFA)的改進算法，通過敏感詞拼音的第一個字母來構建敏感信息決策樹，相比較于傳統的DFA過濾算法[12]嚴重依賴于敏感信息語料庫且匹配檢測重復率高的缺點，其優點是不依賴敏感信息語料庫，實現了敏感信息決策樹的實時更新，提高了檢測和過濾的效率。DFA算法是一種面向網絡安全檢測的高效匹配算法，它幾乎可以處理任意類型的字符匹配操作。

2 算法設計

2.1 準備階段

要想實現對老撾文的敏感信息過濾，首先需要進行以下三個準備步驟。第一，實現老撾文內容語料采集以及文本預處理；第二，對老撾文進行詞匯劃分和詞干提取；第三，由于老撾文結構、語法與編碼的特殊性，需要對老撾文進行編碼化處理。準備階段的過程如圖1所示。

圖1 準備階段流程

2.1.1語料采集和文本預處理

目前對于信息采集有很多開源的工具，對于老撾文的語料采集并不困難，本文所用老撾文語料集主要來自紀錄片字幕翻譯中老雙語平行語料數據集，同時也通過老撾文網頁爬蟲的方式不斷完善補充老撾文語料集，已提取中老對齊語料文本近10 000條。

表1 阿拉伯數字與老撾數字對照表

2.1.2老撾文分詞

詞是自然語言中最小的有意義的構成單位，老撾文是由元音、輔音、尾輔音和聲調組成的多音節文字[4]，老撾語分詞就是將一連串的老撾語字符按一定的規則劃分成單個老撾詞語序列的過程。雖然針對老撾文詞法分析的相關研究相較于中英文起步較晚，但國內外已有實驗室設計并實現了準確率較高的老撾語分詞算法[8,13]，近些年有關老撾語命名實體識別的研究[6]也逐漸興起。老撾語分詞的準確率和效率都在逐步提高。由于CRF具有特征選取靈活、擬合程度好、訓練時間不長等優點，故本文選擇采用了基于條件隨機場(CRF)的老撾語分詞模型[8]，其基本原理如下：

假設x為觀測序列，y和y*為標注序列，αj為對應的權重因子，hj為j處的轉移特征函數，{Ri(x)|||i=1,2,…,n+1}為n+1個矩陣集合，每個Ri(x)均為|x×x|階矩陣，Ri(x)由式(1)計算得出，其矩陣元素的乘積如式(2)所示。

(1)

(2)

式中：N(x)為x對應的歸一化因子，由式(3)計算可得：

(3)

2.1.3編碼化處理

為了提高老撾文敏感信息過濾的算法效率，需要將老撾語的詞匯進行編碼化處理。這樣做的原因有以下三點：① 由于數據存儲格式編碼的差異性，處理后的老撾文語料集在輸出的過程中可能會由于編碼方式不當而出現亂碼問題；② 由于DFA算法和決策樹算法的特殊性，檢測到的敏感信息會以字母的形式輸出，難以重新還原成原本的詞；③ 由于老撾文元音字母和輔音字母的特殊關系，元音字母可以在輔音字母的前后、上下出現，同一個字母出現在詞匯的不同位置就會有不同的表達含義，同時聲調的存在也會影響詞表達意思的不同，這都給敏感信息的檢測帶來了一定的難度。

經過一系列的研究嘗試，對比了幾種不同的字符轉化方式的編碼解碼效果，綜合考慮了編碼解碼的易操作性、匹配的準確性以及對于老撾語詞結構的適用性，本文決定采用常見字符代表的方式進行編碼[14]。現行老撾文有33個輔音字母和28個元音字母，其中輔音相當于漢語中的聲母，元音相當于漢語中的韻母。輔音字母分為單輔音和復合輔音，元音字母分為短音和長音。基于老撾文詞的構成特點，本文將27個輔音字母映射為26個大寫英文字母和一個0，由于老撾官方已經公告廢除低輔音“”并以“”取代，但是民間仍然普遍使用，故在這里用“0”來映射以作區分；將28個元音字母用從1到9的阿拉伯數字和19個小寫英文字母進行映射；將4個聲調符號一一映射為小寫英文字母“o、p、q、u”。對于老撾文字母及聲調符號的映射關系如表2和表3所示。通過這樣的映射關系，老撾語的詞匯可以映射成由數字和大小寫英文符號組成的符號串，如“”(森林)映射成的編碼符號為“FoauWp”(書寫順序映射為從左到右，聲調符號映射書寫位置為該聲調下方字母映射符號順延一位)。通過字符映射的方式對老撾文語料集以及敏感信息語料集進行編碼化處理，這樣的做法不僅提高了敏感信息檢測的算法效率，同時也對后面老撾文的還原工作有著重要的意義。

表2 老撾文字母映射表

表3 老撾文聲調符號映射表

2.2 構建老撾文敏感信息樹

圖3 老撾文敏感信息決策樹

由圖3可以看出，本文構建的決策樹不僅體現了老撾文字母和編碼符號一一映射的關系，還包含了老撾文詞匯的上下文信息和順序信息，這為后文還原過濾后的老撾文提供了基礎。

假設老撾文敏感詞庫集合為D={d1,…,di,…,dn-1}，其中，1≤i

老撾文敏感信息決策樹的構建并不復雜，主要是創建一個根節點α以及包含映射符號的59個子節點，如圖3所示。接下來主要說明一下老撾文敏感信息樹的更新算法，整個算法流程如圖4所示。其中，葉子節點代表該節點是老撾文敏感信息中最后一個字符，同時沒有子節點，用x表示；非葉子節點代表該節點不是老撾文敏感信息中最后一個字符，仍需繼續向它的子節點進行匹配，用y表示；偽葉子節點代表該節點是老撾文敏感信息的最后一個字符，但存在子節點，用z表示；哨兵賦值表示是否需要按最大匹配原則繼續檢測敏感信息。

圖4 老撾文敏感信息樹更新算法

由圖4可得，該算法不僅實現了老撾文敏感信息樹的實時更新，而且具有較好的算法效率。

2.3 老撾文敏感信息的檢測和過濾

構建好老撾文敏感信息決策樹之后，接下來就要實現老撾文敏感信息的檢測和過濾。將預處理后的待過濾老撾文語料集以文本數據流的方式流經敏感信息樹：如果檢測到敏感信息，則立即彈出“檢測到敏感信息”的警示框，進行敏感信息的過濾，即敏感信息用“*”替換，輸出過濾后的老撾文語料集為“.txt”格式，并在控制臺輸出檢測到的敏感詞(注：在windows環境下輸出格式設為“gb2312”，默認的“utf8”格式輸出會出現亂碼)，同時輸出算法運行時間；如果未檢測到敏感信息，則彈出“未檢測到敏感信息”提示框，輸出老撾文語料集，并在控制臺輸出算法運行時間。

假設待過濾的老撾文語料集合為S={S1,…,Si}，其映射符號集為P*，老撾文敏感信息的起點表示Sm，Sij表示第i和j個敏感字之間的老撾文字符串，檢測到的敏感信息表示為Smi。則老撾文敏感信息的檢測和過濾算法如圖5所示。

圖5 老撾文敏感信息的檢測與過濾算法

由圖4和圖5可以共同看出，老撾文敏感信息決策樹的高度與敏感信息的長度有一定關系，但對于老撾文而言，其敏感詞長度是有限的，這有效降低了決策樹的高度對算法空間復雜度的影響，從而在一定程度上提高了本文算法效率。

3 實 驗

3.1 評估指標

為了評估本文所提算法的性能表現，本文引入以下三個評價指標：

(1) 查全率(Precision)。

(4)

(2) 查準率(Recall)。

(5)

(3) F1值(F1 score)。

(6)

3.2 實驗結果與分析

本文所提出的面向老撾文的敏感信息過濾算法結合了決策樹和DFA算法的優勢，不但實現了對老撾文的檢測和過濾，而且實現了敏感信息樹的實時更新，對于老撾文的編碼化處理更是提高了算法的效率和性能。本文算法的整體框架如圖6所示。

圖6 算法整體框架

由于算法主要采用了決策樹和文本信息最大匹配的方法，所以取得了不錯的查全率和查準率。其實驗結果如表4所示。其中，M表示文本敏感信息總條數(人工過濾)，Mtrue表示正確過濾敏感信息條數，Mwrong表示錯誤過濾敏感信息條數。

表4 LDTDFA算法實驗結果

由表4可以看出，本文所提的老撾文過濾算法取得了88.92%的查全率和 86.79%的查準率，但是該算法在決策樹更新的過程中，其查全率、查準率以及F1值下降了3～4個百分點，這說明決策樹的更新會影響算法的性能。進一步分析可得，這是由于在決策樹的更新過程中，部分新添加的敏感詞沒有及時完成節點的更新，導致進行老撾文敏感信息過濾時會忽略掉這部分未添加完全的敏感詞，進而造成了查全率、查準率以及F1值的下降。但這僅僅發生在決策樹更新時，對整體敏感信息的過濾影響不大，所以本文提出算法還是可以較好地完成老撾文敏感信息檢測和過濾的任務。

3.3 算法復雜度分析

LDTDFA算法主要分為構建敏感信息決策樹和敏感信息過濾兩部分，所以對于兩個階段分別進行時間復雜度和空間復雜度的分析[15]。對于構建敏感信息決策樹，其時間復雜度為O(logkn)級，空間復雜度主要與敏感信息決策樹的節點信息有關，為O(n)級，其中n為敏感信息語料集文本總條數；而對于老撾文敏感信息檢測和過濾，其時間復雜度主要與決策樹的規模有關，為O(h×m)級，其中h為決策樹的高度，m為待檢測的老撾文語料集文本總條數，空間復雜度則為決策樹的大小，即O(n)級。

4 結 語

本文通過研究老撾文的語言特點，結合了DFA強大的字符匹配優勢和決策樹的分流特點，提出了一種面向老撾文的敏感信息過濾算法——LDTDFA算法。實驗結果表明，該算法可以有效實現老撾文敏感信息的檢測、過濾以及報警，并取得了較好的查全率和查準率。下一步的工作要在此基礎上繼續完善擴大老撾文語料集，不斷優化算法，進一步提高算法的實時性和準確性。