基于隱馬爾可夫模型的分詞算法的設(shè)計(jì)與實(shí)現(xiàn)

◆林游龍

（福州數(shù)據(jù)技術(shù)研究院有限公司 福建 350019）

1 研究背景

漢語的自動(dòng)分詞問題是計(jì)算機(jī)處理漢語時(shí)面臨的基礎(chǔ)性工作，是諸多應(yīng)用系統(tǒng)不可或缺的重要環(huán)節(jié)[1-3]?；谝?guī)則的切分算法[4-5]又叫做機(jī)械分詞方法，它是按照一定的策略將待分析的漢字串與一個(gè)“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串。常用方法：最小匹配算法，正向（逆向）最大匹配法，逐字匹配算法，神經(jīng)網(wǎng)絡(luò)法、聯(lián)想回溯法，基于N-最短路徑分詞算法。目前機(jī)械式分詞占主流地位的是正向最大匹配法和逆向最大匹配法?；诶斫獾姆衷~方法[6-7]又稱之為知識(shí)分詞，知識(shí)分詞是一種理想的分詞方法。不管是基于理解的切分方法，還是基于統(tǒng)計(jì)的或基于規(guī)則的切分方法，每一種方法都有各自的優(yōu)點(diǎn)和一定的局限性[8-9]。

目前基于統(tǒng)計(jì)的分詞方法是研究的熱點(diǎn)，主要包括，最大熵模型，條件隨機(jī)場(chǎng)，隱馬模型，最大熵隱馬模型。為了彌補(bǔ)條件隨機(jī)場(chǎng)與最大熵模型的缺點(diǎn)，出現(xiàn)了基于多層次混合模型，如最大熵隱馬爾可夫模型，其原理是通過一種模型進(jìn)行粗切分，然后用另一種模型進(jìn)行細(xì)切分[10-12]。目前的基于隱馬爾可夫模型的分詞工具很少，復(fù)雜的代碼結(jié)構(gòu)限制了它的普及。本文針對(duì)隱馬爾可夫模型的特點(diǎn)與中文分詞相結(jié)合，設(shè)計(jì)并實(shí)現(xiàn)了基于隱馬爾可夫模型的分詞算法，總代碼不超過70行，而且簡(jiǎn)單易理解，對(duì)以后基于此模型的詞法分析研究有很大的參考價(jià)值。

2 傳統(tǒng)的方法

2.1 背景

因?yàn)橄惹蟹趾髽?biāo)注的方法雖然簡(jiǎn)單，效率較高，但是這種方法的詞語切分與詞語標(biāo)注是相互獨(dú)立的關(guān)系，而實(shí)際上詞語與詞性是密不可分的關(guān)系，一個(gè)詞語有特定的若干個(gè)與之對(duì)應(yīng)的詞性。因此實(shí)現(xiàn)分詞與詞性標(biāo)注同時(shí)進(jìn)行的方法比單純的使用分詞方法的正確率要高。

又因?yàn)槭褂枚Z法進(jìn)行自動(dòng)分詞的主要問題是，詞與詞的轉(zhuǎn)移概率矩陣非常龐大。自動(dòng)分詞的詞表一般都在4萬詞以上，轉(zhuǎn)移概率矩陣規(guī)模就有16億以上。即使假定概率大于0的詞對(duì)只占4%，也將有6400萬個(gè)數(shù)據(jù)[2]；訓(xùn)練所需的語料規(guī)模非常巨大，因此往往為了降低概率矩陣的規(guī)模，僅用一元語法來求詞串的概率。使得分詞的正確率受到了影響[1-2]。受到基于類的分詞方法的啟發(fā)，如果用詞性來代替類，則以上方法可以看作有基于詞性類的分詞方法，由于自動(dòng)分詞的詞性一般在80個(gè)左右，轉(zhuǎn)移概率矩陣的規(guī)模就在6400個(gè)，假定概率大于0的詞性對(duì)為占100%，6400個(gè)數(shù)據(jù)的規(guī)模所需的訓(xùn)練語料規(guī)模，計(jì)算復(fù)雜度等都非常的小[1-2]。這也就是隱馬爾可夫模型的分詞算法的思想[13]。

2.2 隱馬爾可夫模型概述

