一种新的基于最大概率路径的中文分词*

刘 洋 余 甜 丁 艺

（西安邮电大学计算机学院 西安 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］，可以进行深入研究，使之更好地应用至中文分词，来提升中文分词的精度。