基于最大匹配算法的似然導向中文分詞方法

楊貴軍，徐 雪，鳳麗洲，徐玉慧

(1.天津財經(jīng)大學 統(tǒng)計學院，天津 300222；2.中國聯(lián)合網(wǎng)絡(luò)通信有限公司 青島分公司，山東 青島 266000)

一、引言

近年來，隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展產(chǎn)生了大量的文本數(shù)據(jù)，其中蘊含著豐富的信息為人們?nèi)粘Ｉ畹母鱾€方面提供決策支持。中文分詞作為中文信息處理的基礎(chǔ)環(huán)節(jié)，分詞準確率的高低將直接影響中文文本數(shù)據(jù)挖掘的效果[1]。中文分詞技術(shù)具有非常廣闊的應用前景，已得到廣泛關(guān)注。因自然語言的模糊性和復雜性加大了中文分詞的難度，而高準確度的中文分詞方法對輿情分析[2]、信息推薦以及市場營銷等領(lǐng)域的中文文本數(shù)據(jù)挖掘，具有重要意義[3-4]。

目前，常用的中文分詞方法可以劃分為兩類：基于規(guī)則的分詞方法和基于統(tǒng)計的分詞方法[5]，其中最大匹配算法(Maximum Match)是最常用的基于規(guī)則分詞方法之一。該方法利用詞典作為分詞依據(jù)，以長詞優(yōu)先為基本原則，不需要考慮領(lǐng)域自適應性問題，只需要具有相關(guān)領(lǐng)域的高質(zhì)量詞典即可[6]，因而分詞速度較快。也正因為如此，該類方法歧義處理能力不強，經(jīng)常會錯誤地切分歧義字段，分詞效果仍有待提高，目前已經(jīng)出現(xiàn)了一些改進的最大匹配算法。莫建文等在傳統(tǒng)分詞詞典構(gòu)造的基礎(chǔ)上，結(jié)合雙字哈希結(jié)構(gòu)，利用改進的前向最大匹配分詞算法進行中文分詞[7]，而該算法沒有針對詞匯粘連現(xiàn)象進行特殊處理，無法避免由于詞典顆粒度過大導致的歧義切分問題；張勁松等利用前向匹配、回溯匹配和尾詞匹配有效發(fā)現(xiàn)了歧義字段[8]；周俊等將最長詞條優(yōu)先原則改為最長廣義詞條優(yōu)先原則以解決歧義問題，得到了比傳統(tǒng)最長詞條優(yōu)先原則更好的效果[9]。從研究方法可以看出，傳統(tǒng)的基于規(guī)則的分詞方法單純依賴詞典信息，并未有效利用分詞語料中詞與詞之間的共現(xiàn)關(guān)系，導致其分詞效果不夠理想。

基于統(tǒng)計的分詞方法利用已經(jīng)切分好的分詞語料作為主要的分詞依據(jù)，根據(jù)相鄰字或詞的緊密結(jié)合程度構(gòu)造統(tǒng)計模型進行分詞，當緊密程度高于某一個閾值時，可認為相鄰的字組成了一個詞組[10]。n-gram語言模型是基于統(tǒng)計分詞方法的常用模型之一[11]，該模型采用馬爾可夫條件假設(shè)，可以有效地利用訓練語料信息以及上下文相鄰詞之間的共現(xiàn)頻率等統(tǒng)計信息，很好地反映訓練語料中詞和詞之間的轉(zhuǎn)移關(guān)系，歧義處理能力較強。

針對以上兩類分詞方法具有的相對優(yōu)勢，部分學者提出了新的分詞方法，將詞典信息融入統(tǒng)計分詞模型中以改善分詞方法的性能[12-13]，但該類方法大多都僅將詞典當作一種內(nèi)部資源引入，其訓練和解碼都使用同樣的詞典[14]，同時也很少從統(tǒng)計模型的角度對基于規(guī)則的分詞序列進行概率判定。

