一種基于DFA的短文本信息過濾算法

關(guān)興義，趙 敏，伍文昌

（陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007）

0 引言

隨著信息技術(shù)的不斷發(fā)展和智能手機(jī)的普及，移動互聯(lián)網(wǎng)已逐步滲透至人們工作、生活的方方面面，大量的聊天消息、評論、新聞等碎片化信息在網(wǎng)絡(luò)中傳播，且數(shù)量呈上升趨勢，這類信息通常以短文本為主［1］。本文所指的短文本是按照微軟發(fā)布的關(guān)系數(shù)據(jù)庫管理系統(tǒng)Access 中文本數(shù)據(jù)類型的分類，短文本的長度不超過255 個字符。如今，信息傳遞越來越便利，言論發(fā)表越來越自由，網(wǎng)絡(luò)信息中更加容易出現(xiàn)帶有敏感政治、暴力、色情、不文明等傾向的敏感詞匯。因此，對通信過程中大量傳播的短文本信息進(jìn)行過濾是十分必要的。短文本信息具有字符數(shù)量少、上下文信息缺乏、語義模糊等特點(diǎn)，如何快速、精準(zhǔn)地在海量數(shù)據(jù)中過濾敏感信息，成為亟需解決的重要問題。

1 相關(guān)研究

早期，文本過濾使用簡單的蠻力匹配算法BF（Brute Force）算法。1975 年，Aho 等［2］提出一種經(jīng)典的多模式匹配算法AC（Aho-Corasick）算法，該算法對英文文本具有很好的匹配效果，但是漢語詞匯數(shù)量龐大，其利用失敗指針匹配字符的方式，對中文詞語的匹配達(dá)不到理想狀態(tài)。1977 年，Knuth 等［3］在BF 算法基礎(chǔ)上提出KMP（Knuth Morris Pratt）模式匹配算法，該算法在匹配過程中遇到失配字符時，模式串會根據(jù)已匹配成功的子串向右移動最大距離，相比于BF 算法每次只移動1 個距離，KMP 算法雖然更加高效，但對中文詞匯的匹配效果仍不夠好。

基于確定有限狀態(tài)自動機(jī)（Deterministic Finite Automata，DFA）的過濾算法是目前針對中文文本較為理想的過濾算法。文獻(xiàn)［4］提出的傳統(tǒng)DFA 算法匹配檢測時空效率較高，但未對敏感詞的變形體進(jìn)行有效匹配。文獻(xiàn)［5］提出基于DFA 過濾算法的改進(jìn)設(shè)計(jì)，改進(jìn)后的算法能夠有效過濾出部分敏感詞的變形體，解決特定的人工干擾問題。但由于中文漢字?jǐn)?shù)量龐大，詞匯組合種類繁多，漢語運(yùn)用情景復(fù)雜，不同的過濾算法在不同場景中應(yīng)用的效果不同。

本文設(shè)計(jì)了基于DFA 的短文本信息過濾算法，依據(jù)敏感詞出現(xiàn)的頻率構(gòu)建敏感詞樹，相比于傳統(tǒng)的DFA 過濾算法［4］，其時間復(fù)雜度雖然沒有改變，但實(shí)際運(yùn)行時間更短。通過對敏感詞庫擴(kuò)充敏感詞變形體，去除干擾字符，在SWDT-IFA 算法對敏感信息過濾具有90%以上查準(zhǔn)率和查全率的基礎(chǔ)上［5］，其對短文本信息的過濾效果提升到95%以上。文獻(xiàn)［6］關(guān)于敏感詞過濾的研究雖然小幅提升了過濾效果，但其采用最大匹配原則，而本文算法使用最小匹配原則，對短文本中敏感詞的過濾效果更好。

2 文本信息過濾相關(guān)技術(shù)

2.1 文本過濾主要問題

本文的文本過濾與模式串匹配相類似［7］，是指從文本數(shù)據(jù)流中查找滿足用戶需求的特定文本，預(yù)先給定一個輸入文本流和一個用戶需求，根據(jù)用戶需求建立一個初始模板，并判斷流中的每一文本是否符合用戶需求，然后將符合用戶需求的文本反饋給用戶，再根據(jù)評判情況修改模板。其中用戶需求的特定文本就是敏感詞，本文敏感詞字?jǐn)?shù)范圍限定為不小于2，且不大于5。

2.1.1 敏感詞變形體識別

信息發(fā)布者為確保信息順利發(fā)出，使用變形后的敏感詞表達(dá)原有詞匯含義，以防止信息被過濾，本文主要解決中拼混合、詞語簡寫、詞語拆分3種變形詞的識別問題。

