陳 倩 樂(lè)紅兵

（江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 無(wú)錫 214122）

1 引言

分詞是中文語(yǔ)言處理的基礎(chǔ)性工作。近年來(lái)，中文分詞經(jīng)歷了很大的發(fā)展。將分詞看作序列標(biāo)記問(wèn)題是比較普遍的方法［1］，序列標(biāo)記的目標(biāo)是給序列中所有元素分配標(biāo)簽，包括最大熵和條件隨機(jī)場(chǎng)等監(jiān)督學(xué)習(xí)算法［2］。但是語(yǔ)言搭配是隨著時(shí)間不斷變化的，陳舊的語(yǔ)料訓(xùn)練出的基于統(tǒng)計(jì)的分詞方法難以駕馭人們?nèi)找娓碌恼Z(yǔ)言習(xí)慣，且人工進(jìn)行語(yǔ)料庫(kù)更新是十分巨大繁瑣的工作，國(guó)內(nèi)沒(méi)有能夠獲取并持續(xù)更新的語(yǔ)料庫(kù)，這是基于統(tǒng)計(jì)學(xué)習(xí)的分詞方法所遇到的阻礙［3］。

在現(xiàn)實(shí)生活中需要切分的語(yǔ)料是多種多樣的，并不是所有待切分語(yǔ)料都具有上下文信息，一些需要處理的語(yǔ)料往往以單個(gè)句子的形式出現(xiàn)并要求切分。例如在網(wǎng)絡(luò)上查詢信息時(shí)輸入的文本、網(wǎng)上聊天和電子郵件中輸入的單句、問(wèn)答系統(tǒng)種用戶輸入的句子等都沒(méi)有上下文信息［3］。由此可見(jiàn)基于上下文信息進(jìn)行分詞方法具有局限性。在基于詞典的分詞方法中，未登錄詞造成的分詞精度降低和容易產(chǎn)生歧義是它的缺陷所在，因此未登陸詞識(shí)別和歧義處理是衡量基于詞典的分詞系統(tǒng)優(yōu)劣的重要標(biāo)準(zhǔn)。

針對(duì)分詞算法的詞典構(gòu)造方法，目前形成了成熟的詞典加載結(jié)構(gòu)。如：整詞二分法、Trie 索引樹、逐字二分法。根據(jù)文獻(xiàn)［4］，三種詞典機(jī)制的空間大小排序，Trie 索引＞整詞二分=逐字二分；時(shí)間大小排序，Trie索引樹＞逐字二分＞整詞二分。分詞詞典是劃分出每個(gè)詞的重要依據(jù)，因此分詞詞典的構(gòu)造至關(guān)重要，它無(wú)需通過(guò)語(yǔ)料庫(kù)的訓(xùn)練，計(jì)算量小，原理簡(jiǎn)單且易于實(shí)現(xiàn)。

宗中等［5］依據(jù)雙字詞占比重較高，單字和多字不常用的特點(diǎn)，提出了雙字Hash 詞典機(jī)制。僅對(duì)詞語(yǔ)的前兩個(gè)字順次建立Hash 索引，構(gòu)成了深度只為2 的Trie 子樹，詞的剩余部分構(gòu)成詞組作為詞典正文，從而避免了枝干過(guò)長(zhǎng)，大大提高了詞組查詢速度。分詞速度得到提升，由于沒(méi)有歧義方面的處理，分詞準(zhǔn)確率提高不大。

李江波等［6］提出了雙數(shù)組Trie 思想。首先把所有GB2312 中的基本漢字的順序碼轉(zhuǎn)化成1-6768 的順序碼，然后將所有的順序碼作為初始狀態(tài)放入Base 數(shù)組；接下來(lái)將不同詞語(yǔ)的后續(xù)漢字順序放進(jìn)數(shù)組，生成新的狀態(tài)，并對(duì)數(shù)組中初始狀態(tài)的Base 值進(jìn)行調(diào)整，以保證所有后續(xù)漢字能夠放入數(shù)組。雙數(shù)組Trie 改進(jìn)了數(shù)組指針空置的缺陷，實(shí)現(xiàn)在空間占有較少的同時(shí)還要保證查詢的效率。但是雙數(shù)組Trie內(nèi)存消耗大，實(shí)現(xiàn)復(fù)雜。

