（東莞理工學(xué)院城市學(xué)院，廣東 東莞 523419）

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

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

（一）MMSEG分詞算法

MMSEG包含簡(jiǎn)單最大匹配法和復(fù)雜最大匹配法，本文選取其中的復(fù)雜最大匹配法與統(tǒng)計(jì)方法進(jìn)行結(jié)合。MMSEG的復(fù)雜最大匹配法首先識(shí)別出從當(dāng)前讀取位置開(kāi)始所有的塊（chunk），塊是包含三個(gè)詞的組合。對(duì)于句子 由多個(gè)字符構(gòu)成，則

當(dāng)前分詞位置為 時(shí)則其所有塊組成的集合表達(dá)式為

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

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

取總詞長(zhǎng)度最長(zhǎng)的塊中的第一個(gè)詞作為分詞結(jié)果返回。

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

取得最大詞長(zhǎng)的塊的公式為

例如對(duì)于以上例子有

表1 各塊的總詞長(zhǎng)

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

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

取平均詞長(zhǎng)度最大的塊中的第一個(gè)詞作為分詞結(jié)果返回。

計(jì)算平均詞長(zhǎng)的公式為

選擇最大平均詞長(zhǎng)的塊的公式為

上文例子的平均詞長(zhǎng)為

表2 各塊的平均詞長(zhǎng)

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

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

取詞長(zhǎng)方差最小的塊中的第一個(gè)詞作為分詞結(jié)果返回。

詞長(zhǎng)方差的計(jì)算公式為

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

例子中計(jì)算得到

表3 各塊的詞長(zhǎng)方差

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

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

取單字語(yǔ)素自由度之和最大的塊中的第一個(gè)詞作為分詞結(jié)果返回。

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

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

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

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

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

1.基本思想

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

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

由大數(shù)定律得

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

例如例子“和平和未來(lái)”在經(jīng)過(guò)MMSEG處理后仍然無(wú)法判定唯一的分詞方案，見(jiàn)表4

表4 各塊的語(yǔ)素自由度和

表5 各塊的概率

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

2.異常處理

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

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

二、實(shí)驗(yàn)結(jié)果

（一）分詞結(jié)果

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

圖1 部分分詞效果

（二）實(shí)驗(yàn)結(jié)果

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

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

三、結(jié)束語(yǔ)

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

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

[2] 奉國(guó)和,鄭偉.國(guó)內(nèi)中文自動(dòng)分詞技術(shù)研究綜述[J].圖書(shū)情報(bào)工作,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] 張中耀,葛萬(wàn)成,汪亮友等.基于MMSEG算法的中文分詞技術(shù)的研究與設(shè)計(jì)[J].信息技術(shù),2006(6):17-20.

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

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

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