（1）中拼混合。用敏感詞的拼音替代漢字或者拼音與漢字混合的方式表達(dá)詞語含義，例如“新冠”為敏感詞，可以通過變形為“xinguan”“新guan”等中拼混合形式。文獻(xiàn)［8］提出基于易混拼音分組的敏感詞識別算法，用于識別敏感詞拼音的變形體。

（2）詞語簡寫。是指用詞語縮寫的方式替換原有詞語，而不影響正常語義的表達(dá)。最常用的簡寫方式是用拼音的首字母表示，例如“新冠肺炎”簡寫成“xgfy”。

（3）詞語拆分。是指將組成詞語的漢字進(jìn)行拆分，比如將敏感詞“新冠”拆分成“親斤冠”。文獻(xiàn)［9］根據(jù)漢字特征對敏感詞中的漢字進(jìn)行人工拆分，然后采用區(qū)位碼進(jìn)行編碼，對照形成漢字拆分表。通過人工更新拆分表，可以提升對敏感詞拆分體識別的準(zhǔn)確度，比如敏感詞為“紙巾”，既可以拆分為“絲氏巾”，也可以拆分為“纟氏巾”。

2.1.2 敏感詞識別的準(zhǔn)確性

不同的過濾算法在不同場景下對敏感詞的識別有一定差異，因此對敏感詞的識別存在誤判情況，正常的敏感詞無法完全識別，而正常表達(dá)的詞語也可能被誤認(rèn)為是敏感詞。有的信息發(fā)布者會在敏感詞中夾雜無意義符號，比如表達(dá)成“新*&冠”等，會影響敏感詞識別的準(zhǔn)確性。敏感詞識別的準(zhǔn)確性可用查準(zhǔn)率來衡量，如式（1）所示。

2.1.3 算法時空效率

算法的時空效率包含時間效率和空間效率兩方面。算法的時間效率是指算法的執(zhí)行時間隨問題規(guī)模的增長而增長的趨勢，通常采用時間復(fù)雜度（time complexity）來度量［10］。時間效率是評價(jià)算法好壞的重要標(biāo)準(zhǔn)，為了不影響信息發(fā)送的時效性，過濾算法的時間復(fù)雜度應(yīng)盡可能降低。隨著時間復(fù)雜度的降低，往往會消耗空間資源。由于存儲空間的大小是有限的，因此空間復(fù)雜度也不能無限度地增長［11-12］，需要綜合衡量時間效率和空間效率，對算法作出優(yōu)化。文獻(xiàn)［13］提出的一種DFA 壓縮算法，在不影響匹配速度的前提下，實(shí)現(xiàn)了對存儲空間的壓縮。

2.2 DFA算法介紹

有限自動機(jī)（Finite Automata，F(xiàn)A）具有與正規(guī)表達(dá)式和正規(guī)文法等價(jià)的語言定義能力，使用有限自動機(jī)構(gòu)造詞法分析程序是一種比較好的實(shí)現(xiàn)途徑［14］。有兩種不同的有限自動機(jī)：確定有限自動機(jī)（Deterministic Finite Automata，DFA）、非確定有限自動機(jī)（Nondeterministic Finite Automata，NFA）。DFA 是文本主導(dǎo)，NFA 是表達(dá)式主導(dǎo)，在文本信息過濾上，DFA 的匹配速度更快。

圖1 中的圓圈表示DFA 的狀態(tài)，狀態(tài)名稱為q0、q1、q2、q3 和q4，每個狀態(tài)有帶標(biāo)記的有向邊射出，本文稱這些帶標(biāo)記的有向邊為轉(zhuǎn)移（transitions）。DFA 中僅有一個狀態(tài)用箭頭標(biāo)記為開始狀態(tài)（start state）。q0 是開始狀態(tài)，0 個或多個狀態(tài)用雙圈標(biāo)記為接受狀態(tài)（accept state），所有不是接受的狀態(tài)是拒絕狀態(tài)（reject state），q2 和q3 是接受狀態(tài)，q0、q1和q4是拒絕狀態(tài)。

Fig.1 DFA status transition圖1 DFA狀態(tài)轉(zhuǎn)移

一個確定有窮自動機(jī)可以用一個五元式描述：M=(Q，∑，δ，q0，Z)，以圖1 為例，具體描述如下：①有窮的非空狀態(tài)集合Q={q0，q1，q2，q3，q4}；②輸入字母表∑={b，c}；③初始狀態(tài)q0∈Q；④接受狀態(tài)集合A={q2，q3}?Q；⑤狀態(tài)轉(zhuǎn)換函數(shù)δ。這些有向邊構(gòu)成一個函數(shù)，映射每個狀態(tài)/字符到一個狀態(tài)（有向邊指向的狀態(tài)），為Q×∑到Q的單值映射，δ(q，a)=q′(q′稱為q的后繼狀態(tài)，q、q′∈Q，a∈∑)。

