漢語詞典快速查詢算法研究分析解析

1、漢語詞典快速查詢算法研究李江波周強(qiáng)陳祖舜（清華大學(xué)智能技術(shù)與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室北京100084）E-mail:jiangbo摘要：漢語詞典查詢是中文信息處理系統(tǒng)的重要基礎(chǔ)部分，對系統(tǒng)效率有重要的影響。本文對漢語詞典查詢算法研究作了簡要回顧，設(shè)計實(shí)現(xiàn)了基于雙數(shù)組TRIE機(jī)制的漢語詞典查詢算法，并提出了基于雙編碼機(jī)制的詞典查詢算法。最后對兩種詞典查詢機(jī)制進(jìn)行了實(shí)驗(yàn)分析。關(guān)鍵詞：漢語詞典查詢；雙數(shù)組TRIE;雙編碼；中文信息處理。一、引言在漢語信息處理系統(tǒng)中，漢語詞典查詢是一個重要的基礎(chǔ)環(huán)節(jié)，在整個處理過程中都需要頻繁地訪問詞典以獲得漢語詞語知識，因而漢語詞典的快速查詢是整個處理系統(tǒng)效率的關(guān)鍵所在。

2、針對詞典查詢方法，前人作了大量工作，并形成了許多漢語詞典組織結(jié)構(gòu)和相應(yīng)的查詢算法。早期的詞典組織構(gòu)造主要是基于傳統(tǒng)Hash方法，文獻(xiàn)1中采用的方法就是一個典型應(yīng)用，這種方法的關(guān)鍵技術(shù)是Hash函數(shù)的設(shè)計，采用合理的方式來調(diào)節(jié)數(shù)據(jù)塊的分配，控制分布的均勻性，減少沖突，提高空間利用率，由于涉及到磁盤讀取，這種方法在速度上存在較大局限。文獻(xiàn)2指出了三種典型的詞典查詢方法：整詞二分法、TRIE索引樹法、逐字二分法。以下分別對這三種方法作簡要介紹：（1）基于整詞二分的詞典機(jī)制：整詞二分方法的詞典結(jié)構(gòu)分為詞典正文、詞索引表、首字散列表等三級。通過首字散列表的哈希定位和詞索引表，很容易確定指定詞在詞典正文中

3、的可能位置范圍，進(jìn)而在詞典正文中通過整詞二分進(jìn)行定位。這種算法的數(shù)據(jù)結(jié)構(gòu)簡單、占用空間小，構(gòu)建及維護(hù)也簡單易行，但由于采用全詞匹配的查詢過程，效率較為低下。（2）基于TRIE索引樹的詞典機(jī)制：TRIE索引樹是一種以樹的多重鏈表形式表示的鍵樹，基于TRIE索引樹的詞典機(jī)制由首字散列表和TRIE索引樹結(jié)點(diǎn)兩部分組成。TRIE索引樹的優(yōu)點(diǎn)是分詞應(yīng)用中，在對被切分語句的一次掃描過程中，不需預(yù)知待查詢詞的長度，沿著樹鏈逐字匹配即可；缺點(diǎn)是它的構(gòu)造和維護(hù)比較復(fù)雜，而且都是單詞樹枝，浪費(fèi)了一定的空間。（3）基于逐字二分法的查詢機(jī)制：基于逐字二分法的查詢機(jī)制是對前兩種詞典機(jī)制的改進(jìn)方案，一方面，從組織結(jié)構(gòu)上，

4、逐字二分與整詞二分的詞典結(jié)構(gòu)完全一樣；另一方面，逐字二分吸收了TRIE索引樹的查詢優(yōu)勢，即采用的是“逐字匹配”，而不是整詞二分的“全詞匹配”，這就一定程度地提高了匹配的效率。但由于采用的仍是整詞二分的詞典結(jié)構(gòu)，使效率的提高受到很大的局限。文獻(xiàn)3中提出了基于雙字哈希機(jī)制的詞典查詢方法，該方法主要結(jié)合了詞典中的多字詞條（3字詞以上）數(shù)量少，使用頻度低的特點(diǎn)，對基于TRIE索引樹的詞典機(jī)制做出了改進(jìn)，把TRIE索引樹的深度限制為2。其三層結(jié)構(gòu)分別是首字哈希索引，次字哈希索引，剩余字串組。這種查詢機(jī)制相當(dāng)于使2字詞以下的短詞用TRIE索引樹機(jī)制實(shí)現(xiàn)，3字詞以上的長詞的剩余部分用線性表組織，從而避免了深

