基于分詞的分詞詞典機(jī)制

基于分詞的分詞詞典機(jī)制

分詞詞典是漢語(yǔ)自動(dòng)分詞系統(tǒng)的基本組成部分。分詞的速度直接影響到中文信息處理系統(tǒng)(如因特網(wǎng)上的中文文本檢索、漢字與漢語(yǔ)語(yǔ)音識(shí)別系統(tǒng)以及中文文語(yǔ)轉(zhuǎn)換系統(tǒng)等)的速度,這些系統(tǒng)大多處理的是海量的中文信息,迫切需要高速度的分詞。分詞的方法主要分為基于詞典的分詞和無(wú)詞典分詞?；谠~典的分詞,其速度主要取決于分詞詞典、分詞算法及兩者之間的搭配。1現(xiàn)有的分詞詞典引擎1.1查詢?cè)~長(zhǎng)度不確定這是一種廣為使用的分詞詞典機(jī)制,其機(jī)制見(jiàn)文獻(xiàn)。這種詞典結(jié)構(gòu)比較簡(jiǎn)單,便于構(gòu)建和維護(hù)。但其查詢速度很慢,特別是對(duì)于最大匹配分詞算法和全切分分詞算法,這些算法所查詢的詞長(zhǎng)度不確定,需要多次查詢,由于一、二、三、四字詞分別占THDic(一種詞典正文)的3.6%、64.0%、16.0%、14.0%,它們更動(dòng)態(tài)覆蓋了真實(shí)文本絕大部分,因此這種由長(zhǎng)詞及短詞的盲目嘗試方法效率很低;另一個(gè)重要原因是因?yàn)槠渥罱K是通過(guò)整詞比較來(lái)確定詞。就詞典占用的空間來(lái)說(shuō),這種詞典要存儲(chǔ)3個(gè)表:首字散列表、詞索引表和正文詞表,因此占用空間較大。1.2查試詞典的選擇TRIE索引樹(shù)是一種以樹(shù)的多重鏈表形式表示的鍵樹(shù)。其機(jī)制見(jiàn)文獻(xiàn)。這種詞典結(jié)構(gòu)復(fù)雜,難于構(gòu)建和維護(hù)。相對(duì)于整詞二分分詞詞典來(lái)說(shuō),該詞典查詢速度較快且適用于大多數(shù)的分詞算法,因?yàn)椴还艽樵~的長(zhǎng)度是否確定都只需要一遍掃描,但其在查找每一個(gè)字時(shí)仍需要字符串的比較。這種詞典不再需要顯式地存儲(chǔ)詞條,占用空間較小。1.3t系統(tǒng)traft索引樹(shù)查詢方法這種詞典的結(jié)構(gòu)與整詞二分詞典的結(jié)構(gòu)相同,只是在查詢時(shí)采用了TRIE索引樹(shù)的查詢方法,每次只比較單個(gè)漢字,逐步縮小查找范圍。逐字二分詞典采用了整詞二分詞典的數(shù)據(jù)結(jié)構(gòu),因而便于構(gòu)建和維護(hù)。其查詢速度與TRIE索引樹(shù)相當(dāng),占用空間也比較小。1.4基于雙字的回復(fù)性和區(qū)位碼映射雙字哈希詞典根據(jù)漢語(yǔ)雙字詞占多數(shù)的特點(diǎn),設(shè)計(jì)了兩個(gè)Hash表,對(duì)前兩個(gè)字作直接映射,其機(jī)制見(jiàn)文獻(xiàn)。這種詞典結(jié)構(gòu)比較復(fù)雜,難于構(gòu)建和維護(hù)。由于通用詞典(THCADict)中雙字詞占76.42%,這種詞典查詢速度較快,但其對(duì)剩余字串仍是通過(guò)字串比較進(jìn)行查詢,制約了速度;另外,Hash映射是有沖突映射,不如區(qū)位碼映射快;如果改為區(qū)位碼映射則需要事先申明數(shù)組大小,雙字的區(qū)位碼是一個(gè)7614×7614的點(diǎn)陣,這在Java等內(nèi)存要求較高的語(yǔ)言中是不允許的。其空間占用與TRIE索引樹(shù)詞典大致相當(dāng)。2新的分詞詞典2.1詞典的創(chuàng)建效率從詞典的結(jié)構(gòu)上來(lái)看,已有詞典都要構(gòu)建多個(gè)表,大多數(shù)表還是多維數(shù)組,表與表之間有復(fù)雜的指向關(guān)系(如TRIE索引樹(shù)詞典和雙字哈希詞典,即使是相對(duì)簡(jiǎn)單的整詞二分詞典也要構(gòu)建3個(gè)表),當(dāng)增加一個(gè)新詞時(shí)還要對(duì)整個(gè)詞典進(jìn)行重構(gòu)(因?yàn)槎疾捎昧硕植檎曳?需要對(duì)詞進(jìn)行排序),TRIE索引樹(shù)詞典在構(gòu)建時(shí)還需要對(duì)詞典正文進(jìn)行入口項(xiàng)個(gè)數(shù)和子樹(shù)個(gè)數(shù)的統(tǒng)計(jì)。如果能夠用1個(gè)表,甚至是一個(gè)一維數(shù)組來(lái)設(shè)計(jì)詞典那將是非常易于構(gòu)建和維護(hù)的。從詞典的查詢速度上看,已有詞典都是映射與比較相結(jié)合,究其原因是因?yàn)檫M(jìn)行全詞無(wú)沖突映射(逐字無(wú)沖突映射是一樣的)所需的空間太大(以THDic為例:該詞典中最長(zhǎng)詞為17個(gè)字,每個(gè)字的機(jī)內(nèi)碼占16bit,該詞的機(jī)內(nèi)碼占17×16=272bit,轉(zhuǎn)換成十進(jìn)制數(shù)為2276,直接映射需要申明的數(shù)組大小約為7.5×1081),無(wú)法直接實(shí)現(xiàn)。如果空間上滿足要求則是有沖突映射,其Hash算法的設(shè)計(jì)比較困難。一次字串的比較時(shí)間(約24305ns)大約相當(dāng)于39次直接映射(一次約628ns)的時(shí)間,這是制約已有分詞詞典速度的一個(gè)關(guān)鍵原因。從詞典占用的空間上來(lái)看,已有詞典都要存儲(chǔ)所有詞(整詞二分詞典和逐字二分詞典)或所有漢字(TRIE索引樹(shù)詞典和雙字哈希詞典),因?yàn)槿缜拔乃?它們最終需要比較字串。如果全部通過(guò)映射來(lái)成詞,則這部分空間可以省掉。2.2不同狀態(tài)的轉(zhuǎn)移漢語(yǔ)詞典可以轉(zhuǎn)換成一個(gè)自動(dòng)機(jī)。從狀態(tài)0開(kāi)始,依次以詞的每個(gè)字為轉(zhuǎn)移條件進(jìn)行轉(zhuǎn)移到達(dá)終態(tài),只要前態(tài)和轉(zhuǎn)移條件確定,后態(tài)就是唯一的,也就是說(shuō)一個(gè)字串如果經(jīng)過(guò)該自動(dòng)機(jī)轉(zhuǎn)移最后到達(dá)終態(tài)則該字串必定為詞。(圖1)對(duì)于自動(dòng)機(jī)的實(shí)現(xiàn),前人提出了一種用三個(gè)數(shù)組實(shí)現(xiàn)的方法,Aoe.J等人將其改造為了用雙數(shù)組實(shí)現(xiàn),base數(shù)組用下標(biāo)表示當(dāng)前態(tài),存儲(chǔ)的base值作為轉(zhuǎn)移條件的附加條件,完整的轉(zhuǎn)移條件為:base值+轉(zhuǎn)移條件;check數(shù)組在與base數(shù)組相同的位置存放這一態(tài)的前態(tài),用于在構(gòu)建自動(dòng)機(jī)時(shí)檢測(cè)base數(shù)組中的內(nèi)容是否沖突,沖突產(chǎn)生的原因是后態(tài)要存儲(chǔ)的位置已被其它態(tài)占用了,一旦有沖突產(chǎn)生將更新當(dāng)前態(tài)的base值再做嘗試直到找到無(wú)沖突的base值。這種方法在構(gòu)建漢語(yǔ)詞典的時(shí)候有困難,漢字有7614個(gè),即轉(zhuǎn)移條件有7614個(gè),這樣在構(gòu)建自動(dòng)機(jī)的時(shí)候?qū)a(chǎn)生非常多的沖突,很難找到適合的base值,除非將數(shù)組申明得很大,而且這種擴(kuò)大還是雙倍的擴(kuò)大,因?yàn)閮蓚€(gè)數(shù)組要一樣大小。另外在詞典構(gòu)建完成之后check數(shù)組就無(wú)用了,浪費(fèi)了一半的空間。將一個(gè)漢字的區(qū)位碼拆分成一個(gè)4位碼,如“阿”字的區(qū)位碼為1602,拆分為4位碼為1、6、0、2。這樣將一次狀態(tài)的轉(zhuǎn)移拆分成了4次狀態(tài)的轉(zhuǎn)移,每次轉(zhuǎn)移的轉(zhuǎn)移條件只有0~9共10個(gè),狀態(tài)拆分后的自動(dòng)機(jī)如圖2。構(gòu)建這樣一個(gè)自動(dòng)機(jī),只需要一個(gè)單維數(shù)組。因?yàn)檗D(zhuǎn)移條件只有10個(gè),可以為每個(gè)前態(tài)預(yù)留10個(gè)后態(tài)的位置,這樣就不會(huì)產(chǎn)生沖突,避免了構(gòu)建時(shí)的盲目嘗試,也省去了二維數(shù)組實(shí)現(xiàn)方法中用于構(gòu)建自動(dòng)機(jī)的check數(shù)組。轉(zhuǎn)移公式為:t=|base[s]|-c,其中t為后態(tài)的地址,s為前態(tài)的地址,c為轉(zhuǎn)移條件。base值的確定也很簡(jiǎn)單:base[x]=basemax+10,其中base[x]為新加入狀態(tài)x的base值,basemax為當(dāng)前已有base值中的最大值。當(dāng)一個(gè)詞構(gòu)建結(jié)束時(shí)將終態(tài)的base值取為負(fù):base[last]=-|base[last]|,取絕對(duì)值是因?yàn)橛行┙K態(tài)在其它詞的路徑之上,已經(jīng)取過(guò)負(fù)了,見(jiàn)圖3。2.3單組分散詞典的實(shí)現(xiàn)2.3.1字典建設(shè)2.3.2字典搜索2.4單組通用映射詞典的性能分析2.4.1措施2:六次映射所結(jié)果如前所示,單數(shù)組全映射分詞詞典結(jié)構(gòu)簡(jiǎn)單,非常容易構(gòu)建,當(dāng)增加一個(gè)新詞時(shí)也不需要重構(gòu)整個(gè)詞典,只給沒(méi)有base值的新?tīng)顟B(tài)賦值即可。就查詢速度來(lái)說(shuō),整個(gè)詞的查詢都是通過(guò)無(wú)沖突映射完成的,即使是最長(zhǎng)的詞(THDic為17個(gè)字,即68次映射)其查詢時(shí)間也僅相當(dāng)于1.7次字串比較時(shí)間;而且當(dāng)字串的某個(gè)狀態(tài)不在詞路徑中時(shí)就可以判斷該字串已不是詞,不需要完整地映射;另外不管詞長(zhǎng)是否確定,都只需要一遍映射,速度非?？?。就詞典占用的空間來(lái)看,詞典不再需要存儲(chǔ)詞和字本身;一個(gè)字會(huì)產(chǎn)生4個(gè)狀態(tài),但其中有許多狀態(tài)是共用的,如圖2中的“阿爸”和“啊哈”就共用了狀態(tài)0、1、2、3,實(shí)驗(yàn)顯示,一個(gè)含有119803個(gè)不同詞(平均詞長(zhǎng)2.5,則含有299507.5個(gè)字)的單數(shù)組全映射分詞詞典僅有526847個(gè)不同狀態(tài),狀態(tài)中分別存儲(chǔ)了10、20、…、5268460、5268470,10占用4個(gè)bit,5268470占用23個(gè)b