基于Trie樹(shù)的關(guān)鍵詞匹配算法在電子政務(wù)領(lǐng)域的應(yīng)用

陳有偉 康磊

摘 要：傳統(tǒng)的行政管理方式隨著互聯(lián)網(wǎng)的高速發(fā)展，其效率低下的弊端已經(jīng)逐漸顯露。各級(jí)部門(mén)在依托互聯(lián)網(wǎng)快速發(fā)展的基礎(chǔ)上積極引進(jìn)現(xiàn)代互聯(lián)網(wǎng)技術(shù)，結(jié)合現(xiàn)有行政管理的基本方式形成了符合當(dāng)代環(huán)境的電子政務(wù)行政管理方式。民生訴求是電子政務(wù)的一個(gè)重要組成部分，保障和妥善解決民生問(wèn)題是職能部門(mén)的重要職責(zé)，是反映其辦事效率的一個(gè)窗口。然而由于民生訴求涉及到的投訴信息范圍廣、數(shù)量多、情況錯(cuò)綜復(fù)雜，這給職能部門(mén)快速處理民生訴求帶來(lái)了挑戰(zhàn)。本文通過(guò)在電子政務(wù)系統(tǒng)中引入基于Trie樹(shù)的關(guān)鍵詞匹配算法，對(duì)市民提交的信息進(jìn)行分析、匹配，從而快速分派到相應(yīng)部門(mén)處理、極大地提升了各部門(mén)處理事務(wù)的效率。

關(guān)鍵詞： 電子政務(wù);Trie樹(shù);模糊匹配;關(guān)鍵詞匹配

【Abstract】 With the rapid development of the Internet， the dilemma of the low efficiency of traditional administrative management methods has gradually emerged. On the basis of the rapid development of the Internet， departments at all levels actively introduce modern Internet technologies， and in combination with the basic methods of government administration， form an e-government administrative approach that conforms to the contemporary environment. People's livelihood appeal is an important part of e-government. Safeguarding and properly solving people's livelihood issues is an important duty of the department and a window reflecting the efficiency of department affairs. However， due to the wide range of complaints and the large number of complaints involved in the people's livelihood appeals， this has brought challenges to the department's rapid handling of people's livelihood demands. This paper introduces Trie tree based on keyword matching algorithm in the e-government system to analyze the information submitted by the citizens， and then quickly dispatch them to the corresponding departments for processing， which greatly increases the efficiency of the department's handling of affairs.

【Key words】 ?e-government; Trie tree; fuzzy matching; keyword matching

1 國(guó)內(nèi)外研究現(xiàn)狀

隨著經(jīng)濟(jì)社會(huì)的快速發(fā)展，民眾的訴求呈現(xiàn)出多樣化的趨勢(shì)，涵蓋著從醫(yī)療、就業(yè)、教育等大的方面，直至尋物、家政等小的方面在內(nèi)的眾多議題觀(guān)點(diǎn)[1]。研究可知，信息匹配技術(shù)在電子政務(wù)系統(tǒng)中是處理民生訴求的一項(xiàng)核心技術(shù)。如今，信息匹配技術(shù)在世界各國(guó)都取得了長(zhǎng)足進(jìn)步，依靠國(guó)家力量的支持，以信息匹配技術(shù)為核心的應(yīng)用系統(tǒng)也得以廣泛的發(fā)展[2]。斯坦福大學(xué)的特克和郝克特開(kāi)發(fā)了一種基于內(nèi)容的關(guān)鍵詞匹配系統(tǒng)SIFT（Standford Information Filtering T001） [3]。用戶(hù)憑借這個(gè)系統(tǒng)，能夠單獨(dú)創(chuàng)建屬于自己的詞匯庫(kù)，并通過(guò)使用相關(guān)關(guān)鍵字和空間模型來(lái)完成用戶(hù)的訴求和網(wǎng)絡(luò)信息內(nèi)容間的相互匹配。美國(guó)國(guó)家安全局為了應(yīng)對(duì)恐怖活動(dòng)、軍事威脅，建設(shè)了“Echelon”通信監(jiān)視網(wǎng)絡(luò)[4]，可以通過(guò)衛(wèi)星攔截大量包含個(gè)人信息的傳真、電話(huà)和電子郵件等，Echelon也是一個(gè)通過(guò)關(guān)鍵字匹配來(lái)獲取通信的電子通信系統(tǒng)[5-6]。在英國(guó)，一個(gè)專(zhuān)門(mén)收集情報(bào)機(jī)構(gòu)“英國(guó)政府技術(shù)援助中心”，在英國(guó)政府的主導(dǎo)下也隨之成立，這個(gè)援助中心可以獲取進(jìn)出英國(guó)網(wǎng)絡(luò)的所有信息[7]。

