一種新的基于最大概率路徑的中文分詞*

劉 洋 余 甜 丁 藝

（西安郵電大學(xué)計算機(jī)學(xué)院 西安 710121）

1 引言

隨著自然語言處理［1］以及人工智能［2］的飛速發(fā)展，越來越多的人們希望計算機(jī)可以代替人類的工作。如果想讓計算機(jī)“聽懂”人類的語言，計算機(jī)就需要對文本和詞語進(jìn)行分析，那么中文分詞就成為了最重要的一部分。中文分詞的任務(wù)是將整個句子在不改變語義的前提下切分成一個個單詞。例如，可以將“失敗是成功之母”切分為“失敗/是/成功/之/母”。不同于英文的是，英文可以用空格符自然的將一句話切分成一個個單詞，而中文并沒有這樣自然的符號。因此，在文本分析，信息匹配，計算文本相似度等自然語言處理的范疇上，中文分詞是必不可少的一部分。

為了提高中文分詞的速度，本文提出了一種新的求解最大概率路徑的方法，將這種方法應(yīng)用至中文分詞，并將基于該方法的中文分詞與JIEBA［3］中文分詞分別進(jìn)行實(shí)驗(yàn)，在搜狗新聞數(shù)據(jù)集下經(jīng)過實(shí)驗(yàn)驗(yàn)證，與JIEBA 中文分詞相比，該方法可以在保證良好的分詞效果的基礎(chǔ)上提高分詞速度。

2 中文分詞的發(fā)展

中文分詞一直都是自然語言處理中十分重要的部分。由于二義性，歧義以及一些問題，中文分詞一直都是人們討論的熱門話題［4~5］。

最早的中文分詞是在20世紀(jì)80年代由梁南元教授提出的一種基于“查字典”的方式。同時，也開發(fā)出了第一個分詞系統(tǒng)?；诓樽值涞姆绞绞菍⒕渥优c詞典中的詞條進(jìn)行匹配［6］。若碰到復(fù)合詞時，就選擇最長的詞條進(jìn)行匹配。若句子中的內(nèi)容未出現(xiàn)在詞典中時，則進(jìn)行單字分割。但這種方法的局限性是并不能解決二義性的問題。

接著，哈爾濱大學(xué)的王曉龍［7］博士嘗試將查字典的方式理論化，于是提出了一種最短單詞分割的理論，但二義性的問題仍然存在。

1990年，清華大學(xué)的郭進(jìn)［8］博士提出了一種統(tǒng)計語言模型，成功地解決了詞語二義性的問題并且降低了分詞的錯誤率。

2002 年以年，基于字典的方式一直是中文分詞的主流。直到2002年，在第一屆SIGHAN會議上出現(xiàn)了一篇基于字標(biāo)注的中文分詞的文章［9］。Xue提出了基于最大熵馬爾科夫模型的中文分詞算法［10］。中文分詞被認(rèn)為是為字符序列進(jìn)行標(biāo)注的任務(wù)［11］。在2004 年，Peng［12］使用條件隨機(jī)場模型解決了序列標(biāo)注的問題。隨后，基于詞性標(biāo)注的分詞成為熱門話題。

2010 年，文獻(xiàn)［13］提出了一種基于互信息的最大熵分割算法。該算法通過查找每個可能的單詞及其對應(yīng)的頻率來工作。然后，計算這些詞的條件概率。最后，選擇概率最大的單詞。然而，切分的準(zhǔn)確性受到訓(xùn)練語料庫的影響。

2015 年，彭嘗試對中國文本中的人格特征進(jìn)行分類。他們收集了一組以中文為主要書面語言的Facebook 用戶的帖子和個性評分?jǐn)?shù)據(jù)，使用JIEBA分詞工具來進(jìn)行文本分割。

在中國古代醫(yī)學(xué)領(lǐng)域，由于中醫(yī)注釋數(shù)據(jù)的缺乏，李思等選取了十種類型、三十本中國古代醫(yī)學(xué)典籍建立了注釋語料庫，并在2018 年使用膠囊網(wǎng)絡(luò)實(shí)現(xiàn)了中國古代醫(yī)學(xué)典籍的中文分詞。實(shí)驗(yàn)結(jié)果表明，該方法能有效地提高古代醫(yī)學(xué)文本的分詞性能［14］。

2019 年，昆明大學(xué)邵教授［15］研究了冶金領(lǐng)域的漢語分詞。目前的分詞方法多為基于規(guī)則的分詞方法和傳統(tǒng)的機(jī)器學(xué)習(xí)方法。