5、度搜索，一定程度上提高了查詢性能。此外，文獻(xiàn)4中提出了一種基于PATRICIAtree的漢語詞典查詢機(jī)制，這種方法首先使用詞條的內(nèi)碼來作為一個關(guān)鍵詞位串，然后通過位串比較構(gòu)造出PATRICIAtree樹，樹的每個內(nèi)部節(jié)點(diǎn)包括三個數(shù)據(jù)項(xiàng)：比較位、左指針、右指針，樹的葉子節(jié)點(diǎn)代表一個詞條。查詢時根據(jù)內(nèi)部節(jié)點(diǎn)選擇后繼路徑，直到葉子節(jié)點(diǎn)，該方法的優(yōu)點(diǎn)是引入了位比較，但是因?yàn)闃涞臉?gòu)造過程是基于內(nèi)碼而非字的，所以不可避免地導(dǎo)致樹的深度大大增加，從而造成了效率降低和空間浪費(fèi)。本文設(shè)計實(shí)現(xiàn)了基于雙數(shù)組Trie(Double-ArrayTrie)原理的漢語查詢詞典；提出并實(shí)現(xiàn)了一種基于雙編碼機(jī)制的詞典查詢機(jī)制；

6、最后對改進(jìn)二分法，雙數(shù)組Trie(Double-ArrayTrie),雙編碼方法三種方法進(jìn)行了性能上的比較。下面的第二章介紹雙數(shù)組Trie(Double-ArrayTrie)的數(shù)據(jù)結(jié)構(gòu)和具體實(shí)現(xiàn)，第三章介紹雙編碼方法的編碼思想和具體查詢方式，第四章是對雙編碼思想進(jìn)行的性能分析，第五章是對三種方法進(jìn)行性能實(shí)驗(yàn)分析，第六章為全文的總結(jié)。二、雙數(shù)組Trie(Double-ArrayTrie)的數(shù)據(jù)結(jié)構(gòu)與具體實(shí)現(xiàn)Trie樹是搜索樹的一種，來自英文單詞Retrieval的簡寫，可以建立有效的數(shù)據(jù)檢索組織結(jié)構(gòu)。Trie樹本質(zhì)上是一個確定的有限狀態(tài)自動機(jī)(DFA),每個節(jié)點(diǎn)代表自動機(jī)的一個狀態(tài)，根據(jù)變量的不

7、同，進(jìn)行狀態(tài)轉(zhuǎn)移，當(dāng)?shù)竭_(dá)結(jié)束狀態(tài)或者無法轉(zhuǎn)移的時候，完成查詢。傳統(tǒng)上的DFA一般用轉(zhuǎn)換表方式來實(shí)現(xiàn)，表的列代表自動機(jī)的不同狀態(tài)，行代表轉(zhuǎn)換變量，但是對于詞典查詢來說，轉(zhuǎn)換表的問題是數(shù)據(jù)稀疏導(dǎo)致嚴(yán)重地的空間浪費(fèi)，其空間復(fù)雜度為O(n2)。Trie樹的另一種實(shí)現(xiàn)方式是使用鏈表節(jié)點(diǎn)，這種方式在空間復(fù)雜度上降低為O(n),但是問題在于數(shù)據(jù)結(jié)構(gòu)復(fù)雜，查詢效率較低5。為了讓Trie實(shí)用的實(shí)現(xiàn)算法在空占用間較少的同時還要保證查詢的效率，前人提出了一種用4個線性數(shù)組表示DFA的方法，并進(jìn)一步提出了用3個線性數(shù)組表示Trie樹的方式。在此基礎(chǔ)上，文獻(xiàn)6做出了進(jìn)一步改進(jìn)，用2個線性數(shù)組來進(jìn)行Trie樹的表示，即雙