在國(guó)內(nèi)，由于信息匹配技術(shù)和文本處理技術(shù)革新的相繼問(wèn)世，相關(guān)科研機(jī)構(gòu)、高等院校以及公司，也設(shè)計(jì)了大量結(jié)合系統(tǒng)化技術(shù)的優(yōu)秀產(chǎn)品[8]。例如中科天鞏公司與中國(guó)科學(xué)院聯(lián)合設(shè)計(jì)研發(fā)的“天機(jī)網(wǎng)絡(luò)網(wǎng)頁(yè)關(guān)鍵字監(jiān)測(cè)系統(tǒng)”[9]。2009年1月國(guó)內(nèi)首個(gè)網(wǎng)絡(luò)關(guān)鍵字安全研究機(jī)構(gòu)在北京交通大學(xué)成立，如今該機(jī)構(gòu)正在全方位地推進(jìn)網(wǎng)絡(luò)關(guān)鍵字的產(chǎn)生、傳播和導(dǎo)控等方向的研究以及網(wǎng)絡(luò)輿論安全關(guān)鍵技術(shù)的研發(fā)[10]。北京大學(xué)方正技術(shù)研究院設(shè)計(jì)推出了“方正智思網(wǎng)頁(yè)關(guān)鍵字預(yù)警輔助決策支持系統(tǒng)” [11]，該系統(tǒng)依靠對(duì)網(wǎng)頁(yè)中的離線(xiàn)數(shù)據(jù)的自動(dòng)解析和預(yù)報(bào)，合理分析并規(guī)劃網(wǎng)頁(yè)關(guān)鍵字的監(jiān)控內(nèi)容，產(chǎn)生了一種具有生命周期特征的社情民意反饋系統(tǒng) [2]。

隨著國(guó)內(nèi)外對(duì)于網(wǎng)絡(luò)信息關(guān)鍵字的分析技術(shù)逐步成熟，關(guān)于信息匹配的軟件產(chǎn)品得到了大量推廣，國(guó)內(nèi)電子政務(wù)領(lǐng)域的處理流程得到了部分改善。但是在處理專(zhuān)用信息上，關(guān)鍵詞匹配技術(shù)還不夠完善。特別是，對(duì)于市民提交的民生訴求信息的識(shí)別技術(shù)也仍表現(xiàn)出一定不足，難以滿(mǎn)足智能化的要求，其準(zhǔn)確率和時(shí)效性也有待提高，存在許多問(wèn)題亟待解決。

2 基于關(guān)鍵字的布爾模型匹配算法

布爾模型因?yàn)閷?shí)現(xiàn)方式簡(jiǎn)單、匹配速度快、檢索方式易于用戶(hù)理解[12]等特點(diǎn)，在諸多領(lǐng)域得到了應(yīng)用，成為了網(wǎng)站搜索引擎使用的首選方案。布爾模型是結(jié)合集合論和布爾代數(shù)思想的簡(jiǎn)單數(shù)學(xué)模型，這種模型把文本信息中的關(guān)鍵詞從文本信息中提取出來(lái)，作為文本的特征值[13]。匹配過(guò)程也很簡(jiǎn)單，把匹配詞用“與”、“或”、“非”進(jìn)行連接就可以組成相應(yīng)的正則表達(dá)式，而后利用正則表達(dá)式與模型關(guān)鍵詞進(jìn)行對(duì)比得出匹配到的內(nèi)容是否存在于該文檔中。

