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

劉 洋 余 甜 丁 藝

（西安郵電大學計算機學院 西安 710121）

1 引言

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

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

2 中文分詞的發展

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

最早的中文分詞是在20世紀80年代由梁南元教授提出的一種基于“查字典”的方式。同時，也開發出了第一個分詞系統。基于查字典的方式是將句子與詞典中的詞條進行匹配［6］。若碰到復合詞時，就選擇最長的詞條進行匹配。若句子中的內容未出現在詞典中時，則進行單字分割。但這種方法的局限性是并不能解決二義性的問題。

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

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

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

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

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

在中國古代醫學領域，由于中醫注釋數據的缺乏，李思等選取了十種類型、三十本中國古代醫學典籍建立了注釋語料庫，并在2018 年使用膠囊網絡實現了中國古代醫學典籍的中文分詞。實驗結果表明，該方法能有效地提高古代醫學文本的分詞性能［14］。

2019 年，昆明大學邵教授［15］研究了冶金領域的漢語分詞。目前的分詞方法多為基于規則的分詞方法和傳統的機器學習方法。

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

3 JIEBA中文分詞的原理

JIEBA分詞算法如下。

基于前綴詞典實現高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無環圖（DAG）［17］。

采用了動態規劃查找最大概率路徑，找出基于詞頻的最大切分組合。

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

JIEBA支持的三種分詞模式：

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

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

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

paddle模式，利用PaddlePaddle深度學習框架，訓練序列標注（雙向GRU）網絡模型實現分詞。同時支持詞性標注。

4 改進的最大概率路徑算法

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

對于一個有要進行分詞的句子，第一個任務是DAG 的獲取，然后用DP 算法計算有向無環圖的最大概率路徑。DP 算法之所以可以用來求解最大概率路徑，是因為滿足重復子問題和最優子結構這兩個條件。

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

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

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

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

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] 是存儲每個被分單詞的結束位置和概率的空間，total表示所有分割單詞頻率的總和，DAG是前一步生成的有向無環圖。

5 實驗結果與結論

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

C000008 數據集分詞5 次的比較結果如表1 所示。

表1 C000008組數據運行時間對比表

C000010 數據集分詞5 次的比較結果如表2 所示。

表2 C000010組數據運行時間對比表

C000013 數據集分詞5 次的比較結果如表3 所示。

表3 C000013組數據運行時間對比表

C000016 數據集分詞5 次的比較結果如表4 所示。

表4 C000016組數據運行時間對比表

C000020 數據集分詞5 次的比較結果如表5 所示。

表5 C000020組數據運行時間對比表

C000022 數據集分詞5 次的比較結果如表6 所示。

表6 C000022組數據運行時間對比表

C000023 數據集分詞5 次的比較結果如表7 所示。

表7 C000023組數據運行時間對比表

C000024 數據集分詞5 次的比較結果如表8 所示。

表8 C000024組數據運行時間對比表

為了更清楚地對比新方法與JIEBA 分詞的運行時間，對以上幾組數據進行Matlab 仿真實驗，結果如圖8所示。

圖1 實驗Matlab仿真對比圖

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

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

表9 8組數據平均運行速率提升表

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

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

其中，FN 表示False Negative，被判定為負樣本，但事實上是正樣本。FP表示False Positive，被判定為正樣本，但事實上是負樣本。TN 表示True Negative，被判定為負樣本，事實上也是負樣本。TP 表示True Positive，被判定為正樣本，事實上也是正樣本。

計算以上8 組數據的準確率、召回率和F 值。結果如表10所示。

表10 8組數據的分詞性能指標表

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

6 結語

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

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

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