若對自動機(jī)M=(Q，∑，δ，q0，A)輸入一段字符串x，x∈∑*，有δ(q0，x)=p，p∈A，則稱x為自動機(jī)M 所接受的。

3 短文本信息過濾算法設(shè)計(jì)

3.1 過濾算法總體設(shè)計(jì)

圖2 為本文算法設(shè)計(jì)的總體思路。第一步是對敏感詞進(jìn)行預(yù)處理，通過中拼混合、詞語簡寫、詞語拆分對敏感詞庫進(jìn)行擴(kuò)建，然后將擴(kuò)建后的敏感詞庫按照敏感詞出現(xiàn)的頻率進(jìn)行排序；第二步構(gòu)建敏感詞樹，利用擴(kuò)建后的敏感詞庫構(gòu)建Trie 樹；第三步過濾目標(biāo)文本，將目標(biāo)文本與敏感詞相匹配，匹配過程中跳過無意義字符的干擾，識別出的敏感詞被屏蔽后輸出文本信息。

Fig.2 Overall design of the filtering algorithm圖2 過濾算法總體設(shè)計(jì)

3.2 敏感詞預(yù)處理

本文根據(jù)原始的敏感詞設(shè)計(jì)對敏感詞預(yù)處理的算法，將其擴(kuò)展為中拼混合、詞語簡寫、詞語拆分的敏感詞庫，使得變形后的敏感詞也可以被過濾。本文敏感詞庫擴(kuò)展算法設(shè)計(jì)的執(zhí)行過程有4個步驟：

步驟1：敏感詞轉(zhuǎn)換為拼音，首先建立一個文本文件存儲漢字unicode 編碼與拼音的對應(yīng)關(guān)系，用數(shù)據(jù)流的方式讀取，然后將unicode 碼和拼音存入到一個關(guān)聯(lián)式容器中，unicode 碼為鍵，拼音為值，通過漢字編碼獲取對應(yīng)的拼音。針對多音字的特殊情形，將多音字詞組組合起來，以正確的拼音為鍵，詞組為值，保存到一個關(guān)聯(lián)容器中。獲取目標(biāo)詞組中的漢字拼音時，先判斷當(dāng)前讀取的漢字是否為多音字，如果是多音字，則用拼音在容器中查找目標(biāo)詞組，若找到目標(biāo)詞組，則該拼音為當(dāng)前讀取漢字的正確拼音，如沒找到，則給其一個默認(rèn)的拼音。

步驟2：敏感詞轉(zhuǎn)換為簡寫模式，本文的詞語簡寫采用將敏感詞轉(zhuǎn)換成首字母簡寫的方式。具體方式是在將敏感詞轉(zhuǎn)換為拼音模式的基礎(chǔ)上，取得拼字字符串的首字母。

步驟3：敏感詞轉(zhuǎn)換為拆分模式，根據(jù)漢字的部件對敏感詞中的漢字進(jìn)行拆分，部件是現(xiàn)代漢字的構(gòu)字單位［15］。由一個部件構(gòu)成的漢字稱為獨(dú)體字，例如“羊”“牛”等，不需要再進(jìn)行拆分。合體字是指由兩個或兩個以上單字組成的漢字，是需要拆分的。本文在拆分時按照漢字部件的布局拆分，例如“明”拆分為“日，月”。通過建立字庫文檔存儲漢字對應(yīng)的拆分模式，并通過查詢漢字對應(yīng)的拆分模式實(shí)現(xiàn)對拆分詞的識別。

步驟4：將擴(kuò)建的敏感詞加入敏感詞庫。將通過中拼混合、詞語簡寫、詞語拆分后的敏感詞加入敏感詞庫，圖3以敏感詞“新冠”為例展示擴(kuò)展后的敏感詞，然后按照敏感詞出現(xiàn)的頻率，對敏感詞進(jìn)行排序，將排序后的敏感詞依次加入構(gòu)建的Trie樹中，完成敏感詞擴(kuò)建。

Fig.3 Sensitive word expansion圖3 敏感詞擴(kuò)建

3.3 敏感詞Trie樹構(gòu)建

