趙 麗 郭宏文

(黑龍江生態(tài)工程職業(yè)學院 計算機技術系，哈爾濱 150025)

中文信息處理技術是重要的計算機應用技術，它已滲透到計算機應用的各個領域。中文自動分詞是中文信息處理的一項重要的基礎性工作，許多中文信息處理項目中都涉及到分詞問題。分詞的算法可分為有詞典及無詞典兩大類。>有詞典分詞算法是以分詞詞典作為分詞的基礎，其中正向最大匹配算法、逆向最大匹配算法及全切分算法是基本且有效的分詞算法[2]。

目前，分詞詞典機制種類較多，但典型的主要有整詞二分的詞典機制、基于TRIE樹的詞典機制及逐字二分的詞典機制。隨著研究的深入，還有其他學者提出的雙字哈希詞典機制、基于改進的PAT樹詞典機制及四字哈希詞典機制。這些詞典機制圍繞著分詞的準確率及分詞速度作了逐步改進，但隨著網(wǎng)絡的發(fā)展及信息量成級數(shù)增長的趨勢，分詞的詞典機制還有待加強和提高，以滿足分詞工作的需要。

本文首先介紹了基于雙字哈希的詞典機制及基于改進的PAT樹詞典機制，結合兩種方法的優(yōu)點，提出了基于雙字哈希的PAT樹詞典機制，最后通過實驗對新的詞典機制和已有的詞典機制在分詞準確率及分詞的時間、空間效率上做了比較。

1 兩種相關詞典機制的介紹

1.1 基于雙字哈希的詞典機制

據(jù)有些學者統(tǒng)計，在漢語中單字詞和雙字詞最多，可以占到94%的比例，雙字詞出現(xiàn)的頻率也最高，而三字詞、四字詞以及多字詞相對較少，且出現(xiàn)的頻率也低。針對這種情況，有些學者提出了基于首字哈希機制的改進算法，其中學者李玉虎提出的雙字哈希索引機制[3]在查詢速度上有了很大的提高，雙字哈希索引機制僅對詞條的前兩個字建立哈希索引，通過雙字哈希索引，構建了深度為2的TRIE子樹，詞的剩余字串則按序組成類似整詞二分的詞典正文，具體結構可見圖1。

1.2 首字哈希的PAT樹詞典機制

學者馬哲、姚敏對基于PAT樹的分詞詞典機制提出了改進方案，即在PAT樹結構中加入了首字哈希表，把一棵大的PAT樹分解成多個基于首字的小PAT樹，以減小樹的深度，使空間效率得到提高[4]?；谑鬃止５腜AT樹詞典機制由首字哈希表及PAT樹兩部分組成，具體結構可見圖2。同單純的PAT樹機制相比，基于哈希散列的PAT樹詞典機制在空間上多了一個首字哈希表。加入首字哈希表后，PAT樹的深度減小了，因而從根結點到葉子結點的平均路徑也變小了。

2 基于雙字哈希的PAT樹詞典機制

在雙字哈希的詞典機制中，僅對詞條的前兩個字建立哈希索引，而對詞余字采取類似整詞二分的機制，在多字詞的查詢速度上有待提高?；谑鬃止５腜AT樹詞典機制，僅對首字采用哈希機制，對詞余字采用PAT樹機制，這樣的結構在查詢速度上獲得了較大進步，但在詞典的存儲空間及維護上，需要改善。

針對基于雙字哈希的詞典機制及基于首字哈希的PAT樹詞典機制的優(yōu)點和不足，本文提出了基于雙字哈希的PAT樹詞典機制?；陔p字哈希的PAT樹分詞詞典由三部分組成：首字哈希表、次字哈希表和詞余字PAT樹，具體結構可見圖3。

2.1 首字哈希表

首字哈希表包括首字單元、是否為詞、次字入口項個數(shù)及次字入口項指針。首字哈希表的長度由常用字的個數(shù)決定。本文根據(jù)GB2312-80中所含的6 763個常用漢字，設置首字哈希表的長度為6 763個單元，哈希函數(shù)采用去留余數(shù)法，實現(xiàn)關鍵字與地址的一一對應。

2.1.1 首字單元

即詞的第一個漢字及其相關信息。GB2312-80中規(guī)定漢字在計算機中存儲的94個區(qū)中的第16-87個區(qū)內(nèi)存放漢字且每個區(qū)中的0號位置不存放漢字，所以首字在漢字編碼表中的偏移量可定義為如下公式：

C1=80H+區(qū)碼+20H

C2=80H+位碼+20H

M=(C1-16)×94+(C2-1)

其中M為首字在漢字編碼表中的位置，C1為高位機內(nèi)碼，C2為低位機內(nèi)碼。有了這樣的定義，便可以通過一步映射直接定位首字。本文采用去留余數(shù)法來構建哈希函數(shù)，即H(K)=M mod L，其中M為首字字符的機內(nèi)碼，L為哈希表表長。

2.1.2 是否為詞

標識此首字是否為單字詞。

2.1.3 次字入口項個數(shù)

標識以此首字為詞的詞的個數(shù)。

2.1.4 次字入口項指針

指向首字對應的次字哈希表。

2.2 次字哈希表

由于漢語詞語分布不均勻，而且計算機內(nèi)存空間有限，對于詞次字不可能采用統(tǒng)一的定長表長，具體每個詞次字哈希表的長度由首字對應的詞次字個數(shù)和設定的哈希表的裝填因子a有關，本論文中的裝填因子設置為0.75，當次字哈希表中記錄數(shù)所占比例超過表長的75%時，次字哈希表的長度會自動增至原來的2倍，從而降低產(chǎn)生沖突的可能。裝填因子a可由下面公式得出