設(shè)文檔di（i=1，2，3，…，n）為文本集D=（d1，d2，…，dn）中任意一個(gè)文檔，Ti=（t1，t2，…，tm）為文檔di標(biāo)引詞集，對(duì)于某檢索，形如Q=W1∧W2∧…∧Wn，如果存在W1∈Ti，W2∈Ti，Wi∈Ti，則稱(chēng)文檔di存在于檢索結(jié)果當(dāng)中，這里di為命中文檔，反之di為不命中文檔;對(duì)于檢索形式為Q=W1∨W2∨…∨Wn的檢索式，如若存在一個(gè)或多個(gè)Wk∈Ti，（k=1，2，…，n），則di為命中文檔，反之若不存在滿(mǎn)足條件的Wk∈Ti，（k=1，2，…，n），則di為不命中文檔[14]。

布爾模型的優(yōu)勢(shì)表現(xiàn)在其匹配速度快、實(shí)現(xiàn)方式簡(jiǎn)單等方面，但是這種模型的不足也十分明顯。對(duì)此可做闡釋分析如下。

（1）布爾模型對(duì)滿(mǎn)足其前提條件的文檔進(jìn)行匹配時(shí)容易造成遺漏。由于布爾模型擁有嚴(yán)格的匹配規(guī)則，關(guān)鍵字的選取如果稍有偏差就有可能會(huì)被過(guò)濾，例如當(dāng)使用“與”作為連接詞進(jìn)行匹配時(shí)，系統(tǒng)匹配僅僅只命中與匹配詞一致的文檔，但是那些和匹配詞不一致、內(nèi)容卻一致的文檔通常會(huì)被遺漏，所以如何選取合適的匹配詞就變得十分困難[15]。

（2）無(wú)法匹配重點(diǎn)結(jié)果。由于布爾模型匹配到的結(jié)果是一個(gè)大致的范圍，對(duì)于數(shù)據(jù)量小的情況比較適用，但是對(duì)于在電子政務(wù)領(lǐng)域逐步增長(zhǎng)的海量數(shù)據(jù)信息，布爾檢索在處理能力上的不足就顯得尤為突出。

（3）容易造成匹配結(jié)果的冗余。

（4）因?yàn)椴紶柶ヅ涞膶?shí)現(xiàn)方式過(guò)于簡(jiǎn)單、往往不能完全反映出想要的結(jié)果。

正是由于民生訴求包含的社會(huì)信息十分復(fù)雜、龐大，為了能快速地處理這些信息，引入了一種高效的數(shù)據(jù)結(jié)構(gòu)—Trie樹(shù)。

3 基于Trie樹(shù)的匹配算法

3.1 Trie樹(shù)

Trie樹(shù)也叫作字典樹(shù)，是對(duì)一組詞進(jìn)行結(jié)構(gòu)化處理后的組織 [16]。

其中，字典樹(shù)對(duì)含有相同前綴的詞進(jìn)行壓縮處理，使其所占用的空間得到了極大優(yōu)化。同時(shí)由于將相同公共前綴的詞放在了一起，則使得通過(guò)前綴進(jìn)行匹配也變得十分迅速。研究中構(gòu)建的一顆字典樹(shù)即如圖1所示。

字典樹(shù)通過(guò)從根節(jié)點(diǎn)到子節(jié)點(diǎn)的路徑來(lái)表達(dá)一個(gè)詞，圖1中e，f節(jié)點(diǎn)為一個(gè)詞的最后一個(gè)節(jié)點(diǎn)，也就是說(shuō)圖1字典樹(shù)代表的單詞有ade、ad、bd、cbf、cb。字典樹(shù)的根節(jié)點(diǎn)不表示任何字符。字典樹(shù)不僅節(jié)省了存儲(chǔ)空間，同時(shí)為模糊匹配技術(shù)的發(fā)展提供了堅(jiān)實(shí)的基礎(chǔ)。

3.2 構(gòu)造基于中文的Trie樹(shù)

英文Trie 樹(shù)的結(jié)點(diǎn)是由26個(gè)英文字母組成的，所以英文Trie樹(shù)的一個(gè)節(jié)點(diǎn)最多擁有26個(gè)子節(jié)點(diǎn)。但是中文卻不一樣，生活中常用的漢字就高達(dá)7 000多個(gè)，如果按照英文Trie樹(shù)的構(gòu)建法則來(lái)構(gòu)建中文Trie樹(shù)，將會(huì)極大地降低匹配的效率。因此如何構(gòu)造基于中文的Trie樹(shù)結(jié)構(gòu)就有著至關(guān)重要的研究意義。

