基于詞典的中文自動(dòng)分詞系統(tǒng)

基于詞典的中文自動(dòng)分詞系統(tǒng)

1基于詞典的體系綜合優(yōu)化隨著個(gè)人計(jì)算機(jī)和internet網(wǎng)絡(luò)的普及，中文信息的處理變得一個(gè)非常重要的領(lǐng)域。中文字務(wù)用戶(hù)使用的許多軟件和硬件都與中文信息處理有關(guān)。我們必須建立自己的中文信息處理系統(tǒng)。許多輔助軟件是巨大的開(kāi)發(fā)成本。由于許多輔助軟件的獨(dú)立開(kāi)發(fā)導(dǎo)致中文處理的水平不高，因此開(kāi)發(fā)一種統(tǒng)一、共享、高水平的中國(guó)信息處理系統(tǒng)非常重要。基于該詞典的自動(dòng)漢語(yǔ)排序技術(shù)在中文信息處理中占有基本地位。在公共漢語(yǔ)處理系統(tǒng)中，需要平衡不同方面的性能需求。提高調(diào)查操作的空間和時(shí)間效率非常重要。近年來(lái)提出的許多中文句子算法重視不同方面的性能改善，需要充分考慮性能優(yōu)化，并在實(shí)踐中不斷提高性能。隨著社會(huì)的發(fā)展，新詞和短語(yǔ)的產(chǎn)生，多語(yǔ)混合的詞條和包含特定符號(hào)的詞條也大量使用。新字典無(wú)法滿(mǎn)足人們的工作量和生活需求?？焖僬_地在詞典中添加新詞（短語(yǔ)），對(duì)基本無(wú)用的舊詞進(jìn)行分類(lèi)是非常重要的。此外，在之前的分詞系統(tǒng)項(xiàng)目中，考慮到大量使用快速減速對(duì)計(jì)算算法的影響最大的原因。在一些算法測(cè)試中，結(jié)果是非常可疑的，不同的結(jié)論在不同的方面是矛盾的。因此，本文提出了綜合優(yōu)化的原則，從更全面的角度評(píng)估了幾種典型算法，并提出了一種綜合優(yōu)化的分詞系統(tǒng)。2查詞為編碼查詢(xún)?cè)谖墨I(xiàn)中,孫茂松等提出了評(píng)價(jià)分詞系統(tǒng)的3種基本查詢(xún)操作:(1)指定詞查找;(2)最長(zhǎng)詞查找;(3)全部詞查找.該體系被許多論文引用,影響較大.本文中為了綜合性能,希望詞典能夠根據(jù)指針快速定位每一個(gè)詞條,比如根據(jù)詞條屬性,反查出某詞條后,要能夠快速給出該詞條的漢字串.即第四種查詢(xún)方法:(4)詞的字符串查詢(xún).具體描述如下:查詢(xún)方式1(指定詞查找):在分詞詞典中查找指定詞W0(詞在分詞詞典中的定位);這是一種最基本的查詢(xún)方式.給定詞W0,返回W0在分詞詞典中的位置,以便得到W0的各類(lèi)附屬信息.此時(shí)W0是確定的,所以可以簡(jiǎn)單地通過(guò)二分查找給出結(jié)果.查詢(xún)方式2(最長(zhǎng)詞查找):根據(jù)分詞詞典,在漢字串S中查找從某一指定位置i開(kāi)始的最長(zhǎng)詞Wi,max(對(duì)應(yīng)最大匹配分詞法);有別于查詢(xún)方式1,這里最長(zhǎng)詞Wi,max無(wú)法預(yù)知,需要在查詢(xún)過(guò)程中動(dòng)態(tài)地確定.通常的做法是嘗試始于位置i的所有可能長(zhǎng)度的詞,多次運(yùn)用查詢(xún)方式1來(lái)完成查詢(xún).查詢(xún)方式3(全部詞查找):根據(jù)分詞詞典,在漢字串S中查找從某一指定位置i開(kāi)始的所有的詞Wi,1;Wi,2;……;Wi,max(對(duì)應(yīng)全切分分詞法)查詢(xún)方式4(詞的字符串查詢(xún)):根據(jù)詞典中詞條的位置,查找該詞的字符串.即詞典正文的存儲(chǔ)方式要恰當(dāng).為了評(píng)估詞典維護(hù)的方便性,增加詞、刪除詞和編輯詞條的性能也是重要的評(píng)價(jià)指標(biāo).3般優(yōu)化原則算法在數(shù)學(xué)上的優(yōu)化是第一步,也是最關(guān)鍵的.本質(zhì)上不同的算法,差別極大,在查詢(xún)中依次比較查找是最慢的;二分查找改進(jìn)很大,但要求被查詢(xún)的集合中的元素是有序的,如果元素本身排序困難,則需要進(jìn)行編碼,然后建立索引,這在空間上花了一定的代價(jià);根據(jù)指針查找數(shù)組是最快的,但指針的計(jì)算不要太復(fù)雜,如果數(shù)組太稀疏,則空間的開(kāi)銷(xiāo)太大.第二步是算法的運(yùn)用.比如在最長(zhǎng)詞查找時(shí),通常的做法是嘗試始于某位置的所有可能長(zhǎng)度的詞,多次運(yùn)用指定詞查詢(xún)來(lái)試探,速度很慢.這就是算法應(yīng)用不當(dāng)造成的.實(shí)際上以最大長(zhǎng)度的試探詞進(jìn)行第一次指定詞查詢(xún)失敗的位置離要查找的最長(zhǎng)詞很近了,第二次的試探完全可以在更小的查詢(xún)范圍和更限定的試探詞選擇情況下進(jìn)行,從而大大地提高效率.本文在后面還有詳述.第三步是算法在計(jì)算機(jī)上實(shí)現(xiàn)的優(yōu)化.下面主要討論現(xiàn)代計(jì)算機(jī)技術(shù)帶來(lái)的一般優(yōu)化原則.近年來(lái),計(jì)算機(jī)技術(shù)得到飛速發(fā)展,各個(gè)部件的性能都大大提高.但是CPU的計(jì)算速度提高的幅度遠(yuǎn)遠(yuǎn)高于內(nèi)存數(shù)據(jù)的讀寫(xiě)速度,為了減少CPU等待數(shù)據(jù)的時(shí)間,CPU中設(shè)計(jì)了芯片內(nèi)的一級(jí)緩存,同時(shí)在計(jì)算機(jī)中還設(shè)計(jì)了二級(jí)緩存(可以與CPU同頻也可以不同頻),這個(gè)趨勢(shì)將維持相當(dāng)長(zhǎng)的時(shí)間,目前使用最多的Intel奔騰系列處理器和PC體系架構(gòu)就使用了這種設(shè)計(jì).這充分說(shuō)明各種算法的優(yōu)化必須主要考慮如何減少CPU與內(nèi)存的數(shù)據(jù)交換,如何使CPU需要的數(shù)據(jù)能夠預(yù)取(Prefetch)到緩存中,然后才是CPU內(nèi)部計(jì)算指令的優(yōu)化.Intel編寫(xiě)的《IA-32Intel?架構(gòu)優(yōu)化參考手冊(cè)》中提出了許多數(shù)據(jù)預(yù)取的優(yōu)化原則,一些優(yōu)化建議如下:—Minimizeuseofglobalvariablesandpointers(盡量少地使用全局變量和全局指針)—Minimizeuseofcomplexcontrolflow(盡量少地使用復(fù)雜的控制流)—MinimizememorybankconflictsbyapplyingarraygroupingtogroupcontiguouslyuseddatatogetherorallocatingdataWithin4KBmemorypages.(運(yùn)用連續(xù)的數(shù)組或?qū)?shù)據(jù)定位在4KB內(nèi)存頁(yè)范圍內(nèi)以盡量地減少內(nèi)存棧的沖突)—Faraheadenoughtoallowinterimcomputationtooverlapmemoryaccesstime.(盡可能地用內(nèi)部計(jì)算代替內(nèi)存讀寫(xiě)的時(shí)間)—Nearenoughthattheprefetcheddataisnotreplacedfromthedatacache.(數(shù)據(jù)盡量靠近以避免預(yù)取到緩存的數(shù)據(jù)被代替)詞典的各種查詢(xún)算法涉及到字串比較、指針計(jì)算、尋址、內(nèi)存讀寫(xiě),以及算術(shù)和邏輯運(yùn)算等.在CISC類(lèi)型的CPU中(比如Intel奔騰系列處理器),加法和邏輯運(yùn)算很快;比較操作等同于減法,比加法略慢;片內(nèi)一級(jí)緩存的讀寫(xiě)相當(dāng)于加法;乘法比加法慢許多,但在CISC類(lèi)型的CPU中專(zhuān)門(mén)有乘法的硬件優(yōu)化設(shè)計(jì),比以前通過(guò)多次加法來(lái)實(shí)現(xiàn)乘法的算法快不少;二級(jí)緩存的讀寫(xiě)與乘法相當(dāng);除法和取模運(yùn)算更慢一些;內(nèi)存中數(shù)據(jù)的讀寫(xiě)最慢,常常是速度提高得主要瓶頸.4以三部分三用于詞典的屬性表1分詞系統(tǒng)需要盡可能少地占用存儲(chǔ)空間,使詞典和詞條的重要屬性可以全部存放在內(nèi)存中;還要考慮主要查詢(xún)操作讀寫(xiě)詞典時(shí),方便數(shù)據(jù)預(yù)取到緩存中,同時(shí),詞典的數(shù)據(jù)結(jié)構(gòu)要方便主要的查詢(xún)和維護(hù)操作的算法實(shí)現(xiàn).實(shí)質(zhì)上,詞典由4部分組成:(1)詞典正文,存放詞條的字符串和指向該詞條的屬性;(2)詞條屬性:存放詞條對(duì)應(yīng)的主要屬性和指向詞條正文中該詞條的位置的指針;(3)首字散列表:國(guó)家標(biāo)準(zhǔn)用于計(jì)算機(jī)進(jìn)行漢字處理的漢字和符號(hào)的序列,根據(jù)漢字的機(jī)內(nèi)碼可以方便和唯一地確定漢字在序列中的位置;(4)索引:用于搜索某字符串是否在詞典正文中的輔助數(shù)據(jù),根據(jù)搜索算法的不同,索引部分有較大區(qū)別,可以是二分查找的索引表,可以是TRIE索引樹(shù),也可以是PATRICIA搜索樹(shù),還可以是單字或多字的哈希散列索引表,實(shí)際上常常是幾種索引的組合.下面介紹兩種經(jīng)典的詞典數(shù)據(jù)結(jié)構(gòu),并分析如何按照方便緩存預(yù)取的方式進(jìn)行優(yōu)化.4.1確定使用表1.文獻(xiàn)所敘述的基于整詞二分的分詞詞典機(jī)制如圖1所示,該機(jī)制的詞典結(jié)構(gòu)分為詞典正文,詞索引表,首字散列表等3部分.詞典正文是以詞為單位的有序表,詞索引表是指向詞典正文中每個(gè)詞的指針表.通過(guò)首字散列表的哈希定位和詞索引表很容易確定指定詞在詞典正文中的可能位置范圍,通過(guò)詞索引表和詞典正文的配合,很容易實(shí)現(xiàn)指定詞在詞典正文中的整詞二分進(jìn)行快速查找定位.在圖1中,詞索引表是1個(gè)連續(xù)的數(shù)組,其實(shí)可以按照首字的不同,最多可以分成6763不同的小數(shù)組,也可以把一些太小的鄰近數(shù)組合成1個(gè)較大的數(shù)組,希望這些分散的數(shù)組都小于4KB,而且它們對(duì)應(yīng)的詞典正文也連續(xù)排列,也小于4KB,好將它們預(yù)取到緩存.對(duì)于某個(gè)首字對(duì)應(yīng)的索引數(shù)組或詞典正文大于4KB時(shí),可以采用其他種種技術(shù)手段將其劃分為更小的數(shù)組.4.2按文本個(gè)數(shù)分的方法,有以下簡(jiǎn)稱(chēng)TRIE索引樹(shù)是一種以樹(shù)的多重鏈表形式表示的鍵樹(shù),面向中文的TRIE索引樹(shù)的結(jié)點(diǎn)應(yīng)允許指針個(gè)數(shù)變化.基于TRIE樹(shù)的分詞詞典由兩部分組成(見(jiàn)圖2).第一部分為首字散列表,對(duì)應(yīng)漢字的單元包括TRIE大小(2字節(jié))和指向該漢字的TRIE索引樹(shù)的根結(jié)點(diǎn)指針(4字節(jié)).第二部分為T(mén)RIE索引樹(shù)結(jié)點(diǎn),是一個(gè)按關(guān)鍵字排序的數(shù)組(方便二分查找):每個(gè)單元包括:關(guān)鍵字(2字節(jié)):單一漢字;子樹(shù)大小(2字節(jié)):以從根結(jié)點(diǎn)到當(dāng)前單元的關(guān)鍵字組成的子串為前綴的詞的個(gè)數(shù);子樹(shù)指針(4字節(jié)):子樹(shù)大小非0時(shí),指針指向子樹(shù);否則指向葉子.由于TRIE索引樹(shù)已蘊(yùn)涵了詞條信息,因此詞典中可以不必顯式地羅列詞條,可直接存儲(chǔ)詞的附屬信息(葉子指針直接指向這些信息).但是為了快速進(jìn)行查詢(xún)方式4(詞的字符串查詢(xún))操作,葉子指針指向的存儲(chǔ)單元還是需要顯式地列出詞條內(nèi)容.TRIE索引樹(shù)的結(jié)構(gòu)本身就是分成一個(gè)個(gè)按關(guān)鍵字排序的小數(shù)組,非常適合預(yù)取到緩存中進(jìn)行二分查找.5一些搜索算法的介紹5.1最壞時(shí)的編碼算法二分查找算法是一個(gè)相當(dāng)好的簡(jiǎn)便算法,其基本思想來(lái)將N個(gè)元素的有序集合分成個(gè)數(shù)大致相同的兩半,取第[N/2]個(gè)元素與待測(cè)的元素作比較,決定待測(cè)的元素在哪個(gè)半?yún)^(qū),然后依次遞歸.整個(gè)算法在最壞情況下的計(jì)算復(fù)雜性為O(㏒n).當(dāng)查找的索引范圍比較小,索引可以一次性放入緩存并且關(guān)鍵字(詞)包含在索引中時(shí),該算法比PATRICIA樹(shù)搜索算法略好,因?yàn)镻ATRICIA樹(shù)搜索是不平均的二叉樹(shù),所以分支節(jié)點(diǎn)的深度要大于二分查找;如果關(guān)鍵字(詞)要通過(guò)索引指針從內(nèi)存中毒去,但存放相當(dāng)集中,可以一次放入緩存,則增加一次內(nèi)存讀取就行,那么就比PATRICIA樹(shù)略差一點(diǎn).5.2多對(duì)待表項(xiàng)的連接基于詞典機(jī)制的哈希索引的實(shí)現(xiàn)過(guò)程中,往往用單個(gè)漢字做取模的哈西索引,單個(gè)漢字的哈希值H=VmodL,其中V是此漢字的內(nèi)碼,L是Hash表的可變表長(zhǎng).對(duì)于兩個(gè)漢字組合的哈希值計(jì)算可以是H=V1×V2modL,V1和V2對(duì)應(yīng)兩個(gè)漢字的機(jī)內(nèi)碼.但是當(dāng)漢字串再長(zhǎng)一些,多個(gè)機(jī)內(nèi)碼相乘會(huì)很快溢出,必須設(shè)計(jì)專(zhuān)門(mén)的算法才能進(jìn)行,所以很少被使用.哈西索引算法常采用鏈地址法來(lái)處理溢出情況,它把哈希表中儲(chǔ)存的所有關(guān)鍵碼劃分為L(zhǎng)個(gè)子集合(桶),具有同一個(gè)哈希值H的表項(xiàng)均被置于第H個(gè)桶中;同一個(gè)桶中的不同表項(xiàng)通過(guò)一個(gè)單鏈表進(jìn)行連接.理想分布是桶與字一一對(duì)應(yīng);正常分布有接近2/3的桶對(duì)應(yīng)一個(gè)或多個(gè)漢字,1/3為空;最差的分布是一個(gè)桶對(duì)應(yīng)所有漢字,其他桶為空.這就需要通過(guò)選擇恰當(dāng)?shù)谋黹L(zhǎng)L使哈希索引接近理想情況.在關(guān)鍵碼相互獨(dú)立的假設(shè)下,統(tǒng)計(jì)意義上,正常分布出現(xiàn)的概率最大.為了避免最差分布出現(xiàn),關(guān)鍵碼數(shù)應(yīng)該是一個(gè)大數(shù),實(shí)際工作中20就可以看作為大數(shù),100是比較保險(xiǎn)的閾值.哈希索引算法的過(guò)程是:(1)通過(guò)待查詢(xún)?cè)~S,取出指定的漢字,計(jì)算該字的哈希值H;(2)讀出H指向的詞條T和指向下一個(gè)相同哈希值的詞條的指針P,如果T為空,停止;(3)比較T和S,如果相同,查詢(xún)成功,停止;如果不同,讀出P指向的新T和新P,重復(fù)(3)直到T為空便停止.對(duì)于哈希索引算法,需要在CPU內(nèi)對(duì)S做一些比較復(fù)雜的取模運(yùn)算,與內(nèi)存的存取速度相比就是非?？斓?所以理想情況的哈希索引算法最好,只需要根據(jù)哈西值H從內(nèi)存中的桶中讀取關(guān)鍵字與S比較,就完成了;對(duì)于正常情況,有時(shí)需要幾次讀取關(guān)鍵字和指針,如果同一個(gè)桶中的后續(xù)關(guān)鍵字在內(nèi)存中存放得足夠近,在讀第二個(gè)關(guān)鍵字時(shí),其它關(guān)鍵字也會(huì)被預(yù)取到緩存,則以后再讀關(guān)鍵字時(shí),就在緩存中了,所以平均來(lái)看仍是非常快的;對(duì)于最壞情況,則還不如不用哈希算法,就是直接用最笨的依次比較算法也會(huì)更好.5.3根據(jù)信息的方向,選擇合適的位串和轉(zhuǎn)向抗辯事由PATRICIAtree本質(zhì)上是一種壓縮的二叉查詢(xún)樹(shù),它將關(guān)鍵詞作為二進(jìn)制位串記錄在樹(shù)的結(jié)構(gòu)中,從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的每一條路徑都代表一個(gè)關(guān)鍵詞位串.在PATRICIAtree中,關(guān)鍵詞的具體信息都保存在葉子結(jié)點(diǎn)上,PATRICIAtree的內(nèi)部結(jié)點(diǎn)則用來(lái)記錄關(guān)鍵詞的路徑,它有3個(gè)基本的數(shù)據(jù)項(xiàng):比較位、左指針、右指針,其中,左指針和右指針?lè)謩e指向該結(jié)點(diǎn)的左、右子樹(shù),比較位記錄的是從根結(jié)點(diǎn)到達(dá)該結(jié)點(diǎn)的所有位串中第一個(gè)不相同位的位置.判斷查詢(xún)?cè)~是否存在于詞典中,只須從PATRICIAtree的根結(jié)點(diǎn)出發(fā),根據(jù)查詢(xún)?cè)~位串(包括結(jié)尾處的‘0’)在PATRICIAtree中尋找路徑.當(dāng)比較位為0時(shí),位串轉(zhuǎn)向左子樹(shù),當(dāng)比較位為1時(shí),位串轉(zhuǎn)向右子樹(shù).若比較完所有位后,查詢(xún)?cè)~位串不能到達(dá)葉子結(jié)點(diǎn),則可以斷定該查詢(xún)?cè)~不在詞典中.在查詢(xún)?cè)~位串到達(dá)葉子結(jié)點(diǎn)時(shí),由于只對(duì)查詢(xún)?cè)~中某幾位進(jìn)行了比較,并不能保證查詢(xún)?cè)~與葉子結(jié)點(diǎn)中的關(guān)鍵詞一定是相同的,在這種情況下,還要對(duì)兩者進(jìn)行一次字符串的比較,相同才表明查詢(xún)成功.對(duì)于PATRICIA樹(shù)搜索算法,首先要從內(nèi)存讀取根節(jié)點(diǎn)的比較位和轉(zhuǎn)向指針,作簡(jiǎn)單的比較運(yùn)算,再讀取子節(jié)點(diǎn)的比較位和轉(zhuǎn)向指針,經(jīng)過(guò)多次比較與讀取,到達(dá)葉節(jié)點(diǎn)讀取詞條.如果整個(gè)PATRICIA樹(shù)比較小,在內(nèi)存中的安排又符合數(shù)據(jù)預(yù)取的條件,則經(jīng)過(guò)第一次從內(nèi)存讀取根節(jié)點(diǎn)數(shù)據(jù)的操作,就可以把整個(gè)整個(gè)PATRICIA樹(shù)的全部?jī)?nèi)部節(jié)點(diǎn)放在緩存中,多次的比較位和轉(zhuǎn)向指針的讀取就在緩存中操作,相當(dāng)于多次的加法運(yùn)算,可能5次左右的讀取與比較相當(dāng)于一次哈希索引的取模運(yùn)算,則7次左右相當(dāng)于相同哈希值的關(guān)鍵碼的平均數(shù)為2得正常分布的哈希索引計(jì)算,葉節(jié)點(diǎn)的詞條內(nèi)容一般還需一次內(nèi)存的讀取;如果PATRICIA樹(shù)很大,不能一次性放入緩存,則多次的內(nèi)存讀操作會(huì)將速度降得很慢.所以盡量地切分PATRICIA樹(shù),使其足夠小時(shí)很重要的.PATRICIA樹(shù)在增加新詞和刪除舊詞方面非常方便.增加新詞X時(shí),先建立X的葉結(jié)點(diǎn),搜索一次PATRICIA樹(shù)找到最接近的詞條S,然后從頭比較出X和S的第一個(gè)不同位t,然后再搜索一次PATRICIA樹(shù)路徑,到達(dá)t位時(shí),插入一個(gè)新節(jié)點(diǎn)n,將父節(jié)點(diǎn)指向同路徑的指針繼承指向原來(lái)的子節(jié)點(diǎn),使父節(jié)點(diǎn)指向新節(jié)點(diǎn)n,新節(jié)點(diǎn)n的另一條路經(jīng)指向新詞X.對(duì)待刪除詞Y進(jìn)行一次查詢(xún),找到待刪除詞存在的葉子結(jié)點(diǎn),將此葉子結(jié)點(diǎn)及其父結(jié)點(diǎn)從樹(shù)中刪除,將其父結(jié)點(diǎn)的另一個(gè)子樹(shù)(或葉子結(jié)點(diǎn))直接連在其祖父結(jié)點(diǎn)上.當(dāng)PATRICIAtree只有一根結(jié)點(diǎn)和兩個(gè)葉子結(jié)點(diǎn)時(shí),只刪除待刪除詞所在的葉子結(jié)點(diǎn).針對(duì)緩存優(yōu)化的幾種情況的搜索算法的比較見(jiàn)表1.根據(jù)以上的分析,理想和正常分布下的哈希索引很好,但是差的分布下它又很差,這在搜索范圍很小時(shí)出現(xiàn)的概率較大,這時(shí)使用PATRICIA樹(shù)(小)或者二分查找(小)會(huì)更好.6哈希拉索tri索引國(guó)標(biāo)GB2312漢字編碼表就是一個(gè)理想的哈希索引表,共收錄了6763個(gè)漢字,根據(jù)漢字的機(jī)內(nèi)碼,漢字在編碼表中的位置h=(c1-0xB0)×94+(c2-0xA1),其中,h代表某漢字在編碼表中的位置(就是哈希值),c1、c2代表該漢字的機(jī)內(nèi)碼.在基于詞典的各種具體中文分詞軟件的實(shí)現(xiàn)中都應(yīng)該利用首字哈希散列表提高效率,同時(shí)縮小搜索范圍.基于TRIE索引樹(shù)的分詞詞典數(shù)據(jù)結(jié)構(gòu),是逐字搜索來(lái)定位一個(gè)詞的,每一個(gè)字的二分查找都可以用哈希索引代替二分查找來(lái)提高效率,對(duì)于相同哈希值的關(guān)鍵字還可以用二分查找.對(duì)于小于32個(gè)搜索項(xiàng)的二分查找就不該用哈希索引了,這時(shí)平均來(lái)看,哈希索引并不比二分查找更優(yōu).6.1查檢行為中使用的問(wèn)題文獻(xiàn)給出了一個(gè)整詞二分法進(jìn)行查詢(xún)方式2(最長(zhǎng)詞查找)的例子:[例1]查詢(xún)S“水怪大白天現(xiàn)形一個(gè)多小時(shí)這個(gè)令人驚異的消息不徑而走.”中從“大”字開(kāi)始的最長(zhǎng)的詞.(1)取從“大”字開(kāi)頭最長(zhǎng)可能的漢字串:wi,max=“大白天現(xiàn)形一個(gè)多小時(shí)這個(gè)令人驚異的”(詞典中最長(zhǎng)詞為17個(gè)漢字);(2)用整詞二分法在詞典中查找候選詞wi,max,失敗;(3)去掉wi,max最后一個(gè)字,重復(fù)步驟(2),失敗;(4)..(5)經(jīng)過(guò)14次的錯(cuò)誤嘗試,wi,max最終消減到“大白天”,查找成功,于是返回wi,max=“大白天”.首先分析這14次的查找失敗(圖3).在同一位置的14次查找失敗,顯然這樣的查找效率是低下的,這也就是各種分詞詞典機(jī)制比整詞二分效率高很多的原因.由二分法的查找過(guò)程知道,在一次查找失敗中最后區(qū)間的兩個(gè)端點(diǎn)數(shù)據(jù)與所要查找的數(shù)據(jù)最為接近.簡(jiǎn)單的查詢(xún)優(yōu)化是,在每次查找失敗時(shí),再次查找時(shí)遵守新的規(guī)則:失敗位置的最后區(qū)間的low端(索引號(hào)靠前面)的詞與所要查詢(xún)的詞從首字開(kāi)始依次比較相同位置的漢字直到不相同為止,記錄相同漢字的個(gè)數(shù)作為下次查詢(xún)的長(zhǎng)度,范圍縮小為首字指向的起點(diǎn)到失敗的位置,如果長(zhǎng)度與low端的詞的長(zhǎng)度相等,那么low端的詞就是要找的最長(zhǎng)詞.上例采用這種方式來(lái)查詢(xún),在經(jīng)過(guò)一次查詢(xún)后,第二次查詢(xún)的漢字長(zhǎng)為3個(gè)漢字的長(zhǎng)度,這樣就只要查詢(xún)“大白天”,再次查找顯然就查找成功了.經(jīng)過(guò)這樣的處理,查詢(xún)效率提高很多.對(duì)于最長(zhǎng)詞大于2個(gè)字時(shí),優(yōu)化后的整詞二分優(yōu)于逐字二分,甚至還優(yōu)于TRIE索引樹(shù);對(duì)于最長(zhǎng)詞為2個(gè)字時(shí),優(yōu)化后的整詞二分與逐字二分相當(dāng).文獻(xiàn)中的逐字二分法有錯(cuò)誤,在進(jìn)行最長(zhǎng)詞查詢(xún)時(shí),文中的停止條件有誤.修正錯(cuò)誤后,在各種查詢(xún)時(shí),逐字二分法應(yīng)該都差于TRIE索引樹(shù).6.2優(yōu)化后的整詞二分法測(cè)試?yán)顟c虎等提出了雙字哈希機(jī)制的中文分詞算法,基本思路正確,但是在首字哈希索引的建立中錯(cuò)誤地用取模的哈希算法,反而降低了效率.應(yīng)該直接用國(guó)標(biāo)的漢字編碼表.在剩余字串的數(shù)據(jù)結(jié)構(gòu)中沒(méi)有詞條的索引,只能進(jìn)行逐條比較,算法很差;這時(shí),完全可以采用優(yōu)化后的整詞二分法.他們的測(cè)試中TRIE索引樹(shù)算法、逐字二分算法和雙字Hash索引都采用Java語(yǔ)言在相同的軟硬件環(huán)境(OS:WindoWs2000Server;JDK:Version11311;CPU:PentiumIII667MHz;Memory:256M)來(lái)實(shí)現(xiàn),得出空間占用,TRIE索引樹(shù)>雙字Hash索引>整詞二分=逐字二分;速度,雙字Hash索引>TRIE索引樹(shù)>逐字二分>整詞二分的結(jié)論;這個(gè)結(jié)論與孫茂松等的結(jié)論有矛盾,但李慶虎等沒(méi)有給出說(shuō)明.在速度方面,TRIE索引樹(shù)>逐字二分的結(jié)論正確.6.3基于空間占用比整詞東南角的空間占用算法楊文峰等提出基于PATRICIAtree的漢語(yǔ)自動(dòng)分詞算法,并與逐字二分算法進(jìn)行了測(cè)試比較,得出查詢(xún)速度有一定提高(30-50%),添加詞條和刪除詞條的速度有本質(zhì)提高(4-8倍)的結(jié)論;通過(guò)計(jì)算,得出空間占用比整詞二分算法和TRIE索引樹(shù)算法大的結(jié)論.馬哲、姚敏采用首字哈希散列表方法改進(jìn)了基于PATRICIAt