8、數(shù)組Trie(Double-ArrayTrie)7。雙數(shù)組Trie(Double-ArrayTrie)由兩個整數(shù)數(shù)組構(gòu)成，一個是base口，另一個是check口。設(shè)數(shù)組下標(biāo)為i，如果basei,checki均為0,表示該位置為空。如果basei為負(fù)值，表示該狀態(tài)為詞語。Checki表示該狀態(tài)的前一狀態(tài)，t=basei+a,checkt=i。對于漢字詞典，采用相同的思想。先把雙數(shù)組的1-6768放置6768個常用漢字。對于每一個漢字，確定一個base值，使得對于所有以該漢字開頭的詞，在雙數(shù)組中都能放下。例如，現(xiàn)在要確定“阿”字的base值，假設(shè)以“阿”開頭的詞的第二個字序列碼依次為a1,a2,a

9、3an,我們必須找到一個值i,使得basei+a1,checki+a1,basei+a2,checki+a2basei+an,checki+an均為0。一旦找到了這個i,“阿”的base值就確定為i。對于第二個字，第三個字也是類似。雙數(shù)組構(gòu)造完成以后，查詢起來極為方便。待查詞有幾個字，就將漢字分別轉(zhuǎn)換為對應(yīng)的序列碼，然后作幾次加法，即可查到相應(yīng)的詞語，無須折半查找。由于漢語中常用詞平均長度不到3個字，因此雙數(shù)組查詢算法的效率是極高的。下面舉例說明雙數(shù)組Trie(Double-ArrayTrie)的構(gòu)造過程和查詢過程。假定詞表中只有“啊，阿根廷，阿膠，阿拉伯，阿拉伯人，埃及”這幾個詞，用Trie

10、樹可以表示為：我們首先對詞表中所有出現(xiàn)的10個漢字進(jìn)行編碼：啊-1,阿-2,唉-3,根-4,膠-5,拉-6,及-7,廷-8,伯-9,人-10。然后在此基礎(chǔ)上構(gòu)建雙數(shù)組Trie(Double-ArrayTrie),經(jīng)過四次遍歷，將所有的詞語放入雙數(shù)組中，然后還要遍歷一遍詞表，修改base值。因?yàn)槲覀冇秘?fù)的base值表示該位置為詞語。如果狀態(tài)i對應(yīng)某一個詞，而且Basei=0,那么令Basei=(-1)*i,如果Basei的值不是0,那么令Basei=(-1)*Basei。得到雙數(shù)組如下：下標(biāo)1234567891011121314Base-14400004-94-11-12-4-14Check00

11、00000222381013詞綴啊阿埃阿根阿膠阿拉埃及阿根廷阿拉伯阿拉伯人用上述方法生成的雙數(shù)組，將“啊”，“阿”，“?！?，啊根，“阿拉”，“阿膠”，“埃及”，“阿拉伯”，“阿拉伯人”，“阿根廷”均視為狀態(tài)。每個狀態(tài)均對應(yīng)于數(shù)組的一個下標(biāo)。例如設(shè)“阿根”的下標(biāo)為i=8,那么checki的內(nèi)容是“阿”的下標(biāo)，而basei是“阿根廷”的下標(biāo)的基值。廷的序列碼為x=8,那么阿根廷的下標(biāo)為basei+x=base8+8=12。查詢時相當(dāng)于從一個狀態(tài)找到另一個狀態(tài)。例如查詢“阿根廷”，先根據(jù)“阿”的序列碼b=2,找到狀態(tài)“阿”的下標(biāo)2,再根據(jù)“根”的序列碼d=4找到“阿根”的下標(biāo)baseb+d=8,同時

12、根據(jù)checkbaseb+d=b,表明“阿根”是某個詞的一部分，可以繼續(xù)查詢。然后再找到狀態(tài)阿根廷。它的下標(biāo)為y=12,此時basey0,checky=baseb+d=8,表明“阿根廷”在詞表中，查詢完畢。最后對雙數(shù)組Trie(Double-ArrayTrie)機(jī)制詞典進(jìn)行空間復(fù)雜度分析：該詞典機(jī)制主要增加的輔助成分是雙數(shù)組結(jié)構(gòu)，約120,000個狀態(tài)，另外考慮到實(shí)際應(yīng)用中，還需要獲得詞條的下標(biāo)，所以把雙數(shù)組調(diào)整為三數(shù)組，共需要空間為，120,000*3*4=1,440,000字節(jié)；另外，主詞典需要空間為50,000*113=5,650,000字節(jié)。總共占用空間：7,090,000字節(jié)。三、雙

