基于Trie樹的關鍵詞匹配算法在電子政務領域的應用

陳有偉 康磊

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

關鍵詞： 電子政務;Trie樹;模糊匹配;關鍵詞匹配

【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 國內外研究現狀

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

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

隨著國內外對于網絡信息關鍵字的分析技術逐步成熟，關于信息匹配的軟件產品得到了大量推廣，國內電子政務領域的處理流程得到了部分改善。但是在處理專用信息上，關鍵詞匹配技術還不夠完善。特別是，對于市民提交的民生訴求信息的識別技術也仍表現出一定不足，難以滿足智能化的要求，其準確率和時效性也有待提高，存在許多問題亟待解決。

2 基于關鍵字的布爾模型匹配算法

布爾模型因為實現方式簡單、匹配速度快、檢索方式易于用戶理解[12]等特點，在諸多領域得到了應用，成為了網站搜索引擎使用的首選方案。布爾模型是結合集合論和布爾代數思想的簡單數學模型，這種模型把文本信息中的關鍵詞從文本信息中提取出來，作為文本的特征值[13]。匹配過程也很簡單，把匹配詞用“與”、“或”、“非”進行連接就可以組成相應的正則表達式，而后利用正則表達式與模型關鍵詞進行對比得出匹配到的內容是否存在于該文檔中。

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

布爾模型的優勢表現在其匹配速度快、實現方式簡單等方面，但是這種模型的不足也十分明顯。對此可做闡釋分析如下。

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

（2）無法匹配重點結果。由于布爾模型匹配到的結果是一個大致的范圍，對于數據量小的情況比較適用，但是對于在電子政務領域逐步增長的海量數據信息，布爾檢索在處理能力上的不足就顯得尤為突出。

（3）容易造成匹配結果的冗余。

（4）因為布爾匹配的實現方式過于簡單、往往不能完全反映出想要的結果。

正是由于民生訴求包含的社會信息十分復雜、龐大，為了能快速地處理這些信息，引入了一種高效的數據結構—Trie樹。

3 基于Trie樹的匹配算法

3.1 Trie樹

Trie樹也叫作字典樹，是對一組詞進行結構化處理后的組織 [16]。

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

字典樹通過從根節點到子節點的路徑來表達一個詞，圖1中e，f節點為一個詞的最后一個節點，也就是說圖1字典樹代表的單詞有ade、ad、bd、cbf、cb。字典樹的根節點不表示任何字符。字典樹不僅節省了存儲空間，同時為模糊匹配技術的發展提供了堅實的基礎。

3.2 構造基于中文的Trie樹

英文Trie 樹的結點是由26個英文字母組成的，所以英文Trie樹的一個節點最多擁有26個子節點。但是中文卻不一樣，生活中常用的漢字就高達7 000多個，如果按照英文Trie樹的構建法則來構建中文Trie樹，將會極大地降低匹配的效率。因此如何構造基于中文的Trie樹結構就有著至關重要的研究意義。

比如，在向教育局投訴的信息中，根據教育局的相關關鍵詞構建屬于教育局的Trie樹結構，以關鍵詞“教育局”為例：

首先，基于拆詞的思想，利用正則表達式將關鍵詞“教育局”拆分為教、育、局三個字。

接著，檢查根節點是否已經有字符“教”節點，如果已經有這個節點，依次重復檢驗并添加“育”、“局”兩個節點。如果沒有，則將“教”添加在根加點下。

最后，當插入了每個關鍵詞時，在其末尾增加一個標志符，使用這個字符作為此關鍵詞的結束標志（如圖2中的灰色三角），利用這個字符來標記查找到了這個關鍵詞。

循環插入所有關鍵詞。構造出的中文Trie樹如圖2所示。

3.3 利用中文Trie樹解決中文匹配

以一則民生投訴為例：“我是X中初四學生家長，聽孩子說上體育課跑操時老師大聲罵學生，有時還用腳踢學生，學生真害怕，3、4班的。請求幫助。”利用圖2已經構造好的中文Trie樹來開始匹配。

首先，將投訴內容利用正則表達式拆成單個字符“我”、“是”、…;從根節點處查找第一個字符“我”，并沒有查找到以“我”為首字符的關鍵詞，然后繼續移動字符指針，直到查找到符合條件的字符節點“學”;接著在“學”這個字符節點下查找字符節點值為“生”的節點，成功找到時計算子樹的深度為2，關鍵詞的長度是2，此時字符指針繼續移動，如果發現結束標志，就意味著匹配成功，將匹配到的關鍵詞返回，如果未碰到結束標志則繼續向后移動指針結點尋找下一個字符。

循環遍歷完畢，返回所有匹配到的關鍵詞。

3.4 Trie樹的數據結構設計

Trie樹的數據結構設計采用PHP語言，結合了PHP數組的hash特性，代碼如下：

Private $root = array（

‘depth=>$depth，

// 深度，用來判斷命中的字數

‘next=> array（

$val =>$node， // 使用PHP數組的hash結構，增加子節點的查找速率

…

）

）

4 實驗結果及分析

實驗環境為MacBook Pro（Retina，15-inch，Mid 2015），處理器為2.2 GHz Intel Core i7，內存16 GB 1600 MHz DDR3，使用PHP語言實現。實驗中的給定文本內容來源于某市民心網1 000個市民提交的訴求問題。

將1 000個市民提交的問題內容分成4個小組，每組250篇，并計算其查全率、查準率以及所耗時間。基于Trie樹結構的關鍵詞匹配結果，見表1。

基于正則表達式的關鍵詞匹配結果，見表2。

要應用在電子政務領域，至關重要的就是效率與準確率。通過以上實驗結果可以發現，與在電子政務系統中單純使用正則表達式相比，使用Trie樹結構處理250條數據基本耗時在1 s左右，并且根據關鍵詞匹配到的結果，將其分發到命中的部門，準確率基本都高達93%以上，明顯改善了處理民生訴求問題的效率，符合電子政務領域的基本要求。

5 結束語

本文通過在電子政務系統中引入Trie樹這種效率極高的數據結構結合正則表達式，極大地提高了匹配效率，使得職能部門在處理民眾訴求時，能夠及時將民眾反映的相關問題分派到相應的部門去辦理，優化部門辦事效率，提升了民眾對職能部門的工作滿意度。

參考文獻

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

[2]靳瑞敏. 網頁關鍵字過濾研究及改進[D]. 呼和浩特：內蒙古大學，2012.

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

[4]俞文洋，張連堂，段淑敏. KMP模式匹配算法的研究[J].鄭州輕工業學院學報（自然科學版），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]李靜.基于概念匹配度模型的文獻檢索系統[D].成都：西南交通大學，2009.

[13]段立娟，崔國勤，高文，等.多層次特定類型圖像過濾方法[J].計算機輔助設計與圖形學學報，2002，14（5）： 404-409.

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

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

[16]趙曉暉.基于內容的敏感圖片過濾技術的研究及其在IE瀏覽器中的實現[D].長春：吉林大學，2005.