韓 瑩，豐繼林，袁 靜，王茂發(fā)，張艷霞，陳福明，陳新房，潘志安

(1.防災(zāi)科技學(xué)院災(zāi)害信息工程系，北京 101601;2.清華大學(xué)計算機科學(xué)與技術(shù)系，北京 100084)

0 引言

中文信息處理存在分詞問題，分詞的基礎(chǔ)需要一個足夠大的詞庫，要知道一個漢字串是不是一個詞，就需要查詢詞庫，如果能在詞庫中查詢到，就認(rèn)為是一個詞。分詞詞典是漢語自動分詞系統(tǒng)的一個基本組成部分[1]，在漢語信息處理的過程中需要頻繁地查詢詞典來確認(rèn)某個漢字串是不是詞，因此漢語詞典機構(gòu)組織級查詢速率對整個系統(tǒng)的效率有很大影響。中文自動分詞系統(tǒng)的研究已經(jīng)有很多年了，目前已經(jīng)形成了一些成熟的漢語詞典機制及查詢算法。常用的有線性索引機制、倒排索引機制、哈希索引機制、各種索引樹及混合模式。線性索引機制和倒排索引機制屬于靜態(tài)索引表，不利于添加和刪除等更新操作，只能用順序法或折半法查詢數(shù)據(jù)。哈希索引機制是在表項的存儲位置與它的關(guān)鍵碼之間建立一個確定的對應(yīng)函數(shù)關(guān)系Hash()，使得每個關(guān)鍵碼與結(jié)構(gòu)中的一個唯一的存儲位置對應(yīng)[2]。對于Hash結(jié)構(gòu)來說，關(guān)鍵在于如何設(shè)計一個好的哈希函數(shù)，盡量減少沖突。Douglas C.Schmidt提出一種很好的散列函數(shù)算法[3]，該算法保證得到每一個Hash值都是唯一的。但是這種算法目前來說還有缺陷，實驗結(jié)果顯示，隨著數(shù)據(jù)增大，空間浪費會非常多。搜索索引機制包括B樹和Trie樹結(jié)構(gòu)等，結(jié)構(gòu)相對比較復(fù)雜，但是如果結(jié)構(gòu)設(shè)計得很好，查詢的效率也非常高?；谶@兩種方法，還有一些變種的算法[4-7]。另外文獻[8]中采用的是二級散列索引機制來組織和構(gòu)造機器翻譯詞典。文獻[9]指出了幾種常用的詞典構(gòu)造機制:整詞二分詞典查詢機制、Trie索引樹詞典查詢機制、逐字二分詞典查詢機制。文獻[10]中提出了基于雙字哈希機制的詞典查詢方法。文獻[11]采用了四字哈希機制。文獻[4]中提出了一種基于PATRICIAtree的漢語詞典查詢機制。文獻[12]提出了兩種漢語詞典快速查詢機制:雙數(shù)組Trie索引機制、雙編碼機制?；赥rie索引樹原理，本文先簡單介紹Trie索引樹，然后提出一種改進的基于Trie索引樹的詞典查詢機制。

1 Trie索引樹

Trie樹是搜索樹的一種，可以組織成有效的數(shù)據(jù)索引機制。它是一個確定的有限狀態(tài)自動機，搜索樹中的每個結(jié)點代表一個狀態(tài)，根據(jù)輸入不同的變量，狀態(tài)作出相應(yīng)的轉(zhuǎn)移。面向英文的Trie索引樹大多是以26個字母作為關(guān)鍵字，樹中的每個結(jié)點包含相同的指針，是一棵26叉Trie樹，如圖1所示。

圖1 Trie索引樹結(jié)構(gòu)

