漢語自動分詞系統(tǒng)中分詞詞典的查詢速度

漢語自動分詞系統(tǒng)中分詞詞典的查詢速度

一、分詞詞典查詢方式及查詢過程分詞詞典是漢語自動分詞系統(tǒng)的基本組成部分。自動分詞系統(tǒng)所需要的各類信息知識都要從分詞詞典中獲取分詞詞典的查詢速度直接影響到分詞系統(tǒng)的速度而現(xiàn)實應(yīng)用(如因特網(wǎng)上的中文文本檢索、漢字與漢語語音識別系統(tǒng)的后處理以及中文文語轉(zhuǎn)換系統(tǒng)的前處理等)均對分詞速度提出了迫切要求,因此建立高效快速的分詞詞典機(jī)制勢在必行。針對分詞系統(tǒng)的特點,可以將分詞詞典的查詢操作大致分為三種基本方式:查詢方式1:在分詞詞典中查找指定詞w0(詞在分詞詞典中的定位)這是一種最基本的查詢方式。給定詞w0,返回w0在分詞詞典中的位置,以便得到w0的各類附屬信息。此時w0是確定的,所以可以簡單地通過二分查找給出結(jié)果。查詢方式2:根據(jù)分詞詞典,在漢字串S中查找從某一指定位置i開始的最長詞wi,max(對應(yīng)最大匹配分詞法)有別于查詢方式1,這里最長詞wi,max無法預(yù)知,需要在查詢過程中動態(tài)地確定。通常的做法是嘗試始于位置i的所有可能長度的詞,多次運用查詢方式1來完成查詢。查詢方式3:根據(jù)分詞詞典,在漢字串S中查找從某一指定位置i開始的所有的詞wi,1,wi,2,…,wi,max(對應(yīng)全切分分詞法)類似查詢方式2,但返回結(jié)果通常不唯一。本文設(shè)計并通過實驗考察了三種典型的分詞詞典機(jī)制:(1)基于整詞二分(2)基于TRIE索引樹及(3)基于逐字二分,著重比較了它們的時間、空間效率。二、分詞詞典機(jī)制實驗利用了一個包含112967個不同詞的分詞詞典THDic。THDic中最短詞只有一個漢字(單字詞),最長詞則達(dá)到17個漢字(長詞多為成語、慣用語、習(xí)用語等),平均詞長度約2.5個漢字。2.1基于整詞二分的分詞詞典機(jī)制這是一種廣為使用的分詞詞典機(jī)制。其結(jié)構(gòu)通常分為三級,前兩級為索引(見圖1)。1.直接定位漢字在首字散熱中的序詞首字散列函數(shù)根據(jù)漢字的國標(biāo)區(qū)位碼給出。通過一次哈希運算即可直接定位漢字在首字散列表中的序號。首字散列表的一個單元包括兩項內(nèi)容:入口項個數(shù)(4字節(jié)):以該字為首字的詞的個數(shù);第一入口項指針(4字節(jié)):指向第一入口項在詞索引表中的位置。2.隨機(jī)訪問因詞的長度可變實際系統(tǒng)中還包括附屬于該詞的各類信息故以選擇不定長存儲為宜此外必須實現(xiàn)對詞的隨機(jī)訪問。這兩條決定了必須建立詞索引表。詞索引表的一個單元僅含一項內(nèi)容:詞典正文指針(4字節(jié)):指向詞在詞典正文中的位置。3.基于tre索引樹的分詞詞典機(jī)制以詞為單位的有序表。通過詞索引表和詞典正文的配合,很容易實現(xiàn)指定詞在詞典正文中的整詞二分快速查找。此種分詞詞典機(jī)制比較適合于查詢方式1。而在查詢方式2、3中,對任一位置i,通常我們不得不預(yù)先主觀設(shè)定一個詞的可能最長長度l(一般l取詞典中最長詞的長度。THDic為17個字),然后截取子漢字串S[i,i+l-1]作為假想詞,在詞典中進(jìn)行整詞二分查找。不成功則詞長l遞次減一并循環(huán),直至匹配成功。由于一、二、三、四字詞分別占THDic的3.6%、64.0%、16.0%、14.0%,它們更動態(tài)覆蓋了真實文本絕大部分,因此這種由長詞及短詞的盲目嘗試方法效率很低。[例]查詢S“水怪大白天現(xiàn)形一個多小時這個令人驚異的消息不徑而走?！敝袕摹按蟆弊珠_始的最長的詞。(1)取從“大”字開頭最長可能的漢字串:wi,max=“大白天現(xiàn)形一個多小時這個令人驚異的”(詞典中最長詞為17個漢字);(2)用整詞二分法在詞典中查找候選詞wi,max,失敗;(3)去掉wi,max最后一個字,重復(fù)步驟(2),失敗;(5)經(jīng)過14次的錯誤嘗試,wi,max最終消減到“大白天”,查找成功,于是返回wi,max=“大白天”。2.2基于TRIE索引樹的分詞詞典機(jī)制TRIE索引樹是一種以樹的多重鏈表形式表示的鍵樹。面向英文的TRIE索引樹一般以26個字母作為關(guān)鍵字,樹結(jié)點包含個數(shù)相同的指針。漢字接近7000個,如果采用同樣的策略構(gòu)造中文詞典,顯然將造成指針的大量浪費。面向中文的TRIE索引樹的結(jié)點應(yīng)允許指針個數(shù)變化?；赥RIE樹的分詞詞典由兩部分組成(見圖2)。1.首字散列表同基于整詞二分的分詞詞典機(jī)制。首字散列表的一個單元是所對應(yīng)漢字的TRIE索引樹的根結(jié)點。2.TRIE索引樹結(jié)點TRIE索引樹結(jié)點是以下述結(jié)構(gòu)為單元的、按關(guān)鍵字排序的數(shù)組:關(guān)鍵字(2字節(jié)):單一漢字;子樹大小(2字節(jié)):以從根結(jié)點到當(dāng)前單元的關(guān)鍵字組成的子串為前綴的詞的個數(shù);子樹指針(4字節(jié)):子樹大小非0時,指針指向子樹;否則指向葉子。在TRIE索引樹上查詢?nèi)我庖粋€詞W[1,n]的過程為:(1)根據(jù)首字散列表得到W的TRIE索引樹,沿相應(yīng)指針移動至目標(biāo)結(jié)點NODEx;i=2;(2)在NODEx的關(guān)鍵字域中對漢字W[i]進(jìn)行二分查找。如果與的第個單元的關(guān)鍵字匹配成功,則沿該單元的子樹指針移至目標(biāo)結(jié)點,并令該結(jié)點為新的NODEx;否則查詢失敗,退出此過程。(3)重做(2),直至NODEx為葉子結(jié)點。(4)如果抵達(dá)葉子結(jié)點時i>n,則查詢成功,W[1,n]為分詞詞典中的一個詞與整詞二分形成鮮明對照的是,基于TRIE索引樹的分詞詞典機(jī)制每次僅比較一個漢字,不需預(yù)知待查詢詞的長度,且在對漢字串S的一遍掃描過程中,就能得到查詢方式2、3的結(jié)果。這種由短詞及長詞的確定性工作方式避免了整詞二分分詞詞典機(jī)制中不必要的多次試探性查詢。由于TRIE索引樹已蘊(yùn)涵了詞條信息,因此詞典中不必再顯式地羅列詞條,可直接存儲詞的附屬信息(葉子指針直接指向這些信息)。[例]查詢S“水怪大白天現(xiàn)形一個多小時這個令人驚異的消息不徑而走。”中從“大”字開始的最長詞(及所有詞)。(1)首先通過首字散列表得到以“大”字開頭的詞的TRIE索引樹結(jié)點T;(2)由于結(jié)點T中包含關(guān)鍵字“”(表示空字符,下文同),因此“大”是一個詞。在結(jié)點T中用二分法查找關(guān)鍵字“白”,其指針指向的目標(biāo)結(jié)點設(shè)為T1。(3)結(jié)點T1中包含關(guān)鍵字“”,因此“大白”也是一個詞。在結(jié)點T1中繼續(xù)用二分法查找關(guān)鍵字“天”,此時“天”的目標(biāo)結(jié)點已是葉子結(jié)點,“大白天”也是一個詞,查詢結(jié)束。最后得到“大白天”為最長詞,中間過程識別的“大”、“大白”、“大白天”均為從“大”字開始的詞。TRIE索引樹分詞詞典機(jī)制的主要缺點是其構(gòu)造及維護(hù)比整詞二分復(fù)雜。2.3基于逐字二分的分詞詞典機(jī)制針對整詞二分和TRIE索引樹的不足,這里設(shè)計了一種改進(jìn)方案———基于逐字二分的分詞詞典機(jī)制(見圖3)。逐字二分與整詞二分在數(shù)據(jù)結(jié)構(gòu)上完全一致,不同的僅僅在于查詢過程:不再將整個詞作為關(guān)鍵字進(jìn)行比較,而是類似TRIE索引樹的情形,每次僅僅比較單個的漢字。因而其效果同TRIE索引樹完全一樣。[例]查詢S“水怪大白天現(xiàn)形一個多小時這個令人驚異的消息不徑而走。”中從“大”字開始的最長詞(及所有詞)。(1)通過首字散列表可知:以“大”字開頭的詞位于詞索引表的第14285～第15078項范圍內(nèi),并且其中的頭一項“大”為一個單字詞;(2)通過二分法在第14285～第15078項的范圍內(nèi)查找第二個字為“白”的詞,可知:以“大白”開頭的詞位于詞索引表的第14292～第14297項范圍內(nèi),并且其中的頭一項“大白”為一個二字詞;(3)通過二分法在第14292～第14297項的范圍內(nèi)查找第三個字為“天”的詞,可知:以“大白天”開頭的詞位于詞索引表的第14296～第14297項范圍內(nèi),并且其中的頭一項“大白天”為一個三字詞;(4)通過二分法在第14296～第14297項的范圍內(nèi)查找第四個字為“現(xiàn)”的詞,此范圍為空,查詢結(jié)束。最后得到“大白天”為最長詞,中間過程識別的“大”、“大白”、“大白天”均為從“大”字開始的詞。三、單詞詞典機(jī)制的實驗比較我們從時間和空間角度對第二節(jié)所述的分詞詞典機(jī)制進(jìn)行了實驗比較:1.分詞詞典的類型(1)詞表(僅含詞條,不計詞條所含的各類信息):占用空間782678字節(jié);(2)首字散列表:每個單元占8字節(jié),共7614個單元(包括一、二級漢字及某些圖形符號故首字散列表占空間字節(jié)(3)詞索引表:每個詞占4字節(jié),共112967個詞,故詞索引表占空間112967*4=451868字節(jié);(4)TRIE索引樹:每個TRIE索引樹結(jié)點單元占8字節(jié),共含129588個索引項,故TRIE索引樹占空間129588*8=1036704字節(jié)?；谡~二分和逐字二分的分詞詞典機(jī)制包括(1)、(2)、(3)項開銷。而基于TRIE索引樹的分詞詞典機(jī)制包括項(2)、(4)項開銷。2.實驗結(jié)果和結(jié)論對每種分詞詞典機(jī)制,我們均設(shè)計了四個不同類型的測試:(1)對THDic的所有詞依次查詢1次。(第一類查詢);(2)對THDic的所有詞依次查詢,查詢次數(shù)與詞頻成正比。(第一類查詢,模擬真實文本環(huán)境);(3)從語料庫中任意取一段測試文本,用最大匹配分詞法切分該文本。(第二類查詢);(4)從語料庫中任意取一段測試文本,用全切分分詞法切分該文本。(第三類查詢)。針對(3)(4),我們從《人民日報》中隨機(jī)選取了長度為3066K字節(jié)的文本作為測試文本。則關(guān)于空間、時間的實驗結(jié)果總匯如下:從實驗結(jié)果來看,三種分詞詞典機(jī)制的空間效率差不多。而基于TRIE索引樹和逐字二分的分詞詞典機(jī)制的時間效率大致相同,較基于整詞二分的詞典機(jī)制均有大幅度的改善。由于基