13、編碼機(jī)制的詞典查詢算法1 .雙編碼的基本思想，GB-2312編碼的常用漢字共有6768個，每個漢字都可以從唯一地從區(qū)位碼映射到1-6768間的一個序列碼，從而每個漢字串都可以唯一地映射到一個數(shù)字串，這樣對于詞語的查詢可以轉(zhuǎn)化為基于數(shù)字串的查詢。雙編碼的查詢思想就是首先將漢字區(qū)位碼轉(zhuǎn)換成序列碼，從而使?jié)h字序列轉(zhuǎn)換成數(shù)碼序列；然后將漢字序列對應(yīng)的數(shù)碼序列轉(zhuǎn)換成數(shù)偶碼(代表兩個有理數(shù))。將整個詞表全部轉(zhuǎn)換成數(shù)偶碼表，排好序，供檢索用。從數(shù)碼序列到數(shù)偶碼的轉(zhuǎn)換主要是采用了歐幾里德算法(輾轉(zhuǎn)相除法)的思想8,保證了從數(shù)碼序列和數(shù)偶碼之間轉(zhuǎn)換的唯一性，同時還達(dá)到了一定程度上數(shù)據(jù)壓縮的目的。具體的轉(zhuǎn)換算法如

14、下：(1) 從序列碼到數(shù)偶碼的編碼：假定輸入數(shù)據(jù)序列存放在數(shù)組Seq口中，其長度為n.其中2(i=1,2,n)是漢字符的序碼。P,Q是一對輸出整數(shù)，代表一個既約有理數(shù)P/Q,是輸入數(shù)據(jù)序列的編碼，叫數(shù)偶碼。編碼過程如下：賦初值：Xo=0,Yo=1,Xi=1,Yi=0遞歸求解：Xi=Seqi-2*Xi-1+Xi-2i1Yi=Seqi-2*Yi-1+Yi-2i1獲得數(shù)偶碼：P=Xn+1Q=Yn+1( 2) 從數(shù)偶碼到序列碼的解碼算法：輸入數(shù)據(jù)是整數(shù)偶.輸出數(shù)據(jù)是它所代表的漢字(對應(yīng)的序碼)的序列，放在Out中，該序列的長度為n。解碼過程如下：為變量賦初始值：M0=QX0=P循環(huán)輾轉(zhuǎn)相除，將相除的結(jié)

15、果保存進(jìn)入數(shù)組Out,直到Mi為零，遞歸公式如下：Outi=(int)Xi/MiMi+1=Xi-Outi*MiXi+1=Mi2. 索引機(jī)制的建立對整個詞典進(jìn)行編碼之后，每個詞語就對應(yīng)著一對數(shù)偶碼，其特點(diǎn)是隨著詞語的長度增加，數(shù)值會變得很大，所以必須建立相應(yīng)索引，在這一點(diǎn)上本文進(jìn)行了相應(yīng)的多次探索，最后選擇了分段索引方式。具體來說就是對P值小于0xFFFFFF的詞語和大于0xFFFFFF的詞語分別建立索引，這樣做的原因是：1) 首先0xFFFFFF基本上是二字詞與三字詞的分界線，我們對使用的容量為49500條的詞典進(jìn)行統(tǒng)計，其中的單字詞語有1650條，雙字詞語有31838條，共33488條，占6

16、7.65%?？紤]到在具體應(yīng)用中，多字詞語不僅所占比例較小，而且它們出現(xiàn)的頻率要遠(yuǎn)低于雙字詞和單字詞，所以查詢算法應(yīng)該保證短詞的查詢速度更快。2) 另一方面，經(jīng)過統(tǒng)計，在詞典中，P碼小于0xFFFFFF的詞語個數(shù)為34243，而所有詞語個數(shù)為49500，這樣0xFFFFFF以下的P碼的數(shù)值分布更為密集，所以我們應(yīng)該對兩段分別采用不同的機(jī)制構(gòu)建索引。為了建立從雙碼到詞語位置的Hash機(jī)制，我們還需要盡可能地保證唯一性，讓每個生成的索引值盡量對應(yīng)唯一的一個詞語位置。查詢的具體實(shí)現(xiàn)函數(shù)如下：QuerryWord(char*Word)首先對Word編碼，生成數(shù)偶碼P和Q;If(P0xFFFFFF)原理類