筆者將兩類方法相結(jié)合，提出一種基于最大匹配算法的似然導向分詞方法。創(chuàng)新點主要包括：一是在分詞階段，利用基于詞典的最大匹配方法進行初始詞識別，在后續(xù)詞切分過程中根據(jù)訓練集數(shù)據(jù)的統(tǒng)計信息構(gòu)建訓練集共現(xiàn)詞典，并依據(jù)共現(xiàn)性自動識別后續(xù)詞，既提高了分詞效率，又能夠較好消解歧義詞，提高了分詞的準確性；二是在判定階段，利用基于馬爾可夫性的n-gram模型，提出基于似然導向的判定方法，并計算在分詞階段獲得的不同分詞序列的概率值?；谧畲笏迫辉泶_定最優(yōu)的分詞模式，既充分利用了已有的統(tǒng)計信息，又合理避免了每類分詞算法的不足。

二、最大匹配算法和n-gram語言模型

(一)基于規(guī)則的最大匹配算法

基于規(guī)則的最大匹配算法主要包括前向最大匹配、后向最大匹配和雙向匹配算法等。假設(shè)將包含所有詞條的通用詞典記為D，其最長詞條所含字數(shù)記為MaxLen。不失一般性，記長度為M的待切分漢字串S=s1，s2，…，sM。為了從語句中切分出詞條，前向最大匹配算法是從左向右取待切分語句的候選字串，記：

(1)

其中

(2)

則s1，s2，…，sk與通用詞典匹配成功，將s1，s2，…，sk作為一個詞切分出來；再繼續(xù)對漢字串sk+1，sk+2，…，sM按照式(1)進行匹配和切分，直到切分出所有詞為止，通常情況下k>1。當k=1時，即s1∈D，表示切分的單字作為一個詞條；當k=0時，即s1?D，表示切分的單字作為一個未登錄詞。后向最大匹配與前向最大匹配算法的基本原理相同，只是進行語句的反向切分。

最大匹配分詞方法不具備歧義檢測和消解能力，加大了后續(xù)歧義消解的難度。由于最大匹配分詞方法遵循“長詞優(yōu)先”的規(guī)則，導致每個詞語的長度相對較大，會造成算法的很多無效循環(huán)，并對分詞效率產(chǎn)生負面影響。此外，傳統(tǒng)的最大匹配分詞方法一般都是利用通用詞典按照某種模式進行字串的切分，會使分詞結(jié)果受詞典的顆粒度影響較大，容易產(chǎn)生詞語粘連現(xiàn)象[15]，影響分詞準確性。例如：

邏輯/思維/能力→邏輯思維/能力(前為正確切分，后為錯誤切分，下同)

國際/貿(mào)易壁壘/的/現(xiàn)狀→國際貿(mào)易壁壘/的/現(xiàn)狀

在不考慮標準分詞結(jié)果的情況下，有些分詞結(jié)果也可以認為是正確的。但是，標準分詞結(jié)果是以訓練語料為基礎(chǔ)獲得的，因而所提出分詞方法產(chǎn)生的分詞結(jié)果需要符合訓練語料中詞語的切分模式。

(二) 基于統(tǒng)計的n-gram語言模型

假設(shè)S=s1，s2，…，sM為待切分漢字串，可以切分為N個詞條，記為S=w1，w2，…，wN。采用n-gram語言模型，詞條序列w1，w2，…，wN出現(xiàn)的概率為：

P(S=w1，w2，…，wN)

=p(w1)p(w2|w1)…p(wn|w1，w2，…，wN-1)

(3)

其中約定p(w1|w0)=p(w1)，表示以詞條w1開始的句子在訓練集中出現(xiàn)的概率。上式的概率計算在當前的計算機水平下往往是不可行的。因而，n-gram語言模型引入馬爾可夫條件假設(shè)，即認為第n個詞出現(xiàn)的概率只與其前面的n-1個詞相關(guān)，而與其它詞都不相關(guān)。S出現(xiàn)的概率就是詞條序列w1,w2,…,wN出現(xiàn)概率的乘積：

P(S=w1，w2，…，wN)

(4)

其中max(1,i-n)表示1和i-n的最大值。當n=1時，一個詞的出現(xiàn)僅依賴于其前面出現(xiàn)的1個詞，分詞模型被稱為bi-gram，即：

(5)

仍約定p(w1|w0)=p(w1)。