分詞作為一項(xiàng)基礎(chǔ)技術(shù)，在自然語言處理中發(fā)揮了重要作用，尤其是對于那些沒有明確分隔符的語言，如漢語、韓語、日語等［16］。本文所提出的基于最大概率路徑的中文分詞屬于序列標(biāo)注的范疇，目前也屬于較為主流的方法。

3 JIEBA中文分詞的原理

JIEBA分詞算法如下。

基于前綴詞典實(shí)現(xiàn)高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構(gòu)成的有向無環(huán)圖（DAG）［17］。

采用了動態(tài)規(guī)劃查找最大概率路徑，找出基于詞頻的最大切分組合。

對于未登錄詞，采用了基于漢字成詞能力的HMM 模型，使用了Viterbi 算法。

JIEBA支持的三種分詞模式：

1）精確模式，試圖將句子最精確地切開，適合文本分析［18］；

2）全模式，把句子中所有的可以成詞的詞語都掃描出來，速度非?？?，但是不能解決歧義；

3）搜索引擎模式，在精確模式的基礎(chǔ)上，對長詞再次切分，提高召回率，適合用于搜索引擎分詞。

paddle模式，利用PaddlePaddle深度學(xué)習(xí)框架，訓(xùn)練序列標(biāo)注（雙向GRU）網(wǎng)絡(luò)模型實(shí)現(xiàn)分詞。同時支持詞性標(biāo)注。

4 改進(jìn)的最大概率路徑算法

求解最大概率路徑算法就是尋找概率最大的路徑。將最大概率路徑算法應(yīng)用至中文分詞，過程如下。

對于一個有要進(jìn)行分詞的句子，第一個任務(wù)是DAG 的獲取，然后用DP 算法計算有向無環(huán)圖的最大概率路徑。DP 算法之所以可以用來求解最大概率路徑，是因?yàn)闈M足重復(fù)子問題和最優(yōu)子結(jié)構(gòu)這兩個條件。

在求解最大概率路徑部分時，通常采用的詞頻總和是詞典中所有單詞的詞頻相加，是一個很大的數(shù)。當(dāng)我們計算頻率時，由于詞頻總和過大，用作分母時，會出現(xiàn)下溢問題。同時，利用復(fù)雜的對數(shù)運(yùn)算來解決最大概率路徑會引起時間浪費(fèi)問題。針對以上兩大不足，本文改進(jìn)了求解最大概率路徑的問題。

該方法減小了詞頻總和數(shù)值的大小。新方法的詞頻總和摒棄了詞典中所有詞語的總和，新方法詞頻總和只需要計算中文文本中出現(xiàn)的詞，這樣便使詞頻總和的數(shù)值見笑了，避免了溢出問題。

該方法采用簡單的除法計算，通過減少計算的消耗來提高分詞速度。

新方法的偽指令如下所示：

input：self，sentence，DAG，route

output：route

Step1：N ← the length of sentence，total ←0，

route［N］←（0，0）

Step2：for a ←N-1，N-2，……-1 do

for b ←DAG［a］

Total+=self.FREQ.get（sentence［a：b+1］or 1）

Step3：for idx ←N-1，N-2，……-1 do

for x ←DAG［idx］

route［idx］=max（（（self.FREQ.get（sentence［idx：x+1］）or 1）/total+route［x+1］［0］，x）for x in DAG［idx］）

該偽指令是一種新的求解最大概率路徑的方法，sentence表示待分詞的句子，N表示待分詞文本的長度，route[N] 是存儲每個被分單詞的結(jié)束位置和概率的空間，total表示所有分割單詞頻率的總和，DAG是前一步生成的有向無環(huán)圖。

5 實(shí)驗(yàn)結(jié)果與結(jié)論

本文將新的求解最大概率路徑方法與JIEBA分詞進(jìn)行對比。使用搜狗新聞數(shù)據(jù)集對8 組不同的新聞數(shù)據(jù)進(jìn)行5 次分詞實(shí)驗(yàn)，每組新聞數(shù)據(jù)包含1190 篇不同的新聞文章。對比新方法和JIEBA 分詞的運(yùn)行時間，得到以下結(jié)果。

C000008 數(shù)據(jù)集分詞5 次的比較結(jié)果如表1 所示。

表1 C000008組數(shù)據(jù)運(yùn)行時間對比表

C000010 數(shù)據(jù)集分詞5 次的比較結(jié)果如表2 所示。

表2 C000010組數(shù)據(jù)運(yùn)行時間對比表

C000013 數(shù)據(jù)集分詞5 次的比較結(jié)果如表3 所示。

表3 C000013組數(shù)據(jù)運(yùn)行時間對比表

C000016 數(shù)據(jù)集分詞5 次的比較結(jié)果如表4 所示。

表4 C000016組數(shù)據(jù)運(yùn)行時間對比表

