基于雙字哈希的PAT樹詞典機(jī)制的研究

趙 麗 郭宏文

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

中文信息處理技術(shù)是重要的計(jì)算機(jī)應(yīng)用技術(shù)，它已滲透到計(jì)算機(jī)應(yīng)用的各個(gè)領(lǐng)域。中文自動(dòng)分詞是中文信息處理的一項(xiàng)重要的基礎(chǔ)性工作，許多中文信息處理項(xiàng)目中都涉及到分詞問題。分詞的算法可分為有詞典及無詞典兩大類。>有詞典分詞算法是以分詞詞典作為分詞的基礎(chǔ)，其中正向最大匹配算法、逆向最大匹配算法及全切分算法是基本且有效的分詞算法[2]。

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

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

1 兩種相關(guān)詞典機(jī)制的介紹

1.1 基于雙字哈希的詞典機(jī)制

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

1.2 首字哈希的PAT樹詞典機(jī)制

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

2 基于雙字哈希的PAT樹詞典機(jī)制

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

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

2.1 首字哈希表

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

2.1.1 首字單元

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

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

C2=80H+位碼+20H

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

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

2.1.2 是否為詞

標(biāo)識(shí)此首字是否為單字詞。

2.1.3 次字入口項(xiàng)個(gè)數(shù)

標(biāo)識(shí)以此首字為詞的詞的個(gè)數(shù)。

2.1.4 次字入口項(xiàng)指針

指向首字對(duì)應(yīng)的次字哈希表。

2.2 次字哈希表

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

2.2.1 次字單元

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

2.2.2 是否為詞

標(biāo)識(shí)首字及次字組成的字串是否為二字詞。

2.2.3 沖突指針域

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

2.2.4 余字入口項(xiàng)指針

指向詞余字PAT樹根結(jié)點(diǎn)。

2.3 詞余字PAT樹

詞余字PAT樹的深度與多字詞的長(zhǎng)度有關(guān)。一個(gè)詞包含的字?jǐn)?shù)越多，則對(duì)應(yīng)的PAT樹深度越深。但在漢語中，多字詞所占比例很小，所以，詞余字的PAT樹并不會(huì)占用太多空間。

2.3.1 內(nèi)部結(jié)點(diǎn)

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

2.3.2 葉子結(jié)點(diǎn)

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

3 詞典機(jī)制性能分析

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

3.1 分詞效率的測(cè)試

為了全面分析及測(cè)試本文提出的基于雙字哈希的PAT樹分詞詞典機(jī)制的效果，筆者也選擇了不同學(xué)科的文字材料對(duì)分詞詞典進(jìn)行了測(cè)試，測(cè)試結(jié)果如下：

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

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

3.2 與其他詞典機(jī)制的比較

下面從時(shí)間及空間角度對(duì)基于雙字哈希的PAT樹的詞典機(jī)制、雙字哈希詞典機(jī)制及基于改進(jìn)的PAT樹機(jī)制進(jìn)行比較。

3.2.1 空間

基于雙字哈希的PAT樹詞典機(jī)制與雙字哈希詞典機(jī)制在前兩字的處理上采用相同的方法，但在詞余字的處理上前者采用PAT樹機(jī)制，后者采用類似整評(píng)詞二分的詞典下文機(jī)制，所以在空間上基于雙字哈希的詞典機(jī)制要優(yōu)于雙字哈希的PAT樹詞典機(jī)制?；诟倪M(jìn)的PAT樹機(jī)制，由于只對(duì)首字采用了哈希機(jī)制，而對(duì)于詞余字采用PAT樹機(jī)制，這樣的結(jié)構(gòu)在空間上較優(yōu)，前兩種機(jī)制在空間效率上都要差一些。

綜上可得，在空間效率上，三種詞典機(jī)制的排序?yàn)椋?/p>

雙字哈希機(jī)制<雙字哈希的PAT樹機(jī)制<改進(jìn)的PAT樹機(jī)制

3.2.2 時(shí)間

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

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

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

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

三種詞典機(jī)制在分詞時(shí)間效率上的比較結(jié)果可見表2。

表2 三種詞典機(jī)制時(shí)間效率上的比較 單位:ms

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

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

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

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

[4]馬哲,姚敏.一種改進(jìn)的基于PATRICIA樹的漢語自動(dòng)分詞詞典機(jī)制[J].華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版,2004,(32):28～32.