根據(jù)擴(kuò)建后的敏感詞庫構(gòu)建Trie 樹，本文利用敏感詞構(gòu)建Trie 樹的過程如下：①定義Trie 樹；②根據(jù)敏感詞初始化Trie 樹；③將初始化后的敏感詞樹構(gòu)成DFA 狀態(tài)機(jī)。構(gòu)建Trie 樹的重點(diǎn)在于初始化過程，將每個詞的公共前綴共享一個分支，在匹配過程中輸入的下一個字符決定了下一步狀態(tài)。假設(shè)敏感詞為“香蕉”“香瓜”“香蕉醬”“香蕉樂園”“蘋果”“蘋果樂園”，圖4 是使用Map 容器構(gòu)建的Trie樹，輸入的每個字符作為當(dāng)前匹配的鍵（Key），也是上一輪匹配對應(yīng)值（Value）的一部分。當(dāng)值為 1 時，標(biāo)志著從開始到當(dāng)前輸入的字符串為一個敏感詞，說明敏感詞匹配成功。

Fig.4 Sensitive word tree structure圖4 敏感詞樹結(jié)構(gòu)

3.4 過濾過程算法設(shè)計(jì)

本文算法根據(jù)目標(biāo)文本的特征進(jìn)行設(shè)計(jì)［16］，由于短文本信息具有字符數(shù)量少的特點(diǎn)，文本中存在的敏感詞通常同樣字符數(shù)量較少，完成敏感詞擴(kuò)展并初始化Trie 樹后，采用最小匹配原則對目標(biāo)文本中的敏感詞進(jìn)行檢索和過濾。最小匹配原則是指匹配盡可能少的字符，即一旦遇到與敏感詞相匹配的文本時，該部分文本內(nèi)容便會被判定為敏感文本，從而被屏蔽掉。比如“新冠”和“新冠肺炎”同為敏感詞，當(dāng)目標(biāo)文本中出現(xiàn)“新冠肺炎”時會屏蔽“新冠”而不是屏蔽“新冠肺炎”。在匹配過程中，只需將目標(biāo)文本匹配一遍，便能夠完成過濾過程。具體過濾過程的偽代碼描述如下：

算法1過濾算法

本文過濾算法采用最小匹配原則，一旦遇到敏感詞的匹配成功標(biāo)志符，就會判定為敏感詞并結(jié)束，然后從下一個字符開始繼續(xù)查找敏感詞。

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

具體實(shí)驗(yàn)環(huán)境如下：CPU 為Intel i5-8250U，1.6GHz，內(nèi)存為8GB，操作系統(tǒng)為64 位Windows10，采用Java 語言實(shí)現(xiàn)。分別通過實(shí)驗(yàn)比較其他算法和本文設(shè)計(jì)的過濾算法對不同文本信息的過濾效果，圖5 為本文改進(jìn)后的DFA 算法實(shí)驗(yàn)結(jié)果。由圖5 可以看出，本文算法能夠有效檢測出敏感詞，并能避免中拼混合、詞語簡寫、詞語拆分的干擾。

Fig.5 Experimental results of the improved DFA algorithm圖5 改進(jìn)后的DFA算法實(shí)驗(yàn)結(jié)果

4.1 短文本信息過濾結(jié)果

目標(biāo)文本來自網(wǎng)絡(luò)中提供的大規(guī)模中文對話數(shù)據(jù)集，分別比對3 649、2 680、3 556、2 434 條對話文本信息，每條對話的字符數(shù)量不超過255 個。實(shí)驗(yàn)采用SWDT-IFA 算法和本文設(shè)計(jì)的過濾算法分別對目標(biāo)文本進(jìn)行過濾，實(shí)驗(yàn)結(jié)果如表1、表2所示。

Table 1 Filtering results of the proposed algorithm表1 本文算法過濾結(jié)果

根據(jù)表1 和表2 比對的實(shí)驗(yàn)結(jié)果可以看出，在沒有干擾的情況下，兩種算法的查準(zhǔn)率均達(dá)到100%，誤報(bào)率都為0%。與SWDT-IFA 算法相比，本文使用人工更新后的敏感詞拆分表，在查找目標(biāo)文本敏感詞過程中識別干擾字符，抗干擾能力得到提升。在有干擾的情況下，查準(zhǔn)率保持在95%以上，敏感詞匹配的查準(zhǔn)率平均提高3.0%，誤報(bào)率平均降低0.87%，驗(yàn)證了算法在檢測率上的改進(jìn)。在算法運(yùn)行時間上，由于每次程序運(yùn)行受系統(tǒng)調(diào)度、系統(tǒng)負(fù)載等因素影響，不是每一次實(shí)驗(yàn)運(yùn)行時間都有所減少，通過多次實(shí)驗(yàn)比較，本文按照敏感詞出現(xiàn)的頻率構(gòu)造敏感詞樹，在查找敏感詞的運(yùn)行時間上，每處理1 萬字的內(nèi)容平均用時減少12ms。

