MMSEG算法與統(tǒng)計方法結合的中文分詞模型研究

（東莞理工學院城市學院，廣東 東莞 523419）

在信息檢索和數(shù)據(jù)分析等領域存在大量的中文文本數(shù)據(jù)，而使用計算機對這些數(shù)據(jù)進行處理之前都必須進行分詞的處理。分詞需要高效、準確的算法。目前常見的分詞模型有基于機械式的字符串匹配、基于字符串的統(tǒng)計頻率、基于自然語言語法語義的理解等。其中基于規(guī)則的分詞方法如最大匹配法（MM）及其各種變體，因為規(guī)則覆蓋率不高和規(guī)則的主觀性較強，準確率有所不足[1]。常見的基于統(tǒng)計的模型如N-gram、隱馬爾可夫模型（HMM）、最大熵馬爾可夫模型（MEMM）和條件隨機場（CRF）等分詞方法過于依賴訓練語料庫，分詞效率較低，同時在分詞過程中忽視了漢語的句法、語法等信息[2]。結合規(guī)則與統(tǒng)計的方法是中文分詞領域研究的熱點。本文結合規(guī)則和統(tǒng)計分詞算法提出一種改進的分詞模型，該模型將最大匹配算法的一個變體——MMSEG算法[3-4]與統(tǒng)計方法相結合，根據(jù)中文分詞中所遇到的問題，對模型進行逐步優(yōu)化，最終實現(xiàn)分詞方法的時間復雜度降低，以及分詞的召回率（recall）和F-measure指標的提高。

一、分詞算法及其實現(xiàn)

（一）MMSEG分詞算法

MMSEG包含簡單最大匹配法和復雜最大匹配法，本文選取其中的復雜最大匹配法與統(tǒng)計方法進行結合。MMSEG的復雜最大匹配法首先識別出從當前讀取位置開始所有的塊（chunk），塊是包含三個詞的組合。對于句子 由多個字符構成，則

當前分詞位置為 時則其所有塊組成的集合表達式為

例如有字典dict=[研究，生命，研究生]，對句子“研究生命”進行分詞則能分出所有的塊：[研究，生命]，[研究，生，命]，[研究生，命]，[研，究，生命]，[研，究，生]。如果元素個數(shù)等于1，則選擇唯一的塊中的第一個詞作為分詞結果返回，如果元素多于1個，則依次應用規(guī)則1到4進行過濾。

規(guī)則1：最大總詞長

取總詞長度最長的塊中的第一個詞作為分詞結果返回。

假設的元素個數(shù)為中的元素的有效詞數(shù)（即不為空的詞的個數(shù)）為為詞w的長度，為中的詞，則i的總詞長計算公式為

取得最大詞長的塊的公式為

例如對于以上例子有

表1 各塊的總詞長

如果過濾后得到的候選塊個數(shù)等于1，則選擇該塊中的第一個詞作為分詞結果返回，如果多于1則應用規(guī)則2進行過濾。例子中根據(jù)規(guī)則1排除第5種方案，接著對剩下的4種應用規(guī)則2。

規(guī)則2：最大平均詞長

取平均詞長度最大的塊中的第一個詞作為分詞結果返回。

計算平均詞長的公式為

選擇最大平均詞長的塊的公式為

上文例子的平均詞長為

表2 各塊的平均詞長

如果過濾后得到的候選塊個數(shù)等于1，則選擇該塊中的第一個詞作為分詞結果返回，如果多于1則應用規(guī)則3進行過濾。例子中排除兩種方案，剩下兩種繼續(xù)應用規(guī)則3。

規(guī)則3：最小詞長方差

取詞長方差最小的塊中的第一個詞作為分詞結果返回。

詞長方差的計算公式為

得到最小方差的塊的公式為

例子中計算得到

表3 各塊的詞長方差

如果過濾后得到的候選塊個數(shù)等于1，則選擇該塊中的第一個詞作為分詞結果返回，如果多于1則應用規(guī)則4進行過濾。例子中選出了正確的分詞方案，即返回[研究，生命]中的“研究”一詞作為此次分詞的結果。

規(guī)則4：最大單字語素自由度之和

取單字語素自由度之和最大的塊中的第一個詞作為分詞結果返回。

假設有多重集（multiset）為中單字詞的集合，則有

以各個單字詞的出現(xiàn)頻數(shù)作為函數(shù)的真數(shù)并相加得到最大語素自由度之和，其計算公式為

取得最大語素自由度之和的塊的公式為

依靠以上規(guī)則可以解決大部分的分詞歧義問題，但也有相當?shù)囊徊糠志渥訜o法進行正確分詞，對于應用規(guī)則4后候選塊個數(shù)仍然多于1個的情況，MMSEG則無法處理，所以本文加入了下文的統(tǒng)計分詞算法。

（二）統(tǒng)計分詞算法

1.基本思想