17、似以一個具體查詢的例子來說明具體查詢過程：假設(shè)給定某一詞語“祖國”，進(jìn)行查詢，首先將字串“祖國”根據(jù)內(nèi)碼轉(zhuǎn)換為序列碼存入Seq數(shù)組，“祖”對應(yīng)3736,國對應(yīng)“936”,然后將序列數(shù)組轉(zhuǎn)化為數(shù)偶碼P,Q,其中P=0x356A59;Q=0x3A9,則索引Ind=0x56A59,經(jīng)過查找，Index1Ind.mark=0,Index1Ind.pos=14593,查找到WordsList14592,經(jīng)過驗(yàn)證WordsList14592.Valuep=P20,而且WordsList14592.Valueq=Q,則表明已經(jīng)查詢到了相應(yīng)的詞語，返回WordsList14592,完成查詢。IndexlWor

18、dsList,祖國3736936(P,Q)、0x56A58145900x56A59145910x56A5Ak14592,3. 雙編碼方法性能分析采用如上的哈希機(jī)制之后，可以保證較低的沖突概率。經(jīng)過分析，對于P值0xFFFFFF的哈希表，同一索引值對應(yīng)一個詞的比例占97.15%,同一索引值對應(yīng)兩個詞的比例占2.77%;對于P彳！0xFFFFFF的哈希表，同一索引值對應(yīng)一個詞的比例占88.31%,同一索引值對應(yīng)兩個詞的比例占10.58%,同一索引值對應(yīng)三個詞的比例為1.02%o考慮到查詢詞中雙字詞約占76%,所以我們可以說，雙編碼的沖突概率很低，對于一個漢字串，經(jīng)過編碼后，基本上就能通過哈希表一次

19、查到對應(yīng)的詞。小于0xFFFFFF大于0xFFFFFF我們對雙編碼的機(jī)制進(jìn)行相應(yīng)的空間復(fù)雜度分析：主詞典50000*113=5650000字節(jié)，索引(0xFFFFF+0xFFFF)*3=3342430字節(jié)，總共占用空間：8,992,330字節(jié)。從上面分析可以發(fā)現(xiàn)，雙編碼機(jī)制的查詢效率主要是通過犧牲空間來獲取的，我們針對詞表分別分段構(gòu)建的大小為0xFFFFF和0xFFFF的兩個數(shù)組，被利用的索引值有46779個，其利用率為4.19%,利用率比較低，但考慮到大數(shù)組占用的內(nèi)存空間(如上示，約3.3M)相對于當(dāng)前計算機(jī)的性能而言已經(jīng)不是什么問題，所以該方法是可行的。四、實(shí)驗(yàn)分析為對雙數(shù)組Trie(Do

20、uble-ArrayTrie)查詢算法和雙數(shù)組查詢算法作性能評測，我們選擇了逐字二分法作為性能比較的參照算法。關(guān)于逐字二分法的原理，請參考本文的引言部分以及相關(guān)的引用文獻(xiàn)。為模擬真實(shí)語境，實(shí)驗(yàn)主要是在切分的人民日報半年語料庫的基礎(chǔ)上進(jìn)行的，分別在相同的硬件環(huán)境下，用三種查詢機(jī)制對語料庫中出現(xiàn)的所有詞進(jìn)行查詢。實(shí)驗(yàn)分為三步：首先進(jìn)行數(shù)據(jù)統(tǒng)計分析；然后對三種查詢機(jī)制進(jìn)行速度比較；最后對每一種查詢機(jī)制的各個環(huán)節(jié)都進(jìn)行了速度上的分解分析。1.在速度評測之前，我們首先對語料庫和三種算法的動態(tài)性能進(jìn)行了相應(yīng)的統(tǒng)計分析，作為問題分析的參考：1)在人民日報語料庫基礎(chǔ)上對詞典中的49500個詞語進(jìn)行統(tǒng)計。其中單

