一種快速中文分詞機(jī)制

隨著中文網(wǎng)絡(luò)覆蓋的大規(guī)模發(fā)展，包含中文信息的網(wǎng)絡(luò)數(shù)據(jù)也在迅速擴(kuò)張。長期以來，對中國網(wǎng)絡(luò)數(shù)據(jù)的實(shí)時(shí)分析和處理已成為下一代中國信息處理技術(shù)必須關(guān)注的問題。作為中國信息事務(wù)管理的基礎(chǔ)，它已廣泛應(yīng)用于漢語搜索、人工智能、信息提取、文本搜索等領(lǐng)域。成功的中文分詞機(jī)制需要同時(shí)具有較高的詞匯切分準(zhǔn)確性和快速的詞匯切分能力.其中,前者需要解決未登錄詞匯(out-of-vocabulary)識別和詞匯歧義切分等難題,目前主要采用字符串頻度統(tǒng)計(jì),語料字詞標(biāo)注等機(jī)器學(xué)習(xí)方法;而快速詞匯切分能力是關(guān)系到整個(gè)中文信息處理系統(tǒng),特別是實(shí)時(shí)處理類應(yīng)用系統(tǒng)可用性的關(guān)鍵技術(shù),目前主要通過設(shè)計(jì)高效的分詞詞典機(jī)制來實(shí)現(xiàn)速度提升.此類快速分詞機(jī)制一般基于傳統(tǒng)的詞典分詞方法,依靠已有的特征詞典作為文本切分匹配依據(jù),設(shè)計(jì)簡單,實(shí)現(xiàn)容易,算法效率很高,詞典法分詞機(jī)制中與分詞速度相關(guān)的有2個(gè)要素:詞典構(gòu)造方法和詞匯匹配方法,這2個(gè)方面相互關(guān)聯(lián).常見的詞匯匹配方法有前向匹配、后向匹配、最大匹配、逐字匹配等.目前研究認(rèn)為,采用前向最大匹配是分詞速度最高的匹配方法.本文不研究匹配方法造成的分詞速度差異,主要通過研究不同詞典的構(gòu)造方法來實(shí)現(xiàn)高速的分詞機(jī)制.文中第1部分簡單描述了幾種經(jīng)典分詞詞典機(jī)制;第2部分詳細(xì)介紹幾種改進(jìn)詞典機(jī)制;在第3部分介紹作者提出的一種快速中文分詞詞典構(gòu)造機(jī)制:雙字詞和長詞哈希索引機(jī)制(double-character-and-long-vocabulary-hash-indexing);第4部分通過分析和實(shí)驗(yàn)說明新體制與原有體制相比具有的優(yōu)勢.1傳統(tǒng)的詞典組織最為典型的分詞詞典機(jī)制有以下3類:整詞二分法、TRIE索引樹法和逐字二分法.1.1確定復(fù)雜詞的定位和導(dǎo)致匹配機(jī)制整詞二分法的詞典結(jié)構(gòu)分為詞典正文、詞索引表、首字散列表等3級.通過首字散列表的哈希定位和詞索引表,很容易確定指定詞在詞典正文中的可能位置范圍,進(jìn)而在詞典正文中通過整詞二分進(jìn)行定位.基本的機(jī)制結(jié)構(gòu)如圖1.1.2tre索引樹人工樹人本機(jī)TRIE索引樹是一種以樹的多重鏈表形式表示的鍵樹,基于TRIE索引樹的詞典機(jī)制由首字散列表和TRIE索引樹結(jié)點(diǎn)2部分組成.TRIE索引樹的優(yōu)點(diǎn)是分詞應(yīng)用中,在對被切分語句的一次掃描過程中,不需預(yù)知待查詢詞的長度,沿著樹鏈逐字匹配即可;基本的機(jī)制結(jié)構(gòu)如圖2(a)所示.1.3整詞二分法和tre索引樹法基于逐字二分法的查詢機(jī)制是對前2種詞典機(jī)制的改進(jìn)方案,一方面,從組織結(jié)構(gòu)上,逐字二分與整詞二分的詞典結(jié)構(gòu)完全一樣;另一方面,逐字二分吸收了TRIE索引樹的查詢優(yōu)勢,即采用的是“逐字匹配”,而不是整詞二分的“全詞匹配”,這在一定程度上提高了匹配的效率,如圖2(b).以上3種基本的詞典機(jī)制是該方向研究中的經(jīng)典機(jī)制,但他們的缺點(diǎn)也十分突出.整詞二分法完全采用全詞匹配的查詢過程,效率明顯較為低下;TRIE索引樹法的構(gòu)造和維護(hù)比較復(fù)雜,而且都是單詞樹枝,浪費(fèi)了一定的空間;而逐字二分法由于采用的仍是整詞二分的詞典結(jié)構(gòu),雖然采用了較為高效的匹配方法,但并沒有改進(jìn)“整詞二分”的數(shù)據(jù)結(jié)構(gòu),使得匹配過程并不是完全意義上的逐字匹配,這使效率的提高受到很大的局限.各種新的詞典查詢機(jī)制應(yīng)運(yùn)而生,下面來介紹其中幾種有代表性的機(jī)制.2一些新的詞典機(jī)制2.1基于前2個(gè)字的詞典機(jī)制文獻(xiàn)提出了基于雙字哈希機(jī)制的詞典查詢方法,該方法主要根據(jù)漢語中雙字詞語較多的特點(diǎn),基于TRIE索引數(shù)的詞典機(jī)制做出了改進(jìn),采用前2個(gè)字逐個(gè)哈希索引、剩余字串有序排列的結(jié)構(gòu),查詢過程采用逐字匹配的方法,這相當(dāng)于使2字詞以下的短語用TRIE索引樹機(jī)制實(shí)現(xiàn),3字詞以上的長詞的剩余部分用線性表組織,從而避免了深度搜索,在不提升已有典型詞典機(jī)制維護(hù)復(fù)雜度的情況下,提高分詞速度.圖3為該機(jī)制的正向?qū)崿F(xiàn)圖.2.2基于位串的方法文獻(xiàn)提出了基于PATRICIAtree的漢字詞典查詢機(jī)制,PATRICIAtree本質(zhì)上是一種壓縮的二叉查詢樹,它將關(guān)鍵詞作為二進(jìn)制位串記錄在樹的結(jié)構(gòu)中,從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每一條路徑都代表一個(gè)關(guān)鍵詞位串.在文獻(xiàn)中,作者利用詞條的內(nèi)碼來作為一個(gè)關(guān)鍵詞位串,然后通過位串比較構(gòu)造出PATRICIAtree,樹的每個(gè)內(nèi)部節(jié)點(diǎn)包括3個(gè)數(shù)據(jù)項(xiàng):比較位、左指針、右指針,樹的葉子節(jié)點(diǎn)代表一個(gè)詞條.查詢時(shí)根據(jù)內(nèi)部節(jié)點(diǎn)選擇后繼路徑,直到葉子節(jié)點(diǎn).該方法的優(yōu)點(diǎn)是引入了位比較,只需要進(jìn)行為數(shù)不多的位比較和幾次字符串比較,就能完成各種查詢和更新功能.2.3e樹的改進(jìn)方法文獻(xiàn)提出了一種基于雙數(shù)組Trie(double-arraytrie)的數(shù)據(jù)結(jié)構(gòu),Trie樹本質(zhì)上是搜索樹的一種,是一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)(DFA),每個(gè)節(jié)點(diǎn)代表自動(dòng)機(jī)的一個(gè)狀態(tài),根據(jù)變量的不同,進(jìn)行狀態(tài)轉(zhuǎn)移,當(dāng)?shù)竭_(dá)結(jié)束狀態(tài)或者無法轉(zhuǎn)移的時(shí)候,完成查詢.文獻(xiàn)使用文獻(xiàn)中對傳統(tǒng)的Trie進(jìn)行的改進(jìn)方法,用2個(gè)線性數(shù)組來進(jìn)行Trie樹的表示,即雙數(shù)組Trie.2.4數(shù)碼序列到數(shù)偶碼的轉(zhuǎn)換文獻(xiàn)還提出了一種雙編碼機(jī)制,其基本思想是將GB-2312編碼中的6768個(gè)常用漢字唯一的映射到1～6768間的一個(gè)序列碼,從而每個(gè)漢字串都可以唯一地映射到一個(gè)數(shù)字串,這樣將對于詞語的查詢轉(zhuǎn)化為基于數(shù)字串的查詢.雙編碼中還要將數(shù)碼序列轉(zhuǎn)換為數(shù)偶碼表,排好序,供檢索用.雙編碼機(jī)制的第1步是從數(shù)碼序列到數(shù)偶碼的轉(zhuǎn)換,這種轉(zhuǎn)換主要采用歐幾里德算法(輾轉(zhuǎn)相除法)的思想,保證了從數(shù)碼序列和數(shù)偶碼之間轉(zhuǎn)換的唯一性;同時(shí)還達(dá)到了一定程度上數(shù)據(jù)壓縮的目的.第2步需要建立索引機(jī)制,對整個(gè)詞典進(jìn)行編碼,這樣每個(gè)詞語就對應(yīng)一對數(shù)偶碼,由于隨著詞語的長度增加,數(shù)值會(huì)變得很大,所以必須建立相應(yīng)索引.2.5哈希機(jī)制的優(yōu)勢雙字哈希機(jī)制是一種比較簡潔的機(jī)制,作為對TRIE索引樹的改進(jìn),在構(gòu)造和維護(hù)上比前者簡單,但它對于中文分詞速度的提升并不明顯.原因一是在逐字匹配方法上它并不比TRIE索引樹有太多的改進(jìn),二是在于文獻(xiàn)中使用的java.util.Hashtable內(nèi)置哈希算法也不是一個(gè)非常高效的算法.基于PATRICIAtree的自動(dòng)分詞機(jī)制在速度上是一種較具有優(yōu)勢的算法,但因?yàn)闃涞臉?gòu)造完全基于內(nèi)碼而非字,所以不可避免地導(dǎo)致樹的深度大大增加,從而造成了效率降低和空間的浪費(fèi).基于雙數(shù)組Trie的機(jī)制的算法效率很高,但也存在一個(gè)致命弱點(diǎn):在構(gòu)造調(diào)整的過程中,每個(gè)狀態(tài)都依賴于其他狀態(tài),所以在詞典需要進(jìn)行刪減或增加的時(shí)候,需要對雙數(shù)組進(jìn)行全局的調(diào)整,靈活性很差,這也明顯不符合實(shí)際使用的需要.雙編碼機(jī)制的詞典查詢算法,優(yōu)勢在于避免了傳統(tǒng)查詢中的字符串操作,在哈希機(jī)制上更加靈活;同時(shí)詞典的組織方式是線性表,調(diào)整方便.但文獻(xiàn)中使用的算法壓縮率不夠大,導(dǎo)致了大數(shù)組的產(chǎn)生,限制了查詢效率的提高.從上面的分析看出,現(xiàn)有的諸多基于詞典的分詞機(jī)制都存在著諸多問題,文本結(jié)合上述方法的優(yōu)缺點(diǎn)提出了一種新的中文分詞詞典機(jī)制.3基于雙詞語-長詞的中文分詞詞典機(jī)制對以上若干參考文獻(xiàn)的分析容易發(fā)現(xiàn),詞典法快速查詢方法中,分詞速度較高的機(jī)制往往需要消耗更多的內(nèi)存資源.在計(jì)算機(jī)性能得到極大提高的情況下,可以承受快速分詞機(jī)制對資源的占用,但如果內(nèi)存占用過大,也會(huì)影響算法的實(shí)際應(yīng)用能力.本文中,作者提出了一種基于雙字詞-長詞的中文分詞詞典機(jī)制(DCLVHI).該機(jī)制不通過無限制占用內(nèi)存,而主要依賴于減少詞匯切分所需的平均匹配次數(shù)來提高分詞效率.表1介紹了本文對中文詞匯的簡單分類.3.1雙漢字前2個(gè)字的詞匯結(jié)構(gòu)在漢字詞匯中,雙字組成的詞匯占了大部分,對常用詞典(人民日報(bào))的統(tǒng)計(jì)發(fā)現(xiàn),在108783個(gè)詞匯中,51%為2字詞,31%為3字詞,13%為4字詞,3%左右為單字詞,多于4字以上的詞匯只占2%左右.而在對中文文本的權(quán)威統(tǒng)計(jì)中,雙字詞占有的比例更是高達(dá)70%以上,正是因?yàn)榭吹搅穗p字詞的作用,文獻(xiàn)提出了雙字哈希機(jī)制.在本文提出的新機(jī)制中,為了進(jìn)一步體現(xiàn)雙字詞的重要性,直接針對雙字詞或多字詞的前2個(gè)字建立Hash索引,這樣進(jìn)一步突出了雙字詞的作用,而將多字詞的剩余字串建立了專門的長詞表,長詞表也是一個(gè)Hash索引.也就是說,在詞典的結(jié)構(gòu)化過程時(shí),無論該詞匯為雙字詞、3字詞或其他多字詞,均首先將該詞匯首2字直接建立Hash表.而純粹的單字詞(非其他任何詞匯的前綴),在該詞典詞匯結(jié)構(gòu)中不占用空間.具體詞典結(jié)構(gòu)可以參見圖4.3.2實(shí)驗(yàn)2:網(wǎng)絡(luò)結(jié)構(gòu)的構(gòu)建本節(jié)著重介紹圖4表現(xiàn)的機(jī)制具體構(gòu)成,DCLVHI機(jī)制主要由2個(gè)主要部分構(gòu)成:首詞Hash索引和長詞Hash索引.其中前者又包括了2項(xiàng)內(nèi)容:(1)標(biāo)志位(2bytes):詞的標(biāo)志位,一般認(rèn)為的漢字詞匯不會(huì)超過16個(gè)字,選取2個(gè)字節(jié),16bit作為該詞的標(biāo)志位,i比特位設(shè)置為1,則表示為該雙字詞可以是一個(gè)長度為i+1的長詞.如圖4,圖集是一個(gè)雙字詞,它不能作為其他詞的前綴,那么該詞標(biāo)志位值為0000000000000010,表示其只能是一個(gè)2字詞.再如電老,它本身不是詞,但可以作為3字詞的前綴,它的標(biāo)志位就是0000000000000100,而春夏秋冬,春夏單獨(dú)可以作為一個(gè)詞,但也可以作為春夏秋冬這個(gè)4字詞的前綴,于是它的標(biāo)志位就是0000000000001010,其他詞匯的標(biāo)志位值同理可得.(2)字符串指針(4bytes):指向詞匯在內(nèi)存中的位置,將詞庫的所有詞匯放入到一段連續(xù)空間中,指向每個(gè)詞匯的指針保存在該項(xiàng)中.長詞Hash索引的結(jié)構(gòu)與首詞索引類似,但只包括了1項(xiàng)內(nèi)容.即字符串指針(4bytes)指向詞匯在內(nèi)存中的位置.最后一部分是字符串存儲部分,詞庫中的所有詞匯均放入一段連續(xù)的存儲空間,中間使用‘＼0’作為間隔.以上描述的詞典結(jié)構(gòu)的構(gòu)建過程均使用程序自動(dòng)實(shí)現(xiàn),具有較好的查詢效率,是一種適合正向最大匹配分詞的詞典構(gòu)造方法,且不用預(yù)知待查詞的長度.3.3算法的有效性檢驗(yàn)假設(shè)查詢一無意義字符串“君子蘭圖籍是個(gè)電老虎,春夏都敢作敢為”.查詢步驟如下:(1)從首詞Hash索引中,通過Hash定位得到以“君子”開頭的索引項(xiàng),發(fā)現(xiàn)該索引項(xiàng)對應(yīng)的比特位為“0x0006”,說明可以為2字詞也可以為3字詞.(2)指針移到“蘭”上,計(jì)算“君子蘭”Hash索引,發(fā)現(xiàn)它的確是一個(gè)3字詞,匹配成功.(3)指針指向“圖籍”,通過Hash定位得到“圖籍”的索引項(xiàng),發(fā)現(xiàn)該索引項(xiàng)的比特位是“0x0002”,只可能是2字詞.一次匹配成功.(4)“是個(gè)”,這種情況也會(huì)存在,2個(gè)單字組成的詞,在Hash索引中可能定位到的索引處沒有值,那么直接將“是”作為單字返回.如果發(fā)現(xiàn)索引處有值(Hash算法可能會(huì)碰撞),需要再進(jìn)行比較.在Hash算法的設(shè)計(jì)時(shí),方案會(huì)盡量減少這種碰撞的機(jī)會(huì).(5)“春夏”,既可以是2字詞也可能是4字詞前綴,根據(jù)最大匹配法的原則,先匹配“春夏都敢”,查找長詞表后,發(fā)現(xiàn)它不存在,返回結(jié)果“春夏”為匹配成功的2字詞.剩余文本的處理也可參照上面的方法進(jìn)行.4效率指標(biāo)比較中文分詞機(jī)制的評價(jià)指標(biāo)有詞匯召回率、準(zhǔn)確率、分詞速度等.本文主要比較采用以上各類不同詞典構(gòu)造方法,造成的分詞速度差異.同時(shí)將各詞典構(gòu)造方法所需的系統(tǒng)內(nèi)存也作為效率指標(biāo)進(jìn)行比較.下文中分別比較以下指標(biāo):(1)內(nèi)存使用量,只有內(nèi)存在允許的范圍內(nèi),分詞機(jī)制才具有可行性;(2)機(jī)制的平均詞匯查詢次數(shù),即切割單個(gè)詞匯的平均查詢次數(shù);(3)對于指定文本的查詢時(shí)間實(shí)驗(yàn).4.1基于tricortg的教育應(yīng)用詞典查詢算法占用內(nèi)存可以作為查詢機(jī)制效率的重要指標(biāo).分詞機(jī)制下的基本內(nèi)存消耗有如下4項(xiàng):(1)詞表占用空間574560bytes,SL=108000*(2*0.03+4*0.50+8*0.13+12*0.03)=574560bytes;(2)首字散列表每單元8bytes,共7500個(gè)單元左右,Fchi=7500*8=60000bytes;(3)詞索引表每個(gè)詞占4bytes,共108000個(gè)詞,Wit=108000*4=432000bytes;(4)TRIE索引數(shù)每個(gè)TRIE索引數(shù)結(jié)點(diǎn)單元占8bytes,Th=130000*8=1040000bytes.整詞二分和逐字二分的機(jī)制包括(1)、(2)、(3)項(xiàng)開銷:Ssbw=SL+Fchi+Wit=1066560bytes;(1)Ssbc=SL+Fchi+Wit=1066560bytes;(2)基于TRIE索引的包括(2)、(4)項(xiàng)開銷:STrie=Fchi+Th=1100000bytes;(3)PATRICIAtree方法的開銷約為SPr=2*10*108000=2160000bytes;(4)雙字哈希算法的開銷約為SDchi≈1800000bytes;(5)雙數(shù)組算法的開銷約為SDaTrie=113*108000+108000*2.4*3*4=15314000bytes;(6)雙編碼機(jī)制的開銷約為SDC=113*108000+3342430=15546430bytes;(7)本文中設(shè)計(jì)的新機(jī)制的內(nèi)存消耗包括以下幾個(gè)部分:(1)首詞Hash表:使用2種不同的Hash算法,可以得到2種不同的內(nèi)存消耗.(a)非壓縮算法索引數(shù)IN=C23500=3500(3500?1)2=6123250(2500ΙΝ=C35002=3500(3500-1)2=6123250(2500個(gè)常用單詞和1000個(gè)次常用單詞)標(biāo)志位的長度Fb=2bytes;詞指針的長度Wp=4bytes;消耗內(nèi)存S1a=IN*(Fb+Wp)=36739500bytes;(b)壓縮算法索引數(shù)IN=3*108000*0.5=162000bytes;(系數(shù)3是一個(gè)通用比例)消耗內(nèi)存S1b=IN*(Fb+Wp)=1944000bytes;(2)長詞表索引長詞表索引數(shù)LIN=108000*0.4=43200;長詞指針長度Lwp=4bytes;消耗內(nèi)存S2=LIN*Lwp=172800bytes;(3)詞庫SL=574560bytes;新機(jī)制2種方式下的內(nèi)存消耗分別為:SDCLVHIa=S1a+S2+SL=37486860bytes,(8)SDCLVHIb=S1b+S2+SL=1719360bytes.(9)從圖5可以看出,不采用壓縮算法的機(jī)制SDCLVHIa需要占用較大的內(nèi)存容量,而采用壓縮算法的新機(jī)制SDCLVHIb在內(nèi)容消耗上與其他算法相差不大.4.2實(shí)際文本匹配和數(shù)據(jù)來源詞匯平均查詢次數(shù)是反映分詞機(jī)制效率的重要指標(biāo).一般認(rèn)為,詞匯平均查詢次數(shù)越少,該機(jī)制可能分詞效率越高.在表1的基礎(chǔ)上,主要選取5類代表詞匯,其中包括單字詞、無前綴雙字詞和3類N字詞(如表2).理論分析新機(jī)制與上文提及的幾種典型詞典改進(jìn)算法的平均查詢次數(shù).從理論分析比較可以看出,在文本匹配的主要情況下,DCLVHI所需要的查詢次數(shù)都更少,具有優(yōu)勢.當(dāng)然在所查詞匯很短,而其2字詞根作為很多不同長度詞前綴的情況下,DCHI可能具有優(yōu)勢.但此種情況需要前綴級數(shù)超過3級,在常用詞庫中極少出現(xiàn).通過各類實(shí)驗(yàn)顯示的實(shí)際文本詞匯出現(xiàn)規(guī)律,也表明這種情況造成的效率損失有限.作者進(jìn)行了較大規(guī)模的統(tǒng)計(jì)實(shí)驗(yàn)以證明上面的理論估計(jì),實(shí)驗(yàn)所用數(shù)據(jù)來自1999年和2000年的TDT測試中使用的簡體中文數(shù)據(jù),由LDC提供.選取其中最大的中文文本集(13233篇)作為測試數(shù)據(jù),進(jìn)行了下面幾個(gè)方面的統(tǒng)計(jì).(1)相同詞匯的計(jì)算在這13233篇文章中一共出現(xiàn)了1530000個(gè)詞匯(同一篇文章中出現(xiàn)相同詞匯僅計(jì)算為1次,不同文章中出現(xiàn)的相同詞匯計(jì)算為2次),其中出現(xiàn)26156個(gè)雙字詞679229次,占44.39%;出現(xiàn)3298個(gè)單字詞共665479次,占43.50%;10084個(gè)3字詞共118765次,占7.76%;4895個(gè)4字詞共34997次,占2.29%;另有31530次4字以上詞,占出現(xiàn)次數(shù)的2.06%.(2)雙漢字雙音節(jié)詞,雙給詞數(shù)字13233篇文章中一共出現(xiàn)了3671294次詞匯(出現(xiàn)一次就計(jì)算為1次),其中雙字詞1814756次,占49.43%;單字詞1423971次,占38.78%;3字詞285293次,占7.78%;4字詞70980次,占1.93%;4字以上詞76294次,占2.08%.(3)作為3.和4.4個(gè).在出現(xiàn)的26156個(gè)雙字詞中,其中非前綴雙字詞有18345個(gè),作為3字詞前綴的是6801個(gè),作為4字詞前綴的是1281個(gè),4字詞以上前綴的有328個(gè);同時(shí)作為3字詞/4字詞以上前綴的599個(gè),僅占所有出現(xiàn)詞匯種類的2.29%.(4)dcsi機(jī)制下的查線結(jié)果非前綴雙字詞出現(xiàn)1488093次,3字詞前綴出現(xiàn)242136次,4字詞前綴出現(xiàn)52492次,4字詞以上前綴出現(xiàn)32035次.在該文本數(shù)據(jù)集下,利用DCLVHI機(jī)制,平均每個(gè)詞匯的查找輪數(shù)為1.25次,而如果采用DCHI的查找輪數(shù)是2.34次.4.3實(shí)驗(yàn)數(shù)據(jù)集和效率測試結(jié)果參照文獻(xiàn),本文采用了3類不同類型的查詢時(shí)間測試:(1)對選用詞典的所有詞遍