在分詞系統(tǒng)中常用的分詞詞典機(jī)制有:(1)基于整詞二分;(2)基于TRIE索引樹;(3)基于逐字二分.
一、基于整詞二分的分詞詞典機(jī)制
這是一種廣為使用的分詞詞典機(jī)制.其結(jié)構(gòu)通常分為三級，前兩級為索引，如圖3.1聽示。
圖 3.1 基于整詞二分的分詞詞典機(jī)制
1.首字散列表
詞首字散列函數(shù)根據(jù)漢字的國標(biāo)區(qū)位碼給出。通過一次Hash運(yùn)算即可直接定位漢字在首字散列表中的序號。也就是將詞首字的國標(biāo)碼與其在首字散列表中的序號相對應(yīng)。我國的GB2312-80標(biāo)注規(guī)定漢語字符的交換碼由兩個ASCII碼構(gòu)成：第一個是區(qū)碼，取值從OxA1到OxF7，共87個區(qū)，第二個是位碼，從OxA1到0xFE，共94位。區(qū)碼為OxA1到0xAE的存儲全角符號，如標(biāo)點、字母等。GB2312-80漢字的編碼空間是BOA1-FIFE，共有72 * 94 = 6768個碼位，實有6763個漢字，其中一級漢字3755個，接著是5個空位，后面是3008個二級漢字。設(shè)id是詞首字在首字散列表中的序號，c1和c2是詞首字的區(qū)碼和位碼，利用Hash方法求Id則有:
Id = (c1–176) * 94 + (c2 - 161) (3-1)
這種Hash方法實質(zhì)上是一種一一映射。
首字散列表的一個單元包括兩項內(nèi)容：
1) 入口項 數(shù)(4字節(jié))：以該字為首字的詞的個數(shù)。
2) 第一入口項指針(4字節(jié))：指向第一入口項在詞索引表中的位置。
2.詞索引表
因為詞的長度可變(實際系統(tǒng)中還包括附屬于該詞的各類信息)，故以選擇不定長存儲為宜，此外必須實現(xiàn)對詞的隨機(jī)訪問，這兩條決定了必須建立詞索引表。詞索引表的一個單元僅含一項內(nèi)容：
1) 詞典正文指針(4字節(jié))：指向詞在詞典正文中的位置。
3.詞典正文
以詞為單位的有序表，詞典中的同一首字的詞條按升序排列，通過詞索引表和詞典正文的配合，很容易實現(xiàn)指定詞在詞典正文中的整詞二分快速查找。
在整詞二分查詢?nèi)我庖粋€漢字串W[1…n], W[1]表示該字串首字，W[n]表示首字后面的 n個漢字，查詢的過程為：
1) 根據(jù)首字散列表得到W[1]入口項指針和以它為首字的詞在詞索引表中所占的范圍。
2) 根據(jù) 1)中得到的范圍在詞典正文中對漢字串W[n]進(jìn)行二分查找。如果查詢成功則W [l…n]為分詞詞典中的一個詞.
整詞二分法查詢的基本原理很簡單，但是每次查詢都只能對漢字串W[l…n]是否為一個詞進(jìn)行判斷，它不能從查詢的中間過程中發(fā)現(xiàn)漢字串W[1…n]中所有可能包括的詞。而且它查詢的范圍較大，總是在以W[1]為首字的所有詞表范圍內(nèi)。而我們在分詞過程中，需要得到一個漢字串S中所有可能切分出的詞，也就是說要找出S中所有以W[1]為首字的詞，如果用整詞二分法來查詢的話就需要進(jìn)行多次的試探，即每改變一次待查字串W[1…n]的n值就要對詞典進(jìn)行一次查詢，而且每次的查詢過程都要在以W[1]為首字的所有詞表范圍內(nèi).因此整詞二分法的查詢效率不高.
二、基于TRIE索引樹的分詞詞典機(jī)制
TRIE索引樹是一種以樹的多重鏈表形式表示的鍵樹。
基于TRIE樹的分詞詞典由兩部分組成，如圖3.2所示。
圖 3.2 基于TRIE索引樹的分詞詞典機(jī)制
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[1]TRIE索引樹，沿相應(yīng)指針移動至目標(biāo)結(jié)點NODE，i = 2。
2) 在NODE的關(guān)鍵字域中對漢字W[i]進(jìn)行二分查找。
如果與NODE的第 j 個單元的關(guān)鍵字匹配成功則沿該單元的子樹指針移至目標(biāo)結(jié)點，并令該結(jié)點為新的NODE，i = i + 1，否則 查找失敗，退出此過程。
3) 重做 2)，直到 NODE為 葉子結(jié)點。
4) 如果 到達(dá)葉于結(jié)點時i>n，則
查詢成功，W [l…n]為分詞詞典中的一個詞，否則查詢失敗。
與整詞二分的分詞詞典機(jī)制形成鮮明對照的是：基于TRIE索引樹的分詞詞典機(jī)制每次僅僅只比較一個漢字，不需預(yù)知待查詢詞的長度，且在對漢字串S的一遍掃描過程中，就能得到所有可能切分的詞。這種由短詞及長詞的確定性工作方式避免了整詞二分的分詞詞典機(jī)制不必要的多次試探性查詢。由于TRIE索引樹已蘊(yùn)含了詞條信息，因此詞典中不必再顯式地羅列詞條，可直接存儲詞的附屬信息（葉子指針直接指向這些信息)。
TRIE索引樹分詞詞典機(jī)制的主要缺點是其構(gòu)造及維護(hù)比整詞二分復(fù)雜。
基于TRIE索引樹的另外一種構(gòu)造方式就是：所有字都采用Hash散列的方式。其結(jié)構(gòu)與圖3.2 基本相同，不同的是其入口項個數(shù)要么為0 要么就是整個漢字字庫的大小。這種方式在查詢上有顯著的效率提升，因為不需要執(zhí)行二分查找，但是由于中文漢字?jǐn)?shù)量巨大，同時也造成了大量空間的浪費(fèi)。
三、基于逐字二分的分詞詞典機(jī)制
基于逐字二分的分詞詞典是針對整詞二分和TRIE索引樹的不足而設(shè)計的一種分詞詞典。逐字二分分詞詞典與整詞二分分詞詞典在數(shù)據(jù)結(jié)構(gòu)上相同，因此其構(gòu)造比TRIE索引樹簡單。從查詢方式來看，逐字二分不再將整個詞作為關(guān)鍵字進(jìn)行比較，而是類似TRIE索引樹的情形，每次僅僅比較單個的漢字。因而其效果同TRIE索引樹一樣，不需預(yù)知待查詢詞的長度，且在對漢字串S的一遍掃描過程中，就能得到查詢串中所有可能切分的詞。
基于逐字二分分詞詞典，如圖3.3所示。
