基于隱馬爾可夫模型的分詞算法的設計與實現

◆林游龍

（福州數據技術研究院有限公司 福建 350019）

1 研究背景

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

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

2 傳統的方法

2.1 背景

因為先切分后標注的方法雖然簡單，效率較高，但是這種方法的詞語切分與詞語標注是相互獨立的關系，而實際上詞語與詞性是密不可分的關系，一個詞語有特定的若干個與之對應的詞性。因此實現分詞與詞性標注同時進行的方法比單純的使用分詞方法的正確率要高。

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

2.2 隱馬爾可夫模型概述

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

圖1 隱馬爾可夫模型

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

本文將基于詞性的二元統計模型的分詞與詞性標注一體化模型視為隱馬爾可夫模型。將詞性視為隱馬爾可夫模型中的狀態，將分詞前的候選詞視為隱馬爾可夫模型中的觀察值。如圖2所示：

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

假設句子S是由單詞串組成，W=w1w2…wc（c≥1），單詞wi（1≤i≤n）的詞性標注為ti，即句子S相應的詞性標注符號序列可表達為T=t1t2…tn。那么，分詞與詞性標注的任務就是要在S所對應的各種切分和標注形式中，尋找T和W的聯合概率P（W,T）為最優的詞切分和標注組合。

根據隱馬爾可夫的思想，即應用隱馬爾可夫鏈來描述一個完整句子的詞性變化，每種詞性對應一種狀態，狀態的轉移概率代表詞性之間的搭配關系。這樣，在生成一個句子時，系統不斷地由一個狀態轉移到另外一個狀態，每一個狀態產生一個輸出符號-單詞，直至整個句子輸出完畢[1-3]。

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

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

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

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

假設有一中文句子”他說的確實在理”需要劃分，如圖3所示。詞性如表1所示，這個句子有三種意思：

圖3 中文分詞例子

表1 詞性的符號表示

1、他 說 的 確實 在理

2、他 說 的確 實在 理

3、他 說 的確 實 在理

2.5 隱馬爾可夫模型分詞算法的參數估計

為了獲取P（wi|ti）及P（ti|ti-1），事先用大規模的已切分和標注了詞性的漢語語料做訓練，計算單詞的頻度信息，統計每個詞的不同詞性出現的次數C（wi，ti）及每種詞性ti在文本中出現過的總次數C（ti），用最大似然估計算法計算得等式（2）：

同理，統計訓練文本中前后詞性組合的頻度C（ti-1，ti）及C（ti-1），用最大似然估計算法計算得等式（3），假設等式（4）成立，則得到等式（5），同時易知等式（6）成立：

如果把P（ti+1|ti）看作詞性的轉移概率，則可以使用動態規劃算法來求P（W，T）。因為如果窮盡所有可能的狀態序列，那么設具有N個不同的狀態，時間長度為T，那么有NT個可能的狀態序列。相反如果每一狀態能夠記錄前面所有輸出符號的概率，即等式（6），那么時間復雜度變為O（N2T），這種方法即稱為動態規劃[1-3]。

3 系統設計

3.1 數據結構

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

圖4 候選單詞結構與字典

3.2 函數設計

3.2.1 取候選單詞

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

圖5 取候選單詞函數

其中函數getdicfreq函數表示從字典中取相應的單詞對應的頻率。

3.2.2 取最佳前趨詞

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

圖6 取最佳前趨詞函數

3.2.3 分詞函數設計

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

圖7 分詞函數

4 實驗驗證

訓練數據：北京大學開發的免費版PFR人民日報切分標注語料庫（1998年1月數據）[17]。

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

表2 實驗結果

根據實驗結果可知，本文設計的隱馬爾可夫模型的分詞算法達到了實用的水平。

5 結束語

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