比如，在向教育局投訴的信息中，根據(jù)教育局的相關(guān)關(guān)鍵詞構(gòu)建屬于教育局的Trie樹(shù)結(jié)構(gòu)，以關(guān)鍵詞“教育局”為例：

首先，基于拆詞的思想，利用正則表達(dá)式將關(guān)鍵詞“教育局”拆分為教、育、局三個(gè)字。

接著，檢查根節(jié)點(diǎn)是否已經(jīng)有字符“教”節(jié)點(diǎn)，如果已經(jīng)有這個(gè)節(jié)點(diǎn)，依次重復(fù)檢驗(yàn)并添加“育”、“局”兩個(gè)節(jié)點(diǎn)。如果沒(méi)有，則將“教”添加在根加點(diǎn)下。

最后，當(dāng)插入了每個(gè)關(guān)鍵詞時(shí)，在其末尾增加一個(gè)標(biāo)志符，使用這個(gè)字符作為此關(guān)鍵詞的結(jié)束標(biāo)志（如圖2中的灰色三角），利用這個(gè)字符來(lái)標(biāo)記查找到了這個(gè)關(guān)鍵詞。

循環(huán)插入所有關(guān)鍵詞。構(gòu)造出的中文Trie樹(shù)如圖2所示。

3.3 利用中文Trie樹(shù)解決中文匹配

以一則民生投訴為例：“我是X中初四學(xué)生家長(zhǎng)，聽(tīng)孩子說(shuō)上體育課跑操時(shí)老師大聲罵學(xué)生，有時(shí)還用腳踢學(xué)生，學(xué)生真害怕，3、4班的。請(qǐng)求幫助。”利用圖2已經(jīng)構(gòu)造好的中文Trie樹(shù)來(lái)開(kāi)始匹配。

首先，將投訴內(nèi)容利用正則表達(dá)式拆成單個(gè)字符“我”、“是”、…;從根節(jié)點(diǎn)處查找第一個(gè)字符“我”，并沒(méi)有查找到以“我”為首字符的關(guān)鍵詞，然后繼續(xù)移動(dòng)字符指針，直到查找到符合條件的字符節(jié)點(diǎn)“學(xué)”;接著在“學(xué)”這個(gè)字符節(jié)點(diǎn)下查找字符節(jié)點(diǎn)值為“生”的節(jié)點(diǎn)，成功找到時(shí)計(jì)算子樹(shù)的深度為2，關(guān)鍵詞的長(zhǎng)度是2，此時(shí)字符指針繼續(xù)移動(dòng)，如果發(fā)現(xiàn)結(jié)束標(biāo)志，就意味著匹配成功，將匹配到的關(guān)鍵詞返回，如果未碰到結(jié)束標(biāo)志則繼續(xù)向后移動(dòng)指針結(jié)點(diǎn)尋找下一個(gè)字符。

循環(huán)遍歷完畢，返回所有匹配到的關(guān)鍵詞。

3.4 Trie樹(shù)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

Trie樹(shù)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)采用PHP語(yǔ)言，結(jié)合了PHP數(shù)組的hash特性，代碼如下：

Private $root = array（

‘depth=>$depth，

// 深度，用來(lái)判斷命中的字?jǐn)?shù)

‘next=> array（

$val =>$node， // 使用PHP數(shù)組的hash結(jié)構(gòu)，增加子節(jié)點(diǎn)的查找速率

…

）

）

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

實(shí)驗(yàn)環(huán)境為MacBook Pro（Retina，15-inch，Mid 2015），處理器為2.2 GHz Intel Core i7，內(nèi)存16 GB 1600 MHz DDR3，使用PHP語(yǔ)言實(shí)現(xiàn)。實(shí)驗(yàn)中的給定文本內(nèi)容來(lái)源于某市民心網(wǎng)1 000個(gè)市民提交的訴求問(wèn)題。

將1 000個(gè)市民提交的問(wèn)題內(nèi)容分成4個(gè)小組，每組250篇，并計(jì)算其查全率、查準(zhǔn)率以及所耗時(shí)間。基于Trie樹(shù)結(jié)構(gòu)的關(guān)鍵詞匹配結(jié)果，見(jiàn)表1。