21、字詞2595個,在訓(xùn)練預(yù)料中出現(xiàn)2062393次，比例為；雙字詞31838個，在訓(xùn)練語料中共出現(xiàn)2860757次；三字詞7858個，在訓(xùn)練語料中共出現(xiàn)165044次；四字詞7209個，共出現(xiàn)62829次?？梢娬鎸?shí)語境中單字詞和雙字詞的出現(xiàn)頻率遠(yuǎn)高于長詞。2)在人民日報半年切分預(yù)料庫的基礎(chǔ)上，我們對三種查詢方法的動態(tài)性能分別進(jìn)行了統(tǒng)計。對雙編碼機(jī)制的詞典查詢，經(jīng)過統(tǒng)計分析發(fā)現(xiàn)，平均每次查詢需要54.143次數(shù)值運(yùn)算、1次字符串長度運(yùn)算、16.548次讀取數(shù)組運(yùn)算；對雙數(shù)組Trie(Double-ArrayTrie)機(jī)制的詞典查詢，經(jīng)過統(tǒng)計分析發(fā)現(xiàn)，平均每次查詢需要30.44次數(shù)值運(yùn)算、1次字符串

22、長度運(yùn)算、1.857次讀取數(shù)組運(yùn)算；對逐字二分法機(jī)制的詞典查詢，經(jīng)過統(tǒng)計分析發(fā)現(xiàn)，平均每次查詢需要38.244次數(shù)值運(yùn)算、8.268次數(shù)組讀取運(yùn)算、4.268次字符串比較運(yùn)算、1次字符串copy運(yùn)算。從上面的統(tǒng)計信息可以看出：雙數(shù)組Trie(Double-ArrayTrie)機(jī)制的詞典查詢從算法復(fù)雜度上來說是最快的方法，雙編碼機(jī)制的詞典查詢在數(shù)值運(yùn)算和讀取數(shù)組運(yùn)算上復(fù)雜度較高，逐字二分法機(jī)制的詞典查詢則因?yàn)樵黾恿俗址容^、copy運(yùn)算增加了算法復(fù)雜度。2.接下來三種查詢算法的實(shí)驗(yàn)測試比較查詢算法名稱花費(fèi)時間(s)相對比較改進(jìn)二分法6.697100%雙編碼4.72570.6%雙數(shù)組Trie(D

23、ouble-ArrayTrie)1.40821.1%可見雙數(shù)組Trie(Double-ArrayTrie)是性能最好的一種查詢算法；雙編碼算法作為一種新的想法，查詢過程完全基于數(shù)值運(yùn)算，避免了字符串比較運(yùn)算，相對改進(jìn)二分法性能有所提高。3. 對三種方法進(jìn)行各個時間環(huán)節(jié)的分解分析雙編碼機(jī)制的各個環(huán)節(jié)時間分析：內(nèi)碼轉(zhuǎn)換為序列碼序列碼轉(zhuǎn)換為數(shù)偶碼產(chǎn)生索引值讀取索引數(shù)組進(jìn)行比較驗(yàn)證1.76040.67180.10561.29030.897237.26%13.21%2.23%27.31%19.99%從上面可以看出雙編碼機(jī)制查詢的主要性能瓶頸是之一是內(nèi)碼到序列碼的轉(zhuǎn)換過程，經(jīng)過分析，我認(rèn)為這個地方的性能較

24、低主要是因?yàn)樯尚蛄袛?shù)組，并進(jìn)行了數(shù)據(jù)傳遞。另一個瓶頸是讀取索引數(shù)組，因?yàn)槲覀優(yōu)榱吮ＷC索引的唯一性，作了一個較大的索引，這樣在讀取數(shù)組的時候，性能較低。雙數(shù)組Trie(Double-ArrayTrie)機(jī)制的各個環(huán)節(jié)時間分析:第一個字第二個字第三個字第四個字0.6810.6060.0970.02448.4%43.0%6.9%1.7%從上面的分析可以看出，雙數(shù)組Trie(Double-ArrayTrie)方法的各個環(huán)節(jié)時間消耗跟處理詞語數(shù)目成正比，第一個字處理對應(yīng)所有的詞語處理，第二個字處理對應(yīng)二字詞以上的詞語處理，如此類推。處理的主要方式是從當(dāng)前字生成序列碼，并通過加法來進(jìn)行狀態(tài)轉(zhuǎn)移。改進(jìn)二分