本文將基于規(guī)則的分詞方法和基于統(tǒng)計的分詞方法結(jié)合起來，其中將基于規(guī)則的最大匹配分詞方法視為一種初級分詞法，并利用其對待測試文本進行簡單、快速處理；利用統(tǒng)計語言信息處理詞語粘連以及后續(xù)詞/前綴詞的自動擴展等，生成多組候選分詞序列；利用基于馬爾可夫性的n-gram模型，計算候選分詞序列的概率值，以最大似然原理作為依據(jù)選擇最優(yōu)的分詞模式，得到最終的分詞結(jié)果。新方法不僅充分利用了訓練集的詞頻規(guī)律，還有效彌補了單一分詞算法的不足。

三、基于最大匹配算法的似然導向中文分詞方法

基于最大匹配算法的似然導向中文分詞方法主要包括三個階段：預處理階段、分詞階段、判定階段，具體流程如圖1所示。預處理階段的目的是構(gòu)建共現(xiàn)詞典，為分詞階段的自動識別后續(xù)詞/前綴詞以及為判定階段的計算多組概率值做準備；分詞階段的任務是將基于規(guī)則的前向/后向最大匹配算法與基于統(tǒng)計信息的詞共現(xiàn)性方法相結(jié)合，對測試語料中待劃分的句子進行分詞操作，生成多組候選分詞序列，而在該階段中每種候選分詞序列的作用應該是均等的；判定階段的任務是利用基于馬爾可夫性的n-gram語言模型，計算多組候選分詞序列對應的概率作為序列子串的似然函數(shù)，并選取似然概率值最大的分詞序列作為最終的分詞結(jié)果。

圖1 基于最大匹配的似然導向中文分詞方法流程圖

(一)預處理階段

表1 正向訓練集共現(xiàn)詞典DF表

表2 逆向訓練集共現(xiàn)詞典DB表

(二)分詞階段

針對前向/后向最大匹配算法，使用兩類詞典：一類為不含上下文信息的通用詞典D；另一類為在預處理階段構(gòu)建的包含上下文信息的共現(xiàn)詞典DF和DB。該階段的分詞策略是利用基于通用詞典的最大匹配方法切分初始詞，為了提高分詞效率并消解歧義詞，本文在后續(xù)詞切分過程中，基于領(lǐng)域訓練集語料的統(tǒng)計信息和后續(xù)詞的共現(xiàn)性自動識別后續(xù)詞。

本文利用前向最大匹配與后向最大匹配算法進行分詞的實現(xiàn)思想基本相同，區(qū)別在于利用了不同的訓練集共現(xiàn)詞典DF和DB。下面，以前向最大匹配算法為例描述具體分詞過程：

wN=skN-1+1…sM

(6)

后續(xù)詞的自動識別，一方面是基于詞語的共現(xiàn)性，比較符合人們進行文字表述的規(guī)律；另一方面是大大減少重復切詞和匹配通用詞典的循環(huán)操作，可以提高分詞方法的效率。實際操作時，如果在DF中找不到可以匹配的后續(xù)詞，則轉(zhuǎn)step1，重新在D中進行查找是否有匹配項，并執(zhí)行后續(xù)操作。

經(jīng)過上述步驟，最終可以生成多組候選分詞序列。

(三)判定階段

(7)

語料庫不可能包含所有可能出現(xiàn)的序列，某些詞條在語料中出現(xiàn)頻數(shù)會很少。為了降低數(shù)據(jù)稀疏問題對計算似然概率帶來的影響，僅使用bi-gram語言模型估計似然概率。將式(7)簡化為式(8)的形式，即得到基于馬爾可夫性的bi-gram語言模型：

(8)

在訓練語料中用未曾共現(xiàn)過的新序列計算似然概率時，會出現(xiàn)估計值為零的情況。為此，采用數(shù)據(jù)平滑策略對其進行處理，似然概率計算公式如下：

(9)

其中δ(0≤δ≤1)為平滑參數(shù)，表示每個詞出現(xiàn)的頻數(shù)比實際統(tǒng)計頻數(shù)多δ次；DF為DF中詞共現(xiàn)詞條的總頻數(shù)。

四、 實驗

(一)實驗語料

實驗語料來源于SIGHAN組織的國際中文自然語言處理競賽(Bakeoff)，實驗數(shù)據(jù)包括標準詞典、訓練語料、測試語料以及測試語料的標準切分。由于編碼方式的不同，實驗僅在中文簡體語料庫上進行了測試，訓練語料包含44.947萬詞，測試語料包含11.35萬詞。在訓練過程中，實驗還使用了通用詞典，包含42.7452萬詞。