本文使用的統(tǒng)計分詞算法類似中文分詞中的最大概率法，最大概率分詞是認為一個句子可能有多種分詞結果，而把概率最大的那種分詞結果作為正確的結果[5]。不完全和最大概率分詞方法相同的是本文的統(tǒng)計算法是計算得到概率最大的塊，選擇其第一個詞作為正確分詞結果返回，同時因為基于這樣的假設：每個詞的出現(xiàn)概率獨立。N-gram時間復雜度為v在這里表示一種語言詞典的詞匯量[6]33，而HMM使用的Viterbi算法復雜度為其中N為節(jié)點數(shù)，為網(wǎng)絡寬度[6]232，而本文統(tǒng)計方法的時間復雜度僅為其中表示分詞數(shù)，相對于N-gram和HMM等模型大大減少了計算量和降低了模型復雜度，提高了分詞的速度，在精度和效率間取得了一個平衡。

根據(jù)大數(shù)定律，可以知道只要語料庫足夠大，一個詞出現(xiàn)的頻率就等于其概率[6]30，在這里直接使用詞在訓練語料庫中出現(xiàn)的頻率代表其概率。設語料庫詞匯量為#，w出現(xiàn)次數(shù)為頻率為概率為有

由大數(shù)定律得

求出最大概率的塊，選取其中的第一個詞作為分詞結果返回

例如例子“和平和未來”在經(jīng)過MMSEG處理后仍然無法判定唯一的分詞方案，見表4

表4 各塊的語素自由度和

表5 各塊的概率

例子中得到了正確的分詞結果“和平”。

2.異常處理

對于經(jīng)過統(tǒng)計方法處理后仍然無法得到唯一分詞結果的情況，本文采用將該句子的第一個字作為切分結果返回，然后繼續(xù)往下切分。而對于未登陸詞，為了避免導致分詞總體概率為0，考慮到未登陸詞在應用場景中很可能屬于小概率詞，以及出于簡便的目的，將未登陸詞的出現(xiàn)次數(shù)設置為1，對應其概率則為1/#。

3.統(tǒng)計模塊偽代碼

二、實驗結果

（一）分詞結果

運行本文所實現(xiàn)的分詞程序，部分分詞結果如下圖所示

圖1 部分分詞效果

（二）實驗結果

為了方便且客觀地對比分詞的效果，本文所使用的訓練語料，測試語料以及評測答案均來自由北京大學為SIGHAN舉辦的的第二屆Bakeoff大賽提供的數(shù)據(jù)集，評測程序同樣采用該次比賽的評測程序。此數(shù)據(jù)集及數(shù)據(jù)說明可在SIGHAN官網(wǎng)提供的下載頁面[7]中找到，該屆比賽的比賽結果可在SIGHAN所提供的比賽結果公布頁面中找到。從公布的結果來看，在作為主要評測指標的F-measure上，本文算法優(yōu)于部分公布的參賽算法。因為語料的差異會嚴重影響分詞的最終結果，為了保證對算法本身的評測客觀，本文僅采用封閉測試進行實驗和對比，對比算法為未加入統(tǒng)計方法的MMSEG方法，評測指標主要采用F-measure，運行該測試集提供的評測程序score程序，主要輸出信息如下

通過實驗數(shù)據(jù)分析，本文提出的規(guī)則和統(tǒng)計結合的算法在保持和MMSEG分詞算法一樣的精確率的情況下提升了召回率，從而使得F-measure也有了小幅改善，在MMSEG上加入簡單的統(tǒng)計方法后分詞效果得到了小幅的提升。

三、結束語

本文提出的規(guī)則和統(tǒng)計相結合的分詞算法，能有效改善MMSEG的分詞效果，但還存在以下一些尚待改進的地方：詞出現(xiàn)概率獨立假設這一假設和過于簡化，未能全面，準確地反映現(xiàn)實情況。雖然簡化了計算過程，降低了計算量，但也同時丟失了詞間的上下文信息。未登錄詞的頻率替代問題。本文使用的替代檔案是用1代替，使得該詞對于所求概率影響無效化。當有大量未登陸詞時，會嚴重降低分詞效果，所以需要更為有效的平滑方法處理這種情況。

[1] 趙偉,戴新宇,尹存燕等.一種規(guī)則與統(tǒng)計相結合的漢語分詞方法[J].計算機工應用研究,2004(3):23-25.

[2] 奉國和,鄭偉.國內(nèi)中文自動分詞技術研究綜述[J].圖書情報工作,2011,55(2):41-45.

[3] Tsai C H.MMSEG: A Word Identification System for Mandarin Chinese Text Based on Two Variants of the Maximum Matching Algorithm [EB/OL]. http://technology.chtsai.org/mmseg/,2000.

[4] 張中耀,葛萬成,汪亮友等.基于MMSEG算法的中文分詞技術的研究與設計[J].信息技術,2006(6):17-20.

[5] 丁浩.基于最大概率分詞算法的中文分詞方法研究[J].科技信息,2010,(21):587.

[6] 吳軍.數(shù)學之美[M].第2版.北京:人民郵電出版社,2014:30.

[7] SIGHAN.SIGHAN官網(wǎng)[EB/OL]. http://sighan.cs.uchicago.edu/bakeoff2005/,2006.