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

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

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

0 引 言

近年來(lái)隨著互聯(lián)網(wǎng)的發(fā)展和對(duì)外門戶的開放，我國(guó)與東南亞地區(qū)的交流日益頻繁，大量參差不齊的跨境語(yǔ)言產(chǎn)品涌入其中，給跨境語(yǔ)言網(wǎng)絡(luò)的輿情監(jiān)管工作帶來(lái)了一定的挑戰(zhàn)?？缇痴Z(yǔ)言網(wǎng)絡(luò)缺乏有效的技術(shù)和統(tǒng)一的管理，大量有關(guān)政治、宗教等敏感信息充斥其中，給區(qū)域穩(wěn)定和社會(huì)和諧帶來(lái)了極大的威脅。由于跨境語(yǔ)言網(wǎng)絡(luò)上的敏感內(nèi)容大多以文本形式呈現(xiàn)，因而對(duì)文本敏感信息的檢測(cè)和過(guò)濾成為了維護(hù)跨境網(wǎng)絡(luò)輿情安全的關(guān)鍵技術(shù)之一，其相關(guān)算法的研究則顯得尤為重要。

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

目前，針對(duì)老撾文的敏感信息檢測(cè)和過(guò)濾技術(shù)尚沒(méi)有獨(dú)立的模型和算法，但是對(duì)于中文的敏感信息識(shí)別和過(guò)濾問(wèn)題已經(jīng)取得了較多的研究成果。本文在研究了老撾文語(yǔ)言特點(diǎn)的基礎(chǔ)上，提出了一種基于確定有窮自動(dòng)機(jī)(Deterministic Finite Automaton，DFA)[2]和決策樹(Decision Tree，DT)[3]的老撾文敏感信息過(guò)濾算法LDTDFA(Laos Decision tree DFA)，實(shí)現(xiàn)了老撾文敏感信息的檢測(cè)、過(guò)濾和報(bào)警，并取得了較好的過(guò)濾效果。

1 相關(guān)工作

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

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

文獻(xiàn)[10]提出了一種敏感信息決策樹過(guò)濾算法，通過(guò)構(gòu)建敏感詞決策樹的方式提高了檢測(cè)效率，并通過(guò)給出敏感詞權(quán)重的方式實(shí)現(xiàn)敏感信息的檢測(cè)和過(guò)濾。該方法依賴人工標(biāo)記敏感級(jí)別，難以客觀地表現(xiàn)文本的敏感程度，而且沒(méi)有實(shí)現(xiàn)決策樹的實(shí)時(shí)更新以及敏感詞的屏蔽替換。

文獻(xiàn)[11]針對(duì)中文拼音的特點(diǎn)，提出一種基于確定有窮自動(dòng)機(jī)(DFA)的改進(jìn)算法，通過(guò)敏感詞拼音的第一個(gè)字母來(lái)構(gòu)建敏感信息決策樹，相比較于傳統(tǒng)的DFA過(guò)濾算法[12]嚴(yán)重依賴于敏感信息語(yǔ)料庫(kù)且匹配檢測(cè)重復(fù)率高的缺點(diǎn)，其優(yōu)點(diǎn)是不依賴敏感信息語(yǔ)料庫(kù)，實(shí)現(xiàn)了敏感信息決策樹的實(shí)時(shí)更新，提高了檢測(cè)和過(guò)濾的效率。DFA算法是一種面向網(wǎng)絡(luò)安全檢測(cè)的高效匹配算法，它幾乎可以處理任意類型的字符匹配操作。

2 算法設(shè)計(jì)

2.1 準(zhǔn)備階段

要想實(shí)現(xiàn)對(duì)老撾文的敏感信息過(guò)濾，首先需要進(jìn)行以下三個(gè)準(zhǔn)備步驟。第一，實(shí)現(xiàn)老撾文內(nèi)容語(yǔ)料采集以及文本預(yù)處理；第二，對(duì)老撾文進(jìn)行詞匯劃分和詞干提??；第三，由于老撾文結(jié)構(gòu)、語(yǔ)法與編碼的特殊性，需要對(duì)老撾文進(jìn)行編碼化處理。準(zhǔn)備階段的過(guò)程如圖1所示。

圖1 準(zhǔn)備階段流程

2.1.1語(yǔ)料采集和文本預(yù)處理

目前對(duì)于信息采集有很多開源的工具，對(duì)于老撾文的語(yǔ)料采集并不困難，本文所用老撾文語(yǔ)料集主要來(lái)自紀(jì)錄片字幕翻譯中老雙語(yǔ)平行語(yǔ)料數(shù)據(jù)集，同時(shí)也通過(guò)老撾文網(wǎng)頁(yè)爬蟲的方式不斷完善補(bǔ)充老撾文語(yǔ)料集，已提取中老對(duì)齊語(yǔ)料文本近10 000條。

表1 阿拉伯?dāng)?shù)字與老撾數(shù)字對(duì)照表

2.1.2老撾文分詞

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

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

(1)

(2)

式中：N(x)為x對(duì)應(yīng)的歸一化因子，由式(3)計(jì)算可得：

(3)

2.1.3編碼化處理

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

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

表2 老撾文字母映射表

表3 老撾文聲調(diào)符號(hào)映射表

2.2 構(gòu)建老撾文敏感信息樹

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

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

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