如圖1所示，一個(gè)隨機(jī)過程的變量不是并不是相互獨(dú)立的，每個(gè)隨機(jī)變量的值依賴于這個(gè)序列前面的狀態(tài)。隨著時(shí)間的推移，該系統(tǒng)將從某一狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)。該過程就稱為馬爾可夫模型。但這限制了模型的適應(yīng)性。如果不知道模型所經(jīng)過的狀態(tài)序列，只知道狀態(tài)的概率函數(shù)，也就是說，觀察到的事件是狀態(tài)的隨機(jī)函數(shù)，因此，該模型是一個(gè)雙重的隨機(jī)過程。其中，模型的狀態(tài)轉(zhuǎn)換過程是不可觀察的，即隱蔽的。如圖1所示。一個(gè)HMM記為一個(gè)五元組（S，K，A，B，π），其中，S為狀態(tài)的集合，K為輸出符合的集合，π，A和B分別是初始狀態(tài)的概率分布、狀態(tài)轉(zhuǎn)移概率和符號(hào)發(fā)射概率[14-16]。

圖1 隱馬爾可夫模型

2.3 背景隱馬爾可夫模型分詞理論

本文將基于詞性的二元統(tǒng)計(jì)模型的分詞與詞性標(biāo)注一體化模型視為隱馬爾可夫模型。將詞性視為隱馬爾可夫模型中的狀態(tài)，將分詞前的候選詞視為隱馬爾可夫模型中的觀察值。如圖2所示：

圖2 中文分詞隱馬爾可夫模型

假設(shè)句子S是由單詞串組成，W=w1w2…wc（c≥1），單詞wi（1≤i≤n）的詞性標(biāo)注為ti，即句子S相應(yīng)的詞性標(biāo)注符號(hào)序列可表達(dá)為T=t1t2…tn。那么，分詞與詞性標(biāo)注的任務(wù)就是要在S所對(duì)應(yīng)的各種切分和標(biāo)注形式中，尋找T和W的聯(lián)合概率P（W,T）為最優(yōu)的詞切分和標(biāo)注組合。

根據(jù)隱馬爾可夫的思想，即應(yīng)用隱馬爾可夫鏈來描述一個(gè)完整句子的詞性變化，每種詞性對(duì)應(yīng)一種狀態(tài)，狀態(tài)的轉(zhuǎn)移概率代表詞性之間的搭配關(guān)系。這樣，在生成一個(gè)句子時(shí)，系統(tǒng)不斷地由一個(gè)狀態(tài)轉(zhuǎn)移到另外一個(gè)狀態(tài)，每一個(gè)狀態(tài)產(chǎn)生一個(gè)輸出符號(hào)-單詞，直至整個(gè)句子輸出完畢[1-3]。

P（W,T）可以由HMM近似地表示為等式（1）：

其中，P（W|T）可以稱為生成模型，P（wi|ti）表示在整個(gè)標(biāo)注語料中在詞性ti的條件下，單詞wi出現(xiàn)的概率；P（T）為基于詞性的語言模型，采用二元語法，P（ti|ti-1）表示在前一個(gè)單詞的詞性是ti-1的情況下，當(dāng)前詞的詞性是ti的概率。當(dāng)i=1時(shí)，取P（ti|ti-1）=P（ti）。

因此，在分詞過程中，只要列出所有可能的切分，用單詞出現(xiàn)的概率與詞性的連接概率，計(jì)算每種切分概率總和，概率指最大的一個(gè)即為輸出結(jié)果[1-3]。

2.4 隱馬爾可夫模型分詞例子

假設(shè)有一中文句子”他說的確實(shí)在理”需要?jiǎng)澐?，如圖3所示。詞性如表1所示，這個(gè)句子有三種意思：

圖3 中文分詞例子

表1 詞性的符號(hào)表示

1、他 說 的 確實(shí) 在理

2、他 說 的確 實(shí)在 理

3、他 說 的確 實(shí) 在理

2.5 隱馬爾可夫模型分詞算法的參數(shù)估計(jì)

為了獲取P（wi|ti）及P（ti|ti-1），事先用大規(guī)模的已切分和標(biāo)注了詞性的漢語語料做訓(xùn)練，計(jì)算單詞的頻度信息，統(tǒng)計(jì)每個(gè)詞的不同詞性出現(xiàn)的次數(shù)C（wi，ti）及每種詞性ti在文本中出現(xiàn)過的總次數(shù)C（ti），用最大似然估計(jì)算法計(jì)算得等式（2）：

同理，統(tǒng)計(jì)訓(xùn)練文本中前后詞性組合的頻度C（ti-1，ti）及C（ti-1），用最大似然估計(jì)算法計(jì)算得等式（3），假設(shè)等式（4）成立，則得到等式（5），同時(shí)易知等式（6）成立：

