3/3中文分詞詞典構(gòu)造簡(jiǎn)述中文分詞詞典構(gòu)造簡(jiǎn)述

在分詞系統(tǒng)中常用的分詞詞典機(jī)制有:(1)基于整詞二分;(2)基于TRIE索引樹(shù);(3)基于逐字二分.

一、基于整詞二分的分詞詞典機(jī)制

這是一種廣為使用的分詞詞典機(jī)制.其結(jié)構(gòu)通常分為三級(jí)，前兩級(jí)為索引，如圖3.1聽(tīng)示。

圖3.1基于整詞二分的分詞詞典機(jī)制

1.首字散列表

詞首字散列函數(shù)根據(jù)漢字的國(guó)標(biāo)區(qū)位碼給出。通過(guò)一次Hash運(yùn)算即可直接定位漢字在首字散列表中的序號(hào)。也就是將詞首字的國(guó)標(biāo)碼與其在首字散列表中的序號(hào)相對(duì)應(yīng)。我國(guó)的GB2312-80標(biāo)注規(guī)定漢語(yǔ)字符的交換碼由兩個(gè)ASCII碼構(gòu)成：第一個(gè)是區(qū)碼，取值從OxA1到OxF7，共87個(gè)區(qū)，第二個(gè)是位碼，從OxA1到0xFE，共94位。區(qū)碼為OxA1到0xAE的存儲(chǔ)全角符號(hào)，如標(biāo)點(diǎn)、字母等。GB2312-80漢字的編碼空間是BOA1-FIFE，共有72*94=6768個(gè)碼位，實(shí)有6763個(gè)漢字，其中一級(jí)漢字3755個(gè)，接著是5個(gè)空位，后面是3008個(gè)二級(jí)漢字。設(shè)id是詞首字在首字散列表中的序號(hào)，c1和c2是詞首字的區(qū)碼和位碼，利用Hash方

法求Id則有:

Id=(c1–176)*94+(c2-161)

(3-1)

這種Hash方法實(shí)質(zhì)上是一種一一映射。

首字散列表的一個(gè)單元包括兩項(xiàng)內(nèi)容：

1)入口項(xiàng)數(shù)(4字節(jié))：以該字為首字的詞的個(gè)數(shù)。

2)第一入口項(xiàng)指針(4字節(jié))：指向第一入口項(xiàng)在詞索引表中的位置。

2.詞索引表

因?yàn)樵~的長(zhǎng)度可變(實(shí)際系統(tǒng)中還包括附屬于該詞的各類(lèi)信息)，故以選擇不定長(zhǎng)存儲(chǔ)為宜，此外必須實(shí)現(xiàn)對(duì)詞的隨機(jī)訪(fǎng)問(wèn)，這兩條決定了必須建立詞索引表。詞索引表的一個(gè)單元僅含一項(xiàng)內(nèi)容：

1)詞典正文指針(4字節(jié))：指向詞在詞典正文中的位置。

3.詞典正文

以詞為單位的有序表，詞典中的同一首字的詞條按升序排列，通過(guò)詞索引表和詞典正文的配合，很容易實(shí)現(xiàn)指定詞在詞典正文中的整詞二分快速查找。

在整詞二分查詢(xún)?nèi)我庖粋€(gè)漢字串W[1…n],W[1]表示該字串

首字，W[n]表示首字后面的n個(gè)漢字，查詢(xún)的過(guò)程為：

1)根據(jù)首字散列表得到W[1]入口項(xiàng)指針和以它為首字的詞

在詞索引表中所占的范圍。

2)根據(jù)1)中得到的范圍在詞典正文中對(duì)漢字串W[n]進(jìn)行

二分查找。如果查詢(xún)成功則W[l…n]為分詞詞典中的一個(gè)詞.整詞二分法查詢(xún)的基本原理很簡(jiǎn)單，但是每次查詢(xún)都只能對(duì)漢字串W[l…n]是否為一個(gè)詞進(jìn)行判斷，它不能從查詢(xún)的中

間過(guò)程中發(fā)現(xiàn)漢字串W[1…n]中所有可能包括的詞。而且它查詢(xún)的范圍較大，總是在以W[1]為首字的所有詞表范圍內(nèi)。而我們?cè)诜衷~過(guò)程中，需要得到一個(gè)漢字串S中所有可能切分出的詞，也就是說(shuō)要找出S中所有以W[1]為首字的詞，