(二) 實驗方法

本文針對8種算法進行中文分詞對比實驗：

1)FMM：傳統(tǒng)前向最大匹配分詞方法。

2)BMM：傳統(tǒng)后向最大匹配分詞方法。

3)FBMM：將似然導向用于FMM和BMM的分詞方法。

4)IFMM：利用詞共現(xiàn)性改進的前向最大匹配分詞方法。

5)IBMM：利用詞共現(xiàn)性改進的后向最大匹配分詞方法。

6)POMM：基于最大匹配算法的似然導向中文分詞方法。在該方法中，分詞階段利用詞共現(xiàn)性改進FMM和BMM，判定階段結(jié)合n-gram語言模型實現(xiàn)似然導向功能。

7)IPOMM1：在POMM的基礎(chǔ)上，為解決分詞粘連現(xiàn)象，針對分詞階段獲得的初始詞加入再次切分策略。

8)IPOMM2：在IPOMM1的基礎(chǔ)上，為避免零概率問題，在判定階段計算似然概率時采用平滑參數(shù)δ=0.000 01的平滑策略。

(三)評價指標

為了評價本文方法的分詞性能，分別選擇準確率、召回率、F1值和時間開銷作為評價指標。準確率是在分詞方法生成的分詞結(jié)果中切分正確的目標詞所占的比例，即分詞方法正確分詞數(shù)/分詞方法分詞總數(shù)，記為P；召回率是針對標準分詞結(jié)果中，分詞方法生成的分詞結(jié)果被正確切分的目標詞所占的比例，即分詞方法正確分詞數(shù)/標準分詞總數(shù)，記為R；F1值為F1=2PR/(P+R)，F(xiàn)1值折中考慮準確率與召回率，綜合反映分詞方法的整體效果。

(四)實驗結(jié)果與分析

將以上8種方法歸納為3種類型，其中第1類包括FMM、BMM、FBMM；第2類包括IFMM、IBMM、POMM；第3類包括IPOMM1、IPOMM2。表3給出了3類方法的對比實驗結(jié)果，其中“right”列表示分詞方法生成的分詞結(jié)果中切分正確的目標詞數(shù)量；“split”列表示分詞方法生成的全部詞數(shù)量；“goal”列表示標準分詞結(jié)果中詞的數(shù)量。

表3 不同方法的準確率、召回率、F1值比較表

由表3可知：在第1類方法中，BMM與FBMM方法對應的準確率、召回率及F1值均為0.855 2、0.816 3、0.835 3，F(xiàn)BMM表現(xiàn)與BMM一致，這是由于似然導向策略使得FBMM方法對應結(jié)果由BMM決定；雖然BMM在準確率上高于FMM方法，但從正確切分目標詞數(shù)量上可以看出BMM對應的right值(92 681)少于FMM對應結(jié)果(93 128)。可見，BMM方法在召回正確切分目標詞數(shù)量上并未獲得提高。

第2類方法中，IFMM、IBMM、POMM在P、R、F1值方面，相比于第1類方法均有改善，尤其在使用基于n-gram的似然導向策略時準確率從0.834 8提高到0.871 1、召回率從0.820 3提高到0.832 2，這說明在基于規(guī)則的最大匹配算法中考慮基于統(tǒng)計的詞共現(xiàn)性信息能有效提高算法的準確率和召回率；同時，對POMM方法判定階段的似然導向策略起到了積極作用，從正確切分目標詞數(shù)量上也可以看出POMM 對應的right值(94 474)大于FBMM對應結(jié)果(92 681)，似然導向策略增加了目標詞的召回率，這說明POMM方法綜合考慮了IFMM、IBMM各自的優(yōu)勢，引入詞共現(xiàn)性和似然導向策略能有效提高分詞算法的性能，驗證了似然導向相比于單個分詞方法的優(yōu)勢。