交集型分詞歧義是自動(dòng)分詞遇到的主要歧義類型。以往所提出的歧義處理方法，常需上下文信息的統(tǒng)計(jì)進(jìn)行辨別歧義，例如使用互信息原理、N元統(tǒng)計(jì)模型，t-測(cè)試原理、HMM 模型、字標(biāo)注統(tǒng)計(jì)等方法或模型進(jìn)行上下文信息統(tǒng)計(jì)以實(shí)現(xiàn)歧義消解，無(wú)法在沒(méi)有上下文信息的情況下進(jìn)行歧義消解，或者上下文信息量少影響歧義消解的質(zhì)量。

文中進(jìn)一步改進(jìn)Trie樹詞典加載機(jī)制，采用雙哈希索引，即首字和次字使用哈希索引，詞的剩余字串則按字典順序組成類似“整詞二分”的詞典正文，最大限度地提高匹配時(shí)間效率。然后運(yùn)用詞頻和詞性信息進(jìn)行交集型歧義處理，該方法使用于對(duì)上下文信息匱乏的語(yǔ)料。

2 雙字Hash詞典機(jī)制

Trie 樹是一種以樹的多重鏈表表示的鍵樹，主要有首字散列表和結(jié)點(diǎn)兩部分組成，在語(yǔ)句切分過(guò)程中只需一次掃描，無(wú)需知道待分詞的長(zhǎng)度，沿著樹鏈逐字匹配進(jìn)行分詞，避免了整詞二分的詞典機(jī)制中不必要的多次試探性查詢。Tire 樹進(jìn)行詞典加載一般采用哈希算法，把任意長(zhǎng)度的輸入通過(guò)散列算法，變換成固定長(zhǎng)度的輸入，該輸出就是散列值，這種轉(zhuǎn)換就是一種壓縮映射。哈希算法的基礎(chǔ)是哈希表的建立，散列表（哈希表）是根據(jù)關(guān)鍵碼值直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映射到哈希表的同一地址上，從而產(chǎn)生沖突。

與英文不同，目前漢字已經(jīng)超過(guò)8 萬(wàn)字，常用字就有7000多個(gè)，27萬(wàn)個(gè)詞組，如果一條枝干僅代表一個(gè)字，將有27 萬(wàn)個(gè)葉子節(jié)點(diǎn)，Trie 索引樹的廣度擴(kuò)大，浪費(fèi)了一定的存儲(chǔ)空間，并且Trie 樹中一個(gè)關(guān)鍵字關(guān)聯(lián)多個(gè)值導(dǎo)致散列表查找碰撞嚴(yán)重，分詞速度相應(yīng)變慢。

因此，用Trie進(jìn)行中文詞典加載會(huì)產(chǎn)生大量空指針，散列查找也需要額外的時(shí)間，為了最大限度地提高匹配時(shí)間的效率并兼顧空間利用率。本文提出雙字哈希詞典存儲(chǔ)，二字詞以下的短語(yǔ)使用Trie 索引樹機(jī)制實(shí)現(xiàn)，三字詞以上的長(zhǎng)詞的剩余部分用線性表組織，逐詞匹配三字詞以上的長(zhǎng)詞的剩余字符串，從而避免了深度搜索，一定程度上優(yōu)化了查詢性能，提高了分詞的速度。雖然與莫建文［4］等提出的雙字哈希結(jié)構(gòu)相似，但是本文對(duì)詞典正文進(jìn)行了最大長(zhǎng)度、詞性、使用頻率字段的擴(kuò)充，提高了分詞歧義判斷的準(zhǔn)確性。

根據(jù)權(quán)威統(tǒng)計(jì)，雙字詞語(yǔ)所占比例很大，使用頻率也很高，多（四字以上）字詞語(yǔ)占比例很小，使用頻率較低。漢語(yǔ)各字詞條的詞頻統(tǒng)計(jì)如表1 所示：兩字詞的詞頻占了一半以上，而五字以上的詞的出現(xiàn)概率就非常小，使用頻率低。

