基于二進(jìn)制串的Trie索引樹分詞詞典機(jī)制的研究

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

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

0 引言

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

1 Trie索引樹

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

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

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

2 基于二進(jìn)制串的Trie索引樹

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

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

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

2.2 對二進(jìn)制串進(jìn)行等長切分

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

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

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

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

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

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

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

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

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

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

結(jié)點(diǎn)所在的哈希索引表中的元素結(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é)點(diǎn)。

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

圖3 基于Trie索引樹的分詞詞典機(jī)制

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

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

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

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

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

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

表1 m 取不同值時(shí)的空間分析和時(shí)間分析

4 結(jié)束語

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

[1]孫茂松，鄒嘉彥.漢語自動(dòng)分詞研究中的若干理論問題[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的漢語自動(dòng)分詞詞典機(jī)制[J].中文信息學(xué)報(bào)，2001，15(3):44-49.

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

[6]吳勝遠(yuǎn).一種漢語分詞方法[J].計(jì)算機(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方法的機(jī)器翻譯詞典的組織與構(gòu)造[J].大連理工大學(xué)學(xué)報(bào)，1996，36(3):352-355.

[9]孫茂松，左正平，黃昌寧.漢語自動(dòng)分詞詞典機(jī)制的實(shí)驗(yàn)研究[J].中文信息學(xué)報(bào)，2000，14(1):1-6.

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

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

[12]李江波，周強(qiáng)，陳袒舜.漢語詞典的快速查詢算法研究[J].中文信息學(xué)報(bào)，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ī)制[J].中國科學(xué)院研究生院學(xué)報(bào)，2009，26(5):703-711.