C000020 數(shù)據(jù)集分詞5 次的比較結(jié)果如表5 所示。

表5 C000020組數(shù)據(jù)運(yùn)行時間對比表

C000022 數(shù)據(jù)集分詞5 次的比較結(jié)果如表6 所示。

表6 C000022組數(shù)據(jù)運(yùn)行時間對比表

C000023 數(shù)據(jù)集分詞5 次的比較結(jié)果如表7 所示。

表7 C000023組數(shù)據(jù)運(yùn)行時間對比表

C000024 數(shù)據(jù)集分詞5 次的比較結(jié)果如表8 所示。

表8 C000024組數(shù)據(jù)運(yùn)行時間對比表

為了更清楚地對比新方法與JIEBA 分詞的運(yùn)行時間，對以上幾組數(shù)據(jù)進(jìn)行Matlab 仿真實(shí)驗(yàn)，結(jié)果如圖8所示。

圖1 實(shí)驗(yàn)Matlab仿真對比圖

根據(jù)8 組新聞數(shù)據(jù)進(jìn)行分詞實(shí)驗(yàn)，可以計算出每組數(shù)據(jù)的平均運(yùn)行速度。根據(jù)表中的數(shù)據(jù)得到，新方法的分詞運(yùn)行時間比JIEBA 分詞的運(yùn)行時間明顯減少。同時，也可以計算出每組數(shù)據(jù)的平均運(yùn)行時間減少率，也就是提升的平均運(yùn)行速率。計算公式如下：

如式（1）所示，AVG[i]表示第i組數(shù)據(jù)的平均提高速率，Runningtime[i]表示第i組數(shù)據(jù)使用新方法進(jìn)行中文分詞的運(yùn)行時間，RunningtimeJIEBA[i]表示第i組數(shù)據(jù)使用JIEBA 進(jìn)行中文分詞的運(yùn)行時間。計算結(jié)果如表9所示。

表9 8組數(shù)據(jù)平均運(yùn)行速率提升表

從以上分析可以看出，使用2018 年搜狗新聞數(shù)據(jù)集進(jìn)行分詞實(shí)驗(yàn)后，分詞的平均速度有著顯著的提高。為了保證新方法的中文分詞的效果，本文對各數(shù)據(jù)的準(zhǔn)確率（P）、召回率（R）和F 值（F1）進(jìn)行計算，利用這三個指標(biāo)來評價改進(jìn)后的中文分詞的性能。

準(zhǔn)確性是將檢索到的相關(guān)文檔劃分為所有檢索到的文檔的比率。它指的是對一個對象所表達(dá)的描述的正確程度，用來反映該對象的正確答案。召回率是文檔庫中檢索到的相關(guān)文檔數(shù)量與相關(guān)文檔總數(shù)的比率。兩個值都在0~1 之間。值越接近1，則準(zhǔn)確率或召回率越高。F 值為平均準(zhǔn)確率和召回率。將JIEBA 中文分詞的結(jié)果作為原始文檔，將新方法的中文分詞結(jié)果作為測試文檔，通過計算以上三個指標(biāo)，就可以判斷出新方法的中文分詞性能是否良好。三種指標(biāo)的計算公式如下：

其中，F(xiàn)N 表示False Negative，被判定為負(fù)樣本，但事實(shí)上是正樣本。FP表示False Positive，被判定為正樣本，但事實(shí)上是負(fù)樣本。TN 表示True Negative，被判定為負(fù)樣本，事實(shí)上也是負(fù)樣本。TP 表示True Positive，被判定為正樣本，事實(shí)上也是正樣本。

計算以上8 組數(shù)據(jù)的準(zhǔn)確率、召回率和F 值。結(jié)果如表10所示。

表10 8組數(shù)據(jù)的分詞性能指標(biāo)表

根據(jù)表中數(shù)據(jù)，準(zhǔn)確率、找回率和F 值均大于95%，說明與已有的JIEBA 中文分詞相比，新方法的中文分詞效果良好并且可以減少中文分詞運(yùn)行時間，提升中文分詞速率。

6 結(jié)語

總地來說，中文分詞也存在一些缺點(diǎn)，分割結(jié)果并不總是正確的，本文旨在提高分詞的運(yùn)行速度。在以后的工作中，主要有以下兩點(diǎn)展望：

1）目前比較流行的中文分詞方法還有基于神經(jīng)網(wǎng)絡(luò)的分詞方法，下一步將投入研究基于神經(jīng)網(wǎng)絡(luò)的分詞，通過引入注意力機(jī)制［19］提升分詞的精度。

2）新研發(fā)出的BERT 模型［20］以及膠囊模型［21］，可以進(jìn)行深入研究，使之更好地應(yīng)用至中文分詞，來提升中文分詞的精度。