表1 不同字長(zhǎng)的頻率比

結(jié)合中文字的編碼體系和中文詞的分布以及哈希索引結(jié)構(gòu)的詞典查詢速度快的優(yōu)點(diǎn)，本文設(shè)計(jì)了一個(gè)基于雙字哈希的三層索引詞典結(jié)構(gòu)基本結(jié)構(gòu)如下：

1）首字哈希表（Hashmap 存儲(chǔ)）：全部中文字符的區(qū)位碼的哈希值，哈希值的大小由小到大依次排列，由首字哈希表值可以直接找到對(duì)應(yīng)的首字地址。

漢字在計(jì)算機(jī)中以內(nèi)碼形式存在，將內(nèi)碼計(jì)算后轉(zhuǎn)為區(qū)位碼，再將區(qū)位碼轉(zhuǎn)換為一個(gè)十進(jìn)制的數(shù)字，這個(gè)數(shù)字就是該漢字在哈希表中的序號(hào)。該序號(hào)指示了以該字為首字的詞長(zhǎng)表的入口地址，根據(jù)Hash函數(shù)入口地址的計(jì)算，如式（1）所示：

其中，Offset 為該字在哈希表中的序號(hào)，ch1，ch2分別為該字機(jī)內(nèi)碼的高字節(jié)和低字節(jié)。

2）次字哈希表

采用除留余數(shù)法的散列函數(shù)處理次字哈希索引。

次字哈希函數(shù)為

其中，Offset 為該字在哈希表中的序號(hào)，ch1，ch2 分別為該字機(jī)內(nèi)碼的高字節(jié)和低字節(jié)。Length是求模系統(tǒng)，文中對(duì)其長(zhǎng)度進(jìn)行統(tǒng)一分配。

3）詞典正文

詞典正文是由詞中除首次字外剩余部分組成的按內(nèi)碼順序排序的有序表。

4）雙哈希索引樹中的節(jié)點(diǎn)用DictSegment類來(lái)表示。其中，DictSegment類的單元結(jié)構(gòu)如下。

（1）keyChar（4bit）：當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的字符。

（2）nodeState（1bit）：到詞節(jié)點(diǎn)的前綴部分是否為詞，nodestate=1為詞，nodestate=0不為詞。

（3）point（4bit）：獲取下一層存儲(chǔ)結(jié)構(gòu)的容器對(duì)象，null代表葉子節(jié)點(diǎn)，詞組組成結(jié)束。

（4）nMaxLength（4bit）：該首字開始的最長(zhǎng)詞條長(zhǎng)度，一般用于首字。

（5）nWordType：詞條的詞性，一般用于詞典正文。

（6）nFrequenery：詞條使用的頻率，一般用于詞典正文。核心詞典的邏輯結(jié)構(gòu)如表2所示。

表2 部分關(guān)鍵字對(duì)應(yīng)AMCTT結(jié)構(gòu)

雙字hash 索引可以使查詢速度和存儲(chǔ)空間達(dá)到最優(yōu)。如：“啊呀/啊哈/大案要案/大青蟲/大壩/大白鼠/大白天說(shuō)夢(mèng)話”構(gòu)成本文提出的AMCTT 詞典樹如圖1所示。

圖1 雙字哈希索引分詞詞典機(jī)制（正向）

雙字Hash 在查找某一個(gè)詞語(yǔ)時(shí)，首先要進(jìn)行詞語(yǔ)首字的查找，獲得相對(duì)應(yīng)的以次字為首字的最大詞長(zhǎng)，并根據(jù)具體的詞長(zhǎng)獲得次字的Hash 值，進(jìn)而得到次字和剩余字串，從而得到所要查找的詞語(yǔ)。這樣的查找方法可以快速準(zhǔn)確地獲得所查詢的詞語(yǔ)在詞典中的精確位置，減少了不必要的過(guò)程，縮短了查詢?cè)~語(yǔ)的時(shí)間，提高了分詞的效率，在分詞速度上要優(yōu)于基于傳統(tǒng)詞典的中文分詞方法。