老撾文敏感信息決策樹的構(gòu)建并不復(fù)雜，主要是創(chuàng)建一個(gè)根節(jié)點(diǎn)α以及包含映射符號(hào)的59個(gè)子節(jié)點(diǎn)，如圖3所示。接下來(lái)主要說(shuō)明一下老撾文敏感信息樹的更新算法，整個(gè)算法流程如圖4所示。其中，葉子節(jié)點(diǎn)代表該節(jié)點(diǎn)是老撾文敏感信息中最后一個(gè)字符，同時(shí)沒(méi)有子節(jié)點(diǎn)，用x表示；非葉子節(jié)點(diǎn)代表該節(jié)點(diǎn)不是老撾文敏感信息中最后一個(gè)字符，仍需繼續(xù)向它的子節(jié)點(diǎn)進(jìn)行匹配，用y表示；偽葉子節(jié)點(diǎn)代表該節(jié)點(diǎn)是老撾文敏感信息的最后一個(gè)字符，但存在子節(jié)點(diǎn)，用z表示；哨兵賦值表示是否需要按最大匹配原則繼續(xù)檢測(cè)敏感信息。

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

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

2.3 老撾文敏感信息的檢測(cè)和過(guò)濾

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

假設(shè)待過(guò)濾的老撾文語(yǔ)料集合為S={S1,…,Si}，其映射符號(hào)集為P*，老撾文敏感信息的起點(diǎn)表示Sm，Sij表示第i和j個(gè)敏感字之間的老撾文字符串，檢測(cè)到的敏感信息表示為Smi。則老撾文敏感信息的檢測(cè)和過(guò)濾算法如圖5所示。

圖5 老撾文敏感信息的檢測(cè)與過(guò)濾算法

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

3 實(shí) 驗(yàn)

3.1 評(píng)估指標(biāo)

為了評(píng)估本文所提算法的性能表現(xiàn)，本文引入以下三個(gè)評(píng)價(jià)指標(biāo)：

(1) 查全率(Precision)。

(4)

(2) 查準(zhǔn)率(Recall)。

(5)

(3) F1值(F1 score)。

(6)

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

本文所提出的面向老撾文的敏感信息過(guò)濾算法結(jié)合了決策樹和DFA算法的優(yōu)勢(shì)，不但實(shí)現(xiàn)了對(duì)老撾文的檢測(cè)和過(guò)濾，而且實(shí)現(xiàn)了敏感信息樹的實(shí)時(shí)更新，對(duì)于老撾文的編碼化處理更是提高了算法的效率和性能。本文算法的整體框架如圖6所示。

圖6 算法整體框架

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

表4 LDTDFA算法實(shí)驗(yàn)結(jié)果

由表4可以看出，本文所提的老撾文過(guò)濾算法取得了88.92%的查全率和 86.79%的查準(zhǔn)率，但是該算法在決策樹更新的過(guò)程中，其查全率、查準(zhǔn)率以及F1值下降了3～4個(gè)百分點(diǎn)，這說(shuō)明決策樹的更新會(huì)影響算法的性能。進(jìn)一步分析可得，這是由于在決策樹的更新過(guò)程中，部分新添加的敏感詞沒(méi)有及時(shí)完成節(jié)點(diǎn)的更新，導(dǎo)致進(jìn)行老撾文敏感信息過(guò)濾時(shí)會(huì)忽略掉這部分未添加完全的敏感詞，進(jìn)而造成了查全率、查準(zhǔn)率以及F1值的下降。但這僅僅發(fā)生在決策樹更新時(shí)，對(duì)整體敏感信息的過(guò)濾影響不大，所以本文提出算法還是可以較好地完成老撾文敏感信息檢測(cè)和過(guò)濾的任務(wù)。

3.3 算法復(fù)雜度分析

LDTDFA算法主要分為構(gòu)建敏感信息決策樹和敏感信息過(guò)濾兩部分，所以對(duì)于兩個(gè)階段分別進(jìn)行時(shí)間復(fù)雜度和空間復(fù)雜度的分析[15]。對(duì)于構(gòu)建敏感信息決策樹，其時(shí)間復(fù)雜度為O(logkn)級(jí)，空間復(fù)雜度主要與敏感信息決策樹的節(jié)點(diǎn)信息有關(guān)，為O(n)級(jí)，其中n為敏感信息語(yǔ)料集文本總條數(shù)；而對(duì)于老撾文敏感信息檢測(cè)和過(guò)濾，其時(shí)間復(fù)雜度主要與決策樹的規(guī)模有關(guān)，為O(h×m)級(jí)，其中h為決策樹的高度，m為待檢測(cè)的老撾文語(yǔ)料集文本總條數(shù)，空間復(fù)雜度則為決策樹的大小，即O(n)級(jí)。

4 結(jié) 語(yǔ)

本文通過(guò)研究老撾文的語(yǔ)言特點(diǎn)，結(jié)合了DFA強(qiáng)大的字符匹配優(yōu)勢(shì)和決策樹的分流特點(diǎn)，提出了一種面向老撾文的敏感信息過(guò)濾算法——LDTDFA算法。實(shí)驗(yàn)結(jié)果表明，該算法可以有效實(shí)現(xiàn)老撾文敏感信息的檢測(cè)、過(guò)濾以及報(bào)警，并取得了較好的查全率和查準(zhǔn)率。下一步的工作要在此基礎(chǔ)上繼續(xù)完善擴(kuò)大老撾文語(yǔ)料集，不斷優(yōu)化算法，進(jìn)一步提高算法的實(shí)時(shí)性和準(zhǔn)確性。