如果把P（ti+1|ti）看作詞性的轉(zhuǎn)移概率，則可以使用動(dòng)態(tài)規(guī)劃算法來求P（W，T）。因?yàn)槿绻F盡所有可能的狀態(tài)序列，那么設(shè)具有N個(gè)不同的狀態(tài)，時(shí)間長(zhǎng)度為T，那么有NT個(gè)可能的狀態(tài)序列。相反如果每一狀態(tài)能夠記錄前面所有輸出符號(hào)的概率，即等式（6），那么時(shí)間復(fù)雜度變?yōu)镺（N2T），這種方法即稱為動(dòng)態(tài)規(guī)劃[1-3]。

3 系統(tǒng)設(shè)計(jì)

3.1 數(shù)據(jù)結(jié)構(gòu)

如圖4所示，（a）為候選單詞的數(shù)據(jù)結(jié)構(gòu)[3]，本文使用候選字符串中的偏移整數(shù)量offset與length表示一個(gè)候選單詞。tag表示詞性，goodprev表示最佳前趨詞，它也是一個(gè)candidate數(shù)據(jù)結(jié)構(gòu)。fee表示概率，sumfee表示目前為到候選單詞為止的概率的總和。（b）為字典設(shè)計(jì)，freq代表頻率即訓(xùn)練集中出現(xiàn)的個(gè)數(shù)。

圖4 候選單詞結(jié)構(gòu)與字典

3.2 函數(shù)設(shè)計(jì)

3.2.1 取候選單詞

設(shè)此函數(shù)為gettmpwords（str）[3]：即從需要未分詞的字符串str中找出候選單詞。其中str是需要切分的漢語字符串，函數(shù)的返回值為候選單詞列表，如圖5所示：

圖5 取候選單詞函數(shù)

其中函數(shù)getdicfreq函數(shù)表示從字典中取相應(yīng)的單詞對(duì)應(yīng)的頻率。

3.2.2 取最佳前趨詞

設(shè)此函數(shù)為getprev（i，list）[3]：填寫第i個(gè)候選詞的最佳前趨詞的序號(hào)，并且計(jì)算到第i個(gè)候選詞為止，路徑上的最小累計(jì)費(fèi)用。其中i是候選單詞列表list中的序號(hào)，list為候選單詞列表。如圖6所示。

圖6 取最佳前趨詞函數(shù)

3.2.3 分詞函數(shù)設(shè)計(jì)

設(shè)此函數(shù)為str_fengchi（str）[3]：將漢語字符串str分詞，其中str是需要切分的漢語字符串，函數(shù)返回值為已切分好字符串str的字符串，如圖7所示。

圖7 分詞函數(shù)

4 實(shí)驗(yàn)驗(yàn)證

訓(xùn)練數(shù)據(jù)：北京大學(xué)開發(fā)的免費(fèi)版PFR人民日?qǐng)?bào)切分標(biāo)注語料庫（1998年1月數(shù)據(jù)）[17]。

測(cè)試數(shù)據(jù)：第二屆國際中文分詞評(píng)測(cè)（SigHan 2005）的語料庫，msr_test，pku_test[18]。由于其他的基于隱馬爾可夫模型的分詞工具如TnT，Citar等需要標(biāo)記訓(xùn)練集，而且標(biāo)記的方法不是以詞性為標(biāo)準(zhǔn)如詞頭、詞尾、詞中等，而本文所使用的隱馬爾可夫分詞工具實(shí)現(xiàn)的是基于標(biāo)準(zhǔn)詞性集的標(biāo)記方法，因此不能與TnT以及Citar做比較。得到的實(shí)驗(yàn)結(jié)果如表2所示。

表2 實(shí)驗(yàn)結(jié)果

根據(jù)實(shí)驗(yàn)結(jié)果可知，本文設(shè)計(jì)的隱馬爾可夫模型的分詞算法達(dá)到了實(shí)用的水平。

5 結(jié)束語

本文設(shè)計(jì)的隱馬爾可夫模型算法不僅用于分詞領(lǐng)域，還可以用到其他詞法分析領(lǐng)域，如未登錄詞發(fā)現(xiàn)，人名、地名識(shí)別，詞性標(biāo)注等其他可用隱馬爾可夫模型的地方。今后需改進(jìn)模型參數(shù)的存儲(chǔ)方式，使用雙數(shù)組Trie等存儲(chǔ)模型參數(shù)以提高程序的處理速度。另外研究基于三語法模型的分詞與詞性標(biāo)注一體化方法，解決搜索空間問題。