3 歧義消解

歧義現(xiàn)象指一種形式對(duì)應(yīng)著兩種或兩種以上的解釋，在人類豐富的自然語(yǔ)言中充斥著大量的歧義現(xiàn)象。漢語(yǔ)由于缺乏嚴(yán)格意義的形態(tài)變化，語(yǔ)法形式和語(yǔ)法意義之間的對(duì)應(yīng)關(guān)系錯(cuò)綜復(fù)雜，因此歧義現(xiàn)象比形態(tài)發(fā)達(dá)的語(yǔ)言更具有普遍性。

使用雙向最大匹配分別對(duì)原始語(yǔ)料進(jìn)行切分。雙向最大匹配是從左到右和從右到左將待分詞文本中的幾個(gè)連續(xù)字符與詞表匹配，如果匹配上，并且保證下一個(gè)掃描不是詞表中的詞或詞的前綴則切分出一個(gè)詞。結(jié)合詞性和詞頻信息，有兩種方法進(jìn)行詞組歧義消解：

1）詞頻消解：由m 個(gè)漢字組成的歧義切分字段C=c1c2...cm有兩種切分結(jié)果W=w1w2...wn和V=v1v2...vk。

則選擇切分結(jié)果W，若

則選擇切分結(jié)果V；其中，frq(w)表示詞w的頻率。

單純使用詞頻信息，沒(méi)有考慮到詞性及詞義信息，更沒(méi)有考慮到不同詞性和詞義之間的概率轉(zhuǎn)移關(guān)系，錯(cuò)誤率高。對(duì)于低頻字不能正確切分。

例：他的確切菜了

錯(cuò)誤切分結(jié)果：他/的/確切/菜/了。所以需要結(jié)合詞性信息共同切分。

2）動(dòng)詞消解：對(duì)于交集型歧義，即對(duì)于字段C=c1c2c3，c1c2∈C，C 為詞表，則稱C 為交集型歧義。對(duì)于這樣的歧義，根據(jù)中文的規(guī)則，如果交集詞的前面的詞在動(dòng)詞詞典中，則直接將該詞切分為c1c2/c3，如果后面的詞在動(dòng)詞詞典中，則將該詞切分為c1/c2c3。

顯然，切為動(dòng)詞，例句正確切分為他/的確/切/菜/了。

4 實(shí)驗(yàn)分析比較

系統(tǒng)環(huán)境是core2 i7、雙核8G 內(nèi)存、win7 64位、jdk 1.7 普通pc 壞境。通用詞典來(lái)自搜狐研發(fā)中心發(fā)布的搜狗實(shí)驗(yàn)室數(shù)據(jù)（http：//www.sogou.com/labs/resource/w.php），其中詞頻和詞性是Sogou 搜索引擎索引到的中文互聯(lián)網(wǎng)語(yǔ)料統(tǒng)計(jì)出的15 萬(wàn)條高頻詞，統(tǒng)計(jì)時(shí)間是2006 年10 月。數(shù)據(jù)格式示例如表3所示。

表3 詞典中數(shù)據(jù)格式示例

4.1 評(píng)價(jià)指標(biāo)說(shuō)明

本文采用準(zhǔn)確率、召回率及F 值作為評(píng)價(jià)指標(biāo)。

準(zhǔn)確率：

其中tp為分析結(jié)果中正確的數(shù)目，fp為分析結(jié)果中錯(cuò)誤的數(shù)據(jù)量。

召回率：

其中tp為分析結(jié)果中正確的數(shù)目，fn為正確的但是沒(méi)有被識(shí)別出的數(shù)目。使用調(diào)和平均值表現(xiàn)出準(zhǔn)確率和召回率的共同效果。

調(diào)和平均值：

4.2 詞典分詞比較

從文件中讀取詞典信息、詞頻和詞性信息及原始語(yǔ)料，放入內(nèi)存中。