2.2.1 次字單元

即詞的第二個漢字及相關信息。由兩字及多字詞的詞次字組成，由于以首字為詞的詞個數(shù)不確定，所以，次字哈希表采用不定長存儲。

2.2.2 是否為詞

標識首字及次字組成的字串是否為二字詞。

2.2.3 沖突指針域

當次字哈希散列中出現(xiàn)沖突時，采用鏈地址法來解決沖突，所以，在次字哈希表中給出沖突指針域，指向由哈希函數(shù)計算得到相同位置的詞次字組成的鏈表。

2.2.4 余字入口項指針

指向詞余字PAT樹根結點。

2.3 詞余字PAT樹

詞余字PAT樹的深度與多字詞的長度有關。一個詞包含的字數(shù)越多，則對應的PAT樹深度越深。但在漢語中，多字詞所占比例很小，所以，詞余字的PAT樹并不會占用太多空間。

2.3.1 內(nèi)部結點

用來存儲詞條的二進制比較位，由于一個漢字字符的機內(nèi)碼為16位，所以，在16n+1處出現(xiàn)分支；當比較位為0時，轉向左子樹；當比較位為1時，轉向右子樹。

2.3.2 葉子結點

用來存儲詞條信息，即漢字的機內(nèi)碼。

3 詞典機制性能分析

本文使用搜狗網(wǎng)提供的互聯(lián)網(wǎng)語料庫中的MINI版作為訓練集和測試集，采用基于雙字哈希的PAT樹機制，通過統(tǒng)計語言處理模式的方法，生成22詞條的分詞詞典，最長詞條為11字詞。測試環(huán)境選擇3GWS分詞系統(tǒng)，此系統(tǒng)可加載用戶自定義的詞典。

3.1 分詞效率的測試

為了全面分析及測試本文提出的基于雙字哈希的PAT樹分詞詞典機制的效果，筆者也選擇了不同學科的文字材料對分詞詞典進行了測試，測試結果如下：

表1 基于雙字哈希PAT樹分詞詞典機制的分詞效果

由上面的統(tǒng)計結果可以看出，本文提出的分詞詞典機制，對文學、經(jīng)濟、歷史、計算機、社會等學科門類進行統(tǒng)計分詞的準確率在98%以上，這樣的準確率主要是因為采用了封閉測試的方法，所以準確率比較高。剩下的小于2%的錯誤主要是歧義字段，其中大部分為組合型歧義，這也是統(tǒng)計方法的不足之處。同時從算法處理結果可以看出，首字哈希—詞尾PAT樹機制減少了平均查詢路徑，從而使分詞的效率得到了提高。

3.2 與其他詞典機制的比較

下面從時間及空間角度對基于雙字哈希的PAT樹的詞典機制、雙字哈希詞典機制及基于改進的PAT樹機制進行比較。

3.2.1 空間

基于雙字哈希的PAT樹詞典機制與雙字哈希詞典機制在前兩字的處理上采用相同的方法，但在詞余字的處理上前者采用PAT樹機制，后者采用類似整評詞二分的詞典下文機制，所以在空間上基于雙字哈希的詞典機制要優(yōu)于雙字哈希的PAT樹詞典機制。基于改進的PAT樹機制，由于只對首字采用了哈希機制，而對于詞余字采用PAT樹機制，這樣的結構在空間上較優(yōu)，前兩種機制在空間效率上都要差一些。

綜上可得，在空間效率上，三種詞典機制的排序為：

雙字哈希機制<雙字哈希的PAT樹機制<改進的PAT樹機制

3.2.2 時間

下面通過具體的實驗數(shù)據(jù)對基于雙字哈希的PAT樹的詞典機制、雙字哈希詞典機制及基于改進的PAT樹機制進行比較。實驗環(huán)境仍為3GWS分詞系統(tǒng)。為確保實驗數(shù)據(jù)的準確性，測試使用的詞典中詞條數(shù)為22萬，最長詞條為11字詞，測試方法如下：

(1)采用確定詞條的查詢方法，對詞典中所有詞條均查詢一次。

(2)任取一段文本(2萬字左右)，采用逆向最大匹配法切分該文本。

(3)任取一段文本(3萬字左右)，采用逆向最大匹配法切分該文本。

三種詞典機制在分詞時間效率上的比較結果可見表2。

表2 三種詞典機制時間效率上的比較 單位:ms

由表2可以看出，對于三種不同的詞典機制，其分詞的時間效率略有差異，通過實驗數(shù)據(jù)可以得出，雙字哈希的PAT樹機制在分詞的時間效率上略高于其他兩種詞典機制。

[1]吳棟,滕育平.中文信息檢索引擎中的分詞與檢索技術[J].計算機應用,2004,24(7):28～31.

[2]張啟宇，朱玲，張雅萍.中文分詞算法研究綜述[J].情報探索，2008，(11):53～56.

[3]李玉虎，陳玉健，孫家廣.一種中文分詞詞典新機制——雙字哈希機制[J].中文信息學報，2003，4(17)：13～18.

[4]馬哲,姚敏.一種改進的基于PATRICIA樹的漢語自動分詞詞典機制[J].華南理工大學學報：自然科學版,2004,(32):28～32.