25、法機(jī)制的各個環(huán)節(jié)時間分析：根據(jù)首字確定范圍二分查找匹配詞語0.90795.789113.56%86.44%改進(jìn)二分法機(jī)制的主要時間耗費(fèi)在二分查找匹配詞語的過程中，因?yàn)橐M(jìn)行若干次字符串比較工作。4. 綜合評價雙數(shù)組Trie(Double-ArrayTrie)機(jī)制的詞典查詢算法中，若待查詞長度為N,則將漢字分別轉(zhuǎn)換為對應(yīng)的序列碼，經(jīng)過N次加法，即可查到相應(yīng)的詞語，無須折半查找。另外由于漢語中常用詞平均長度不到3個字，因此雙數(shù)組查詢算法的效率是極高的。這種方法缺點(diǎn)在于：構(gòu)造調(diào)整過程中，每個狀態(tài)都依賴于其他狀態(tài)，所以當(dāng)在詞典中插入或刪除詞語的時候，往往需要對雙數(shù)組結(jié)構(gòu)進(jìn)行全局調(diào)整，靈活性能較差。雙編

26、碼機(jī)制的詞典查詢算法，基本思想是把漢字詞語轉(zhuǎn)換到數(shù)碼的層次上，然后進(jìn)行詞典組織和詞語查詢。這種算法的優(yōu)勢在于避免了傳統(tǒng)查詢中的字符串操作，在哈希機(jī)制上更為靈活，有較大的改進(jìn)空間；同時詞典組織的方式是傳統(tǒng)的線性表，調(diào)整起來十分方便；另外，在本算法中突出體現(xiàn)了短詞優(yōu)先的特性，提高了查詢效率。這種算法的缺點(diǎn)在于，漢字詞語轉(zhuǎn)化到數(shù)碼的壓縮率還不夠大，導(dǎo)致生成的數(shù)偶碼較大，隨著詞語長度的增加，可能導(dǎo)致溢出，必須引入大數(shù)機(jī)制；另外，進(jìn)行詞典組織的時候需要構(gòu)建一個較大的數(shù)組，限制了查詢效率的提高。五、結(jié)語本文在雙數(shù)組Trie(Double-ArrayTrie)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，實(shí)現(xiàn)了一種基于漢語的詞典查詢算

27、法，它只需要進(jìn)行若干次加法運(yùn)算就可以完成查詢，速度上相對其它詞典查詢機(jī)制有了明顯的提高，同時相同前綴的詞語在詞典中也有邏輯上的關(guān)系，因此在分詞中可以有很好的應(yīng)用。它的缺點(diǎn)是構(gòu)造過程復(fù)雜，插入刪除每一條詞語都會引發(fā)對整個詞典的調(diào)整，因此，最好應(yīng)用于實(shí)時性要求較高的封閉式詞典中。本文還提出了雙編碼機(jī)制的漢語詞典查詢算法，該算法的特點(diǎn)是，通過算術(shù)編碼，可以把任意字符串轉(zhuǎn)化為有理數(shù)，從而一切查詢工作可以基于有理數(shù)來進(jìn)行，避免了二分法的字符串比較，在效率上有所提高，而且詞典以線性表組織，調(diào)整起來也比較容易。這種方法的缺點(diǎn)是從字符串轉(zhuǎn)化到有理數(shù)的過程較復(fù)雜，同時生成的有理數(shù)過大，建立索引難度比較大，既要盡

28、可能地避免數(shù)據(jù)稀疏，同時還不能讓索引過大，本文通過實(shí)驗(yàn)探索，找到了比較合適的索引機(jī)制。本詞典相對改進(jìn)二分法詞典，性能有了較大的提高。這種算法改進(jìn)的余地還比較大，可以在數(shù)碼生成環(huán)節(jié)，哈希機(jī)制等環(huán)節(jié)作近一步的改進(jìn)，可以應(yīng)用于詞語長度較小，對速度要求較高的開放式詞典中。參考文獻(xiàn)1王秀坤，李政，簡幼良，劉劍基.基于Hash方法的機(jī)器翻譯詞典的組織與構(gòu)造.大連理工大學(xué)學(xué)報，1996,(3)2 孫茂松，左正平，黃昌寧.漢語自動分詞詞典機(jī)制的實(shí)驗(yàn)研究.中文信息學(xué)報，2000,(1)3 李慶虎，陳玉健，孫家廣.一種中文分詞詞典新機(jī)制雙字哈希機(jī)制.中文信息學(xué)報，2003,(4)4 楊文峰，陳光英，李星.基于PATRICIAtree的漢語自動分詞詞典機(jī)制.中文信息學(xué)報，2001,(3)5 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).北京：清華大學(xué)出版社，19926 Aoe,J.AnEf