Table 2 Filtering results of SWDT-IFA algorithm表2 SWDT-IFA算法過濾結(jié)果

4.2 干擾類型對過濾效果的影響

本實(shí)驗(yàn)中，將文本內(nèi)容隨機(jī)分為4 組進(jìn)行測試：第一組為50 篇文本信息，第二組為150 篇，第三組為250 篇，第四組為350 篇。分別根據(jù)中拼混合、詞語簡寫、詞語拆分3種變形體模式構(gòu)建敏感詞庫，然后逐一與RSWDT 算法對比過濾4組文本信息的效果［9］，如圖6所示。

Fig.6 Experimental results of different interference types圖6 不同干擾類型實(shí)驗(yàn)結(jié)果

通過分析實(shí)驗(yàn)結(jié)果可以看出，本文改進(jìn)后的DFA 算法與RSWDT 算法相比，在中拼混合和詞語簡寫上的查準(zhǔn)率變化不明顯。因人工更新了敏感詞拆分表，所以對敏感詞拆分的變形體過濾效果明顯提升。由于很多詞匯的簡寫內(nèi)容相同，使得詞語簡寫的識別準(zhǔn)確率較低，不通過上下文分析很難判斷準(zhǔn)確，因此實(shí)驗(yàn)中對其識別的準(zhǔn)確率普遍偏低。

4.3 長文本過濾實(shí)驗(yàn)結(jié)果

隨機(jī)選擇字符數(shù)量分別為100、1 000、2 000、5 000 的網(wǎng)絡(luò)文本，按照字符數(shù)量將目標(biāo)文本分為4 組，分別用本文算法對4 組文本進(jìn)行過濾，實(shí)驗(yàn)結(jié)果如圖7 所示。由圖7可以看出，本文設(shè)計(jì)的改進(jìn)算法隨著目標(biāo)文本長度的增長，查準(zhǔn)率呈下降趨勢后，其中目標(biāo)文本長度為100 個字符和1 000 個字符的過濾性能變化最為明顯。隨著目標(biāo)文本字符數(shù)量的增加，查準(zhǔn)率下降，說明在文本長度改變時對算法的過濾效果存在影響，本文算法對于字符數(shù)量少的文本具有更好的過濾性能。性能變化的原因在于本文使用的是最小匹配原則，短文本中更容易使用簡短的詞語表達(dá)相同語義。比如，短文本中使用“新冠”的頻率遠(yuǎn)高于“新冠肺炎”，本文可以有效識別出敏感詞“新冠”，但對于含有敏感詞“新冠肺炎”的目標(biāo)文本不能有效識別。

Fig.7 Experimental results of target texts with different length圖7 不同長度目標(biāo)文本實(shí)驗(yàn)結(jié)果

5 結(jié)語

本文基于短文本信息過濾的既定場景，設(shè)計(jì)了決策樹的確定自動機(jī)算法。算法的復(fù)雜度與敏感詞數(shù)據(jù)庫的大小無關(guān)，只與敏感詞長度和目標(biāo)文本長度有關(guān)，通過在過濾目標(biāo)文本前對敏感詞進(jìn)行預(yù)處理，對敏感詞匯進(jìn)行擴(kuò)展和改進(jìn)，提升了敏感詞匹配的精準(zhǔn)度。實(shí)驗(yàn)結(jié)果表明，該算法能夠有效檢測出文本中的敏感詞，并對短文本信息有著較好的檢測效果，可以實(shí)踐運(yùn)用于移動網(wǎng)絡(luò)敏感信息過濾，實(shí)時凈化網(wǎng)絡(luò)環(huán)境。本文設(shè)計(jì)的算法對部分特定干擾字符的抗干擾能力弱，比如“！”“。”等字符既可以成為干擾字符，又可以成為正常文本符號，此類干擾字符的存在會降低算法過濾效果。要進(jìn)一步提高敏感詞過濾的精準(zhǔn)度，還應(yīng)考慮更多干擾方式，比如信息發(fā)送者利用同音字替換敏感詞，或者用地方方言表示敏感詞的含義將難以被識別。下一步將逐步進(jìn)行深入研究，綜合考慮影響過濾效果的因素，提升算法的時空效率，進(jìn)一步提高對文本中敏感詞過濾的效果，擴(kuò)大算法的適用范圍。