如果用整詞二分法來(lái)查詢(xún)的話(huà)就需要進(jìn)行多次的試探，即每改變一次待查字串W[1…n]的n值就要對(duì)詞典進(jìn)行一次查詢(xún)，而且每次的查詢(xún)過(guò)程都要在以W[1]為首字的所有詞表范圍內(nèi).因此整詞二分法的查詢(xún)效率不高.

二、基于TRIE索引樹(shù)的分詞詞典機(jī)制

TRIE索引樹(shù)是一種以樹(shù)的多重鏈表形式表示的鍵樹(shù)。

基于TRIE樹(shù)的分詞詞典由兩部分組成，如圖3.2所示。

圖3.2基于TRIE索引樹(shù)的分詞詞典機(jī)制

1.首字散列表

同基于整詞二分的分詞詞典機(jī)制。首字散列表的一個(gè)單元是所對(duì)應(yīng)漢字的TRIE索引樹(shù)的根結(jié)點(diǎn).

2.TRIE索引樹(shù)結(jié)點(diǎn)

TRIE索引樹(shù)結(jié)點(diǎn)是以下述結(jié)構(gòu)為單元的，按關(guān)鍵字排序的數(shù)組：

關(guān)鍵字(2字節(jié))：?jiǎn)我粷h字。

子樹(shù)大小(2字節(jié))：以從根結(jié)點(diǎn)到當(dāng)前單元的關(guān)鍵字組成的子串為前緩的詞的個(gè)數(shù)。

子樹(shù)指針(4字節(jié))：子樹(shù)大小非0時(shí)，指針指向子樹(shù)，否則指向葉子。

在TRIE索引樹(shù)上查詢(xún)?nèi)我庖粋€(gè)詞W[1…n]的過(guò)程為：

1)根據(jù)首字散列表得到W[1]TRIE索引樹(shù)，沿相應(yīng)指針移動(dòng)至目標(biāo)結(jié)點(diǎn)NODE，i=2。

2)在NODE的關(guān)鍵字域中對(duì)漢字W[i]進(jìn)行二分查找。

如果與NODE的第j個(gè)單元的關(guān)鍵字匹配成功則沿該單元的子樹(shù)指針移至目標(biāo)結(jié)點(diǎn)，并令該結(jié)點(diǎn)為新的NODE，i=i+1，否則查找失敗，退出此過(guò)程。

3)重做2)，直到NODE為葉子結(jié)點(diǎn)。

4)如果到達(dá)葉于結(jié)點(diǎn)時(shí)in，則

查詢(xún)成功，W[l…n]為分詞詞典中的一個(gè)詞，否則查詢(xún)失敗。

與整詞二分的分詞詞典機(jī)制形成鮮明對(duì)照的是：基于TRIE

索引樹(shù)的分詞詞典機(jī)制每次僅僅只比較一個(gè)漢字，不需預(yù)知待查詢(xún)?cè)~的長(zhǎng)度，且在對(duì)漢字串S的一遍掃描過(guò)程中，就能得到所有可能切分的詞。這種由短詞及長(zhǎng)詞的確定性工作方式避免了整詞二分的分詞詞典機(jī)制不必要的多次試探性查詢(xún)。由于TRIE索引樹(shù)已蘊(yùn)含了詞條信息，因此詞典中不必再顯式地羅列詞條，可直接存儲(chǔ)詞的附屬信息（葉子指針直接指向這些信息)。

TRIE索引樹(shù)分詞詞典機(jī)制的主要缺點(diǎn)是其構(gòu)造及維護(hù)比整

詞二分復(fù)雜。

基于TRIE索引樹(shù)的另外一種構(gòu)造方式就是：所有字都采用Hash散列的方式。其結(jié)構(gòu)與圖3.2基本相同，不同的是其

入口項(xiàng)個(gè)數(shù)要么為0要么就是整個(gè)漢字字庫(kù)的大小。這種方式在查詢(xún)上有顯著的效率提升，因?yàn)椴恍枰獔?zhí)行二分查找，但是由于中文漢字?jǐn)?shù)量巨大，同時(shí)也造成了大量空間的浪費(fèi)。

三、基于逐字二分的分詞詞典機(jī)制

基于逐字二分的分詞詞典是針對(duì)整詞二分和TRIE索引樹(shù)的不足而設(shè)計(jì)的一種分詞詞典。逐字二分分詞詞典與整詞二分分詞詞典在數(shù)據(jù)結(jié)構(gòu)上相同，因此其構(gòu)造比TRIE索引樹(shù)簡(jiǎn)

單。從查詢(xún)方式來(lái)看，逐字二