Trie樹的一種存儲方式是使用鏈表結(jié)點，這種方式在空間復(fù)雜度上降低為O(n)，但是缺點在于數(shù)據(jù)結(jié)構(gòu)復(fù)雜，查詢效率較低[13]。傳統(tǒng)上的有限狀態(tài)自動機多采用轉(zhuǎn)換表來實現(xiàn)，其列表示自動機的不同狀態(tài)，行表示轉(zhuǎn)換變量，但是對于詞典查詢來說，轉(zhuǎn)換表的不足之處在于稀疏的數(shù)據(jù)導(dǎo)致了很多的空間浪費，其空間復(fù)雜度為O(n2)。一方面為了保證查詢的效率，另一方面又要使占用的空間較少，前人提出了4個數(shù)組來表示DFA的方法，之后又對其進行了改進，提出了用3個線性數(shù)組來表示Trie樹的方法。文獻[14]在上述基礎(chǔ)上做出了又一次改進，用兩個線性數(shù)組來表示，即雙數(shù)組Trie[15]。構(gòu)造完雙數(shù)組之后，查詢就變得比較方便。查詢的漢字串有幾個字，就將該漢字串分別轉(zhuǎn)換為相應(yīng)的編碼，在編碼基礎(chǔ)上做加法運算，即可以查詢詞庫判斷該漢字串是不是一個詞語。在漢語詞匯中，對常用詞典(人民日報)的統(tǒng)計發(fā)現(xiàn)，在108783個詞匯中，51%為2字詞，31%為3字詞，13%為4字詞，3%左右為單字詞，多出4字以上的詞匯只占2%左右[16]，因此雙數(shù)組查詢算法的效率是極高的。

2 基于二進制串的Trie索引樹

基于Trie索引樹結(jié)構(gòu)的思想，本文提出一種改進的詞典索引機制?；舅枷肴缦?

2.1 對漢字串處理轉(zhuǎn)換成二進制串的處理

信息在計算機中都是以二進制的方式存儲的，每個漢字在計算機中的編碼就對應(yīng)于一組二進制串，本文把對漢字串的處理轉(zhuǎn)化成對二進制串的處理。

2.2 對二進制串進行等長切分

可以對任意一個二進制串分成長度均為m(m＞=2bit＆＆m＜=16bit)的幾段，在最后一段中，如果長度不夠m，自動補0使該段長度為m。例如一個漢字串含有2個漢字，共有32bit，每5bit分成一段，則被分成7段，最后一度長度為2bit，自動在后面加3個0，使其達(dá)到5個bit的長度。

對于m的值，如果取值小，使用的空間少，但是增加索引的級別，即所創(chuàng)建的Trie樹層次多，增加查詢開銷;如果取值太大，所建的Trie樹層次少，查詢速度快，但是耗費的空間非常大。應(yīng)該根據(jù)詞庫中詞的特點及實際的問題需求，為m選擇一個合適值。

以m=8為例，即對待處理的漢字串的二進制串選取每8bit為一段，每段視為無符號數(shù)，求出其值，最大值為255，那么表示的數(shù)據(jù)范圍是0～255。

例如:詞語“作風(fēng)”的GBK內(nèi)碼是D7F7B7E7，對應(yīng)的二進制串11010111111101111011011111100111，把該二進制每8bit分成一段，得到的是11010111、11110111、10110111、11100111，把每一段看成無符號數(shù)，計算其十進制值為 215，247，183，231。

2.3 索引樹結(jié)點結(jié)構(gòu)

索引樹中的每個結(jié)點都是以如圖2所示結(jié)構(gòu)為基本元素構(gòu)成的哈希索引表。

圖2 Trie索引樹結(jié)點結(jié)構(gòu)

標(biāo)志位flag:標(biāo)識詞語是否結(jié)束，如果結(jié)束為1，否則為0;初值均為0。

指針:指向其孩子結(jié)點，初值均為空。

上述對二進制串分段后計算出來的無符號值作為在結(jié)點的哈希索引表中的地址，因為8bit二進制串最大能表示出來的無符號數(shù)值為256，因此結(jié)點的哈希索引表長為256，所得到的索引樹是一棵256叉樹。

結(jié)點所在的哈希索引表中的元素結(jié)構(gòu)定義如下:

typedef struct tag_word_node{//哈希索引表中元素的結(jié)構(gòu)類型

struct tag_word_node* next_tb;

int flag;

}word_node_t;

#define MAX_TABLE_SIZE 256

word_node_t g_table[MAX_TABLE_SIZE];//全局變量，作為根結(jié)點。

以m=8bit為例，部分詞語構(gòu)成的Trie索引樹結(jié)構(gòu)圖如圖3所示。

圖3 基于Trie索引樹的分詞詞典機制

3 實驗結(jié)果及分析

實驗環(huán)境為 Intel-I3、4G內(nèi)存、64位操作系統(tǒng)Window 7。

在程序測試時，測試詞庫使用的是含有339095不限詞長的基本通用詞表，空間分析與時間分析如下。