測(cè)試1：為使測(cè)評(píng)結(jié)果盡量公平，我們從互聯(lián)網(wǎng)上下載5 篇不同領(lǐng)域的測(cè)試語(yǔ)料作為樣本，平均大小為60KB。

1）本文將所構(gòu)建的詞典機(jī)制（圖中樣本中右面第一個(gè)）與常用的3 種詞典機(jī)制（圖中樣本從左往右依次為：基于整詞二分法的詞典構(gòu)造機(jī)制，基于Trie 索引樹的詞典構(gòu)造機(jī)制和基于逐字二分的詞典構(gòu)造機(jī)制）進(jìn)行比較，采用相同的測(cè)試樣本進(jìn)行中文分詞，具體數(shù)據(jù)如圖2所示。

圖2 不同詞典分詞時(shí)間對(duì)比

通過(guò)不同分詞方法的比較和分詞效率的分析，本文方法的分詞速度相比于其他分詞詞典的速度有了一定的提高。

2）得出的測(cè)試結(jié)果如表4所示。

表4 詞典加載方法數(shù)據(jù)對(duì)比

根據(jù)測(cè)試1、測(cè)試2，使用傳統(tǒng)的基于詞典的正向最大匹配法和反向最大匹配法的測(cè)評(píng)結(jié)果與本文方法進(jìn)行比較：使用改進(jìn)的正向最大匹配分詞算法［9］及中國(guó)科學(xué)院計(jì)算研究所研制的漢語(yǔ)詞法分詞系統(tǒng)ICTCLAS（http：//ictclas.nlpir.org）的分詞結(jié)果進(jìn)行對(duì)比，結(jié)果如表5所示。

表5 匹配方法數(shù)據(jù)對(duì)比

本文大體上解決了由于機(jī)械匹配產(chǎn)生的歧義字段的識(shí)別不足問(wèn)題，可以得出：使用雙字哈希詞典加載，結(jié)合詞頻和詞性進(jìn)行分詞消歧的方法得出的調(diào)和平均數(shù)明顯高于其他方法。

該方法在搜索引擎、自動(dòng)問(wèn)答系統(tǒng)、電子郵件過(guò)濾、信息檢索與信息摘錄、文本分類和自動(dòng)摘要、自然語(yǔ)言理解等需要對(duì)無(wú)上下文信息預(yù)料進(jìn)行切分的實(shí)際運(yùn)用領(lǐng)域中具有較強(qiáng)的實(shí)用性。既能夠不使用上下文信息，又能準(zhǔn)確提取出需要的詞語(yǔ)信息，也不需要各領(lǐng)域的語(yǔ)料作為訓(xùn)練對(duì)象，是一種通用高效的中文分詞方法。

5 結(jié)語(yǔ)

在沒(méi)有上下文信息或許上下文信息匱乏的情況下，顯然不能使用統(tǒng)計(jì)學(xué)知識(shí)進(jìn)行分詞。本文提出用改進(jìn)Trie 樹的雙字Hash 詞典提高分詞速度，再用詞典中記載的詞頻詞性信息進(jìn)行分詞的歧義消解，提高了分詞的準(zhǔn)確率。也存在以下需要改進(jìn)的方面：

1）本文提出的根據(jù)詞頻和詞性的歧義消解只能消解一部分歧義，一些非正式場(chǎng)合沒(méi)有嚴(yán)格根據(jù)構(gòu)詞法使用語(yǔ)句，可能需要運(yùn)用調(diào)節(jié)語(yǔ)序，更換詞語(yǔ)等方法再進(jìn)行歧義消解。

2）缺少上下文，組合型歧義和真歧義沒(méi)有辦法解決。

3）分詞詞典的覆蓋面以及測(cè)試語(yǔ)料的選取對(duì)分詞的結(jié)果有很大影響，所以下一步的研究重點(diǎn)是如何把專業(yè)詞典和未登錄詞典附加到通用詞典中，以此為基礎(chǔ)，在不同領(lǐng)域以及不同大小的語(yǔ)料中進(jìn)行分詞，更加全面地證明本文方法在分詞中的優(yōu)勢(shì)。