基于正則表達(dá)式的關(guān)鍵詞匹配結(jié)果，見(jiàn)表2。

要應(yīng)用在電子政務(wù)領(lǐng)域，至關(guān)重要的就是效率與準(zhǔn)確率。通過(guò)以上實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，與在電子政務(wù)系統(tǒng)中單純使用正則表達(dá)式相比，使用Trie樹(shù)結(jié)構(gòu)處理250條數(shù)據(jù)基本耗時(shí)在1 s左右，并且根據(jù)關(guān)鍵詞匹配到的結(jié)果，將其分發(fā)到命中的部門(mén)，準(zhǔn)確率基本都高達(dá)93%以上，明顯改善了處理民生訴求問(wèn)題的效率，符合電子政務(wù)領(lǐng)域的基本要求。

5 結(jié)束語(yǔ)

本文通過(guò)在電子政務(wù)系統(tǒng)中引入Trie樹(shù)這種效率極高的數(shù)據(jù)結(jié)構(gòu)結(jié)合正則表達(dá)式，極大地提高了匹配效率，使得職能部門(mén)在處理民眾訴求時(shí)，能夠及時(shí)將民眾反映的相關(guān)問(wèn)題分派到相應(yīng)的部門(mén)去辦理，優(yōu)化部門(mén)辦事效率，提升了民眾對(duì)職能部門(mén)的工作滿(mǎn)意度。

參考文獻(xiàn)

[1]麥范金， 李東普， 岳曉光. 基于雙向匹配法和特征選擇算法的中文分詞技術(shù)研究[J].昆明理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，36（1）：47-51.

[2]靳瑞敏. 網(wǎng)頁(yè)關(guān)鍵字過(guò)濾研究及改進(jìn)[D]. 呼和浩特：內(nèi)蒙古大學(xué)，2012.

[3]http：//zjnustdl.blogdriver.com/zjnustdl//1196699.html.

[4]俞文洋，張連堂，段淑敏. KMP模式匹配算法的研究[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版），2007，22（5）：64-66.

[5]HARALICK R M. Statistical and structural approaches to texture[J] . Proceedings of the IEEE， 1979，67（5）：786-804.

[6]TAMURA H， MORI S， YAMAWAKI T. Textural features corresponding to visual perception[J]. IEEE Transactions on Systems， Man， and Cybernetics， 1978，8（6）：460-473.

[7]CHEN Yixin， WANG J Z， KROVETZ R. Clue：Cluster-based retrieval of images by unsupervised learning[J]. IEEE Transactions on Image Processing： A Publication of the IEEE Signal Processing Society， 2005，14（8）：1187-1201.

[8]FLECK M， FORSYTH D，BREGLER C. Finding naked people[C]// 1996 European Conference on Computer Vision. Berlin， Germany：Springer-Verlag， 1996，2：592-602.

[9]WU S， MANBER U. A fast algorithm for multi-pattern searching[R].Tucson：University of Arizona， 1994.

[10]SAGE D， NEUMANN F R， HEDIGER F，et al. Automatic tracking of individual particles：Application to the study of chromosome dynamics[J].IEEE Transactions on Image Processing， 2005，14（9）：1372-1383.

[11]http：//www.ekany.corn/wd998/cg/tutorialapter8/lesson8-6.html.

[12]李靜.基于概念匹配度模型的文獻(xiàn)檢索系統(tǒng)[D].成都：西南交通大學(xué)，2009.

[13]段立娟，崔國(guó)勤，高文，等.多層次特定類(lèi)型圖像過(guò)濾方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14（5）： 404-409.

[14]范曉，申銥京.基于IE瀏覽器的色情圖片過(guò)濾器「J].吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2004，22（6）： 631-637.

[15]馮軍紅，劉桂林，高立新，等.基于小樣本訓(xùn)練集的膚色模型建立方法「J].計(jì)算機(jī)工程與應(yīng)用，2003（28）：67-71.

[16]趙曉暉.基于內(nèi)容的敏感圖片過(guò)濾技術(shù)的研究及其在IE瀏覽器中的實(shí)現(xiàn)[D].長(zhǎng)春：吉林大學(xué)，2005.