分別對m取不同的值做了相應(yīng)的分析，當(dāng)m＞=9的時候，測試程序提示內(nèi)存不足，所以實驗中只分析了m在2～8之間的值。以m=8為例來說明，當(dāng)m=8的時候，所建立的256叉Trie樹共有532113個結(jié)點，每個結(jié)點是一個含有256個元素的哈希索引表，哈希索引表表中的每個元素是一個含有一個標(biāo)志符和一個指向其孩子結(jié)點的指針構(gòu)成，計算出來所含的字節(jié)數(shù)是 1，089，767，424。

在本系統(tǒng)中，查詢詞語與詞條的多少沒有關(guān)系，只與詞條本身的長度有關(guān)系。以m=8為例，如果要查找一個漢字個數(shù)為3的詞條，需要計算6次索引值就能確認(rèn)該詞在詞庫中是不是存在。

選取幾個具有代表性的m的值，表1顯示了當(dāng)m分別取不同值時的結(jié)點數(shù)和所耗的空間大小，查詢時間為把含有339095個詞條的測試詞庫中所有的詞條查詢一遍所耗費的平均總時間。

表1 m 取不同值時的空間分析和時間分析

4 結(jié)束語

本文在分析了Trie樹結(jié)構(gòu)之后，根據(jù)信息在計算機以二進制串存儲的特點，把對文本信息處理改為對二進制串的處理，建立Trie樹的分詞詞典機制。雖然這種Trie存儲結(jié)構(gòu)沒有雙數(shù)組Trie樹的查詢速度快，但是這種結(jié)構(gòu)更靈活，可以適用于不同的語言。在實際處理過程中，二進制的串與串之間有很多相同的前綴，實際耗費的空間并不多;并且該詞典機制不受詞數(shù)量的限制，詞語的數(shù)量越多，空間利用率越高。這種分詞詞典機制不受語言限制，也不受詞庫大小的限制，是一個功能強大的大容量詞典機制。

[1]孫茂松，鄒嘉彥.漢語自動分詞研究中的若干理論問題[J].語言文字應(yīng)用，1995(4):40-46.

[2]殷人昆，陶永雷，謝若陽，等.數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC++描述[M].北京:清華大學(xué)出版社，1999.

[3]Douglas Schmidt.GPERF:A Perfect Hash Function Generator[EB/OL].http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1056，2012-08-03.

[4]楊文峰，陳光英，李星.基于PATRICIA Tree的漢語自動分詞詞典機制[J].中文信息學(xué)報，2001，15(3):44-49.

[5]溫滔，朱巧明，呂強.一種快速漢語分詞算法[J].計算機工程，2004，30(19):119-120，128.

[6]吳勝遠(yuǎn).一種漢語分詞方法[J].計算機研究與發(fā)展，1996，33(4):306-311.

[7]Kazuhiro M，El-Sayed A，Masao F，et al.Fast and compact updating algorithms of a double-array structure[J].Information Sciences，2004，159(1-2):53-67.

[8]王秀坤，李政，簡幼良，等.基于Hash方法的機器翻譯詞典的組織與構(gòu)造[J].大連理工大學(xué)學(xué)報，1996，36(3):352-355.

[9]孫茂松，左正平，黃昌寧.漢語自動分詞詞典機制的實驗研究[J].中文信息學(xué)報，2000，14(1):1-6.

[10]李慶虎，陳玉健，孫家廣.一種中文分詞詞典新機制——雙字哈希機制[J].中文信息學(xué)報，2003，17(4):13-l8.

[11]張培穎，李村合.一種中文分詞詞典新機制——四字哈希機制[J].微型電腦應(yīng)用，2006，22(10):35-36，55.

[12]李江波，周強，陳袒舜.漢語詞典的快速查詢算法研究[J].中文信息學(xué)報，2006，20(5):31-39.

[13]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，1992.

[14]Aoe J.An efficient digital search algorithm by using a double-array structure[J].IEEE Transactions on Software Engineering.1989，15(9):1066-1077.

[15]Theppitak Karoonboonyanan.An Implementation of Double-Array Trie[EB/OL].http://linux.thai.net/～ thep/datrie/datrie.html，2010-09-25.

[16]吳晶晶，荊繼武，聶曉峰，等.一種快速中文分詞詞典機制[J].中國科學(xué)院研究生院學(xué)報，2009，26(5):703-711.