基于N―gram模型的中文分词前k优算法

摘要：本文首先从中文输入法应用的角度出发，在阐述了N-gram模型的基础上对中文输入法的分词进行了详细的剖析，进一步根据训练数据的稀疏问题，使用Back-off模型进行数据的平滑处理。针对系统词库数量受限的问题，在构建词图的前提下，使用基于A*的算法求解前k优路径。最后实验结果表明，本文所使用的基于A*的算法与改进Dijkstra算法、基于DP的算法等常用的求前k优路径的算法相比，具有较高的效率和准确率，为中文分词及求取k-best算法的研究开拓了新的思路。

关键词：中文输入法； N-gram模型； k优路径； A*算法

中图分类号： TP391

文献标志码：A

文章编号： 2095-2163（2016）06-0031-05

0引言

[JP2]中文输入法（Chinese input method）是指为了将汉字输入计算机或手机等电子设备而采用的编码方法，是中文信息处理的重要技术。时下的中文输入法可分为基于音标（Phonetic-based）和基于字形（Shape-based）两种类型[1]，本文使用的方法则属于第一类。一个具有整句输入功能的输入法主要包括着以下部分：首先是语言模型，语言模型将提供输入法其他部分所需要的信息；其次是输入处理（拼音流切分）[2]，该部分把输入的拼音流切分为单个音节的序列，供音-字转换部分设计使用；最后是音-字转换部分，该部分将处理好的单音节序列转化为汉字编码进行结果输出。其中，汉语的语言模型大体上可划定为基于字和基于词的这样2个研究进展方向。[JP3]

而为了提供整句输入，并减少输入成本，基于词的语言模型即已成为本次分析处理首选。在此基础上，研究可知，语言模型的建立还需要引进语料库的优势支持。总地来说，语料库（Corpus）[3]将可分为生语料库（未经处理的）和熟语料库（经过处理，带有标记的）两种。相应地，熟语料库通常需要经由商业购买且价格昂贵，而生语料库却不能提供基于词的语言模型所要求的有效信息。推理至此可得，针对生语料库则需要通过分词（Word_segmentation）算法生成获取研究所需要的特定信息[4]。[JP]

目前，中文分词算法的核心类别可大致分为字符匹配[5]、理解法[6]和统计法。使用一个性能优良的分词算法即能以更少的资源建立信息高度准确的语言模型，而这样的语言模型就可以大大提升输入法的用户体验，同时也将进一步减少用户的输入成本[7]。

另外，拼音流的切分算法是音-字转换的前提，快速准确的切分是后续查词、解码的实现关键。而音-字转换部分[8]则决定着整个输入法的单词转化的时间成本。综上所述，为了完成整句匹配的功能，输入法将在基于词的N-gram语言模型的研发过程后，以单音节序列建立有向无环词图，并将问题转化为求解k-best问题。此后，对于k-best问题，本文还将重点对比改进Dijkstra算法、基于DP[9]的算法以及本文所用的基于A*的求解算法[10]。

1关键技术

[BT5]1.1N-gram语言模型

N-gram模型是大词汇连续语音识别中常用的一种语言模型[11]。对于中文而言，可称其为汉语语言模型（CLM，Chinese Language Model）。CLM利用上下文相邻词间的搭配信息，可以计算出具有最大概率的句子，从而实现到汉字的自动转换，且无需用户手动选择，高效解决了许多汉字对应一个相同拼音的重码问题。

N-gram模型是基于这样一种假设，第n个词的出现只与前面的n-1个词相关，而与其他任何词都不相关，整句的概率就是各个词出现概率的乘积。每个词的概率都可以通过从语料库中直接统计n个词出现的次数而最终得到。依据该假设，可给出该模型的概率表示：

由表 1可知，实验选取了2个语料库，训练样本总计选取文本句子共有761 972 个， 中文字符 10 719 630 个。

将选择的样本用于训练N-gram模型，并对as_testing.utf8 语料库处理展开基于N-gram的边界探索法N-boundary 的不同⑹的分词研究。

设计时，将分别选取N=1，2，3，4 ，以此获得迭代分词的实验测试效果。这样，即可确定n-boundary 分词算法中参数N对于生语料库的作用影响，从而选择提取最优参数。

结果指标设定为召回率、准确率和F值。当N=1，2，3，4 时，实验结果中各指标呈现如图5所示。分析图5可知，参数N的选取，将会产生不同颗粒度的切分效果。

从图5中还可以看出，当N=2 时，召回率与准确率最高，F值最大。N=1时，颗粒度偏小，不能得到正确分词；而 N >= 3时，颗粒度偏大，准确率对比 N=1 时虽然有所提高，但召回率却仍颇小；且函数收敛。

而后，在第一步的基础上又基于不同参数进行了二次迭代。文中使用了不同N值作为第一次迭代的对比，对比效果如图6所示。实验发现，通过迭代就能多次控制分词颗粒度，提高分词的准确率，召回率和F值。具体来说，使用4-2 迭代将获得最好的分词效果，而且提高准确率至0.783 5。

综上实验过程可知，本输入法将使用n-boundary 边界探索算法来设计选定二次迭代分词，参数选择为4-2，原理是先用N=4进行大颗粒度的切分，再对处理后的语言模型用N=2实现迭代小颗粒度的切分。

2.2前k优路径选取实验

在构造出词图后，按照切分词之间转移的概率拼凑成短语或句子，然后选取整句的概率大小作为输入法响应词的返回顺序。这样中文输入法就转换成了基本k-best（有向无环图的求k优路径）的问题，针对准确率和耗时为输入法选择A*作为求取前k优路径的算法。实验就准确率和耗时与改进Dijkstra算法和基于DP的算法进行对比，最终验证了A*算法的优越性。