第3類方法中，IPOMM1、IPOMM2相對于第1、2類方法，在P、R、F1值方面都得到明顯提升。例如第1、2類方法準確率的最大值分別為0.855 2和0.871 1，明顯小于IPOMM1和IPOMM2的結(jié)果；在召回率方面，從第1、2類方法的最大值0.820 3、0.832 2，提高到了0.887 0。通過對比召回目標詞數(shù)量發(fā)現(xiàn)，第1類方法中FMM方法最優(yōu)，正確分詞數(shù)量為93 128；第2類方法中POMM方法最優(yōu)，正確分詞數(shù)量為94 474；第3類方法中IPOMM2方法最優(yōu)，正確分詞數(shù)量為100 692，這進一步說明了引入詞共現(xiàn)性和似然導向策略能有效提高分詞算法性能。

對具體的錯誤分詞結(jié)果進行分析發(fā)現(xiàn)：第1類方法基于最大匹配算法，受到通用詞典顆粒度的影響，易出現(xiàn)粘連現(xiàn)象；第2類方法通過加入基于統(tǒng)計的詞共現(xiàn)性信息，在一定程度上減少了這種粘連現(xiàn)象，但在初始詞劃分時依然受到通用詞典中詞的顆粒度的影響；第3類方法在第2類方法的框架下優(yōu)化了初始詞切分策略，克服了最大匹配算法受通用詞典顆粒度影響較大的問題。此外，該方法在判定階段調(diào)整了平滑參數(shù)，降低了數(shù)據(jù)稀疏對概率計算準確性的影響。圖2展示了第3類方法IPOMM2與第1類方法FBMM在錯誤分詞結(jié)果方面的對比情況，即圖2中的詞是采用FBMM方法會被錯誤切分但采用IPOMM2方法時可以正確切分的詞，例如在FBMM 方法中切分錯的詞“國有企業(yè)”、“非關(guān)稅壁壘”、“經(jīng)濟運行”等，通過IPOMM2方法正確切分為“國有/企業(yè)”、“非關(guān)稅/壁壘”、“經(jīng)濟/運行”等；第3類方法IPOMM2有效解決了中文分詞中受詞典顆粒度影響而產(chǎn)生的詞語粘連問題。

圖2 錯誤分詞結(jié)果對比詞云圖

第1類方法第2類方法第3類方法FBMMPOMMIPOMM1IPOMM2T= 63.74T= 56.30T= 56.51T=59.84

表4對比了3類分詞方法中采用似然導向策略時所需的時間開銷，即第1類方法中的FBMM、第2類方法中的POMM、第3類方法中的IPOMM1和IPOMM2。由表4知，第2類方法、第3類方法所產(chǎn)生的時間開銷普遍少于第1類方法，說明分詞階段進行后續(xù)詞/前綴詞的自動擴展有助于提高運算效率；第3類方法為了減少詞語粘連現(xiàn)象和避免零概率問題，在第2類方法的基礎(chǔ)上優(yōu)化了初始詞切分方法并調(diào)整了平滑參數(shù)，因而導致第3類方法的時間開銷稍高于第2類方法，在提升分詞性能的同時稍微損失一些計算效率，也是在可接受范圍內(nèi)。

五、結(jié)語

本文結(jié)合基于規(guī)則的分詞方法與基于統(tǒng)計的分詞方法的優(yōu)勢，提出了一種基于最大匹配算法的似然導向中文分詞方法POMM。新方法在分詞階段引入詞共現(xiàn)性，很好地發(fā)揮了基于統(tǒng)計的分詞方法處理詞與詞之間緊密程度的優(yōu)勢；在判定階段利用n-gram語言模型的馬爾可夫性對不同的概率值進行似然導向調(diào)整；在POMM的基礎(chǔ)上，針對粒度較大的初始詞進一步切分以消解歧義，并調(diào)整平滑參數(shù)，避免數(shù)據(jù)稀疏所帶來的精度下降問題。相比于傳統(tǒng)的最大匹配算法或者單一分詞方法，新方法在準確率、召回率、F1值方面均得到了顯著的提升。

對于某些詞語，似然導向也帶來了一定的負效應，即前向最大匹配/后向最大匹配可以正確切分的詞，使用似然導向方法偶爾會發(fā)生切分錯誤。在下一步研究中，一方面將考慮引入多種不同的分詞策略或者新詞識別方法以解決無法正確切分的句子；另一方面將引入集成學習方法以保留更多的正確導向，降低錯誤率。