论文部分内容阅读
摘要：本文首先从中文输入法应用的角度出发，在阐述了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*算法的优越性。 图7给出了3种关于求解前k优路径研究算法在不同点数的有向无环图中求取准确率的示意图，横坐标代表有向无环图点的数量，纵坐标代表准确率的百分比。图7表明，仅从准确率的角度来说，3种算法都能满足要求，在含普通点数的有向环图中准确率可以达到100%。
图8是3种求解前k优路径算法随着有向无环图点的数量的递增所显示的消耗时间示意图，横坐标代表有向无环图所包含的点的个数，纵坐标代表求取前k优路径所消耗的时间（以ms为单位）。本实验选用图是在确保其是有向无环图的前提下随机生成的，由图8对比试验结果可知这3种算法在对前k优路径的求取中，拟用的A*算法效率较高。
在此，针对本次设计的中文输入法选用的A*算法进行极限测试，验证算法的高效可用程度，即当词图较为复杂的情况下算法依然能保持较高的处理效率。测试结果如图9所示。图9中，横坐标代表有向无环图点的数目，纵坐标代表求前k短路所用的时间（以ms为单位）。
[JP2]由实验结果可知，研究中基于A*的求解k-best的算法准确率高达百分之百，因而能够达到拼音输入法对前k优路径的要求。此外，又经过有向无环图点数较多时的极限测试可以进一步看出基于A*的k-best的求解算法具有较高的稳定性，因此在输入法的开发设计中采用了基于A*求解k-best的算法。[JP]
3结束语
基于N-gram模型的中文分词前k优算法对于中文拼音输入法的各个功能实现展开了全面的研究，较为细致地论述[CM（26]了中文输入法实现过程中需要语言模型及算法，具有较高的[CM）][LL]
实用性和准确性，对中文拼音输入法的深入研究奠定了良好基础。而且，虽然本文是针对中文拼音输入法给出的研究设计，但是对于其他的拼音文字语言，如日文、泰文等，同样具有重要参考价值。
参考文献：
[1]宗成庆. 统计自然语言处理[M]. 北京： 清华大学出版社， 2008：14-143.
[2]王希杰. 最大正向匹配分词算法的VC 实现[J]. 福建电脑， 2011（4）：71-72.
[3]WOLK K， MARASEK K. A sentence meaning based alignment method for parallel text corpora preparation[J]. Advances in Intelligent Systems and Computing，2014， 275（275）：229-237.
[4][JP3]张俊. 基于神经网络的拼音汉字转换[D]. 南京：南京理工大学，2004.[JP]
[5]刘刚，丁晓青，彭良瑞，等. 多知识综合判决的字符切分算法[J]. 计算机工程与应用，2002（17）：59-61，72.
[6]崔刚. 从语言处理的复杂性与高效性看联结主义[J]. 外语与外语教学，2007（5）：1-4，41.
[7]徐志明， 王曉龙， 姜守旭. 一种语句级汉字输入技术的研究[J]. 高技术通讯， 2000（1）：51-55.
[8] 邹荣. 大词汇量连续语音识别系统中统计语言模型的研究[D]. 北京：北京邮电大学， 2006.
[9]（美）CORMEN T H， LEISERSON C E， RIVEST R L，等著. 算法导论[M]. 殷建平，徐云，王刚，等译. 北京：机械工业出版社， 2013：78-301.
[10]吴军. 数学之美[M]. 北京：人民邮电出版社，2012：154-208.
[11]FIGUEROA A， ATKINSON J. Contextual language models for ranking answers to natural language definition questions[J].Computational Intelligence， 2012，28（4）：528-548.
[12]（美）MANNING C D，（德）SCHTZEH， H著. 统计自然语言处理基础[M]. 苑春法，李庆中，王 昀，等译. 北京：电子工业出版社，2005：37-111.
关键词：中文输入法； 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*算法的优越性。 图7给出了3种关于求解前k优路径研究算法在不同点数的有向无环图中求取准确率的示意图，横坐标代表有向无环图点的数量，纵坐标代表准确率的百分比。图7表明，仅从准确率的角度来说，3种算法都能满足要求，在含普通点数的有向环图中准确率可以达到100%。
图8是3种求解前k优路径算法随着有向无环图点的数量的递增所显示的消耗时间示意图，横坐标代表有向无环图所包含的点的个数，纵坐标代表求取前k优路径所消耗的时间（以ms为单位）。本实验选用图是在确保其是有向无环图的前提下随机生成的，由图8对比试验结果可知这3种算法在对前k优路径的求取中，拟用的A*算法效率较高。
在此，针对本次设计的中文输入法选用的A*算法进行极限测试，验证算法的高效可用程度，即当词图较为复杂的情况下算法依然能保持较高的处理效率。测试结果如图9所示。图9中，横坐标代表有向无环图点的数目，纵坐标代表求前k短路所用的时间（以ms为单位）。
[JP2]由实验结果可知，研究中基于A*的求解k-best的算法准确率高达百分之百，因而能够达到拼音输入法对前k优路径的要求。此外，又经过有向无环图点数较多时的极限测试可以进一步看出基于A*的k-best的求解算法具有较高的稳定性，因此在输入法的开发设计中采用了基于A*求解k-best的算法。[JP]
3结束语
基于N-gram模型的中文分词前k优算法对于中文拼音输入法的各个功能实现展开了全面的研究，较为细致地论述[CM（26]了中文输入法实现过程中需要语言模型及算法，具有较高的[CM）][LL]
实用性和准确性，对中文拼音输入法的深入研究奠定了良好基础。而且，虽然本文是针对中文拼音输入法给出的研究设计，但是对于其他的拼音文字语言，如日文、泰文等，同样具有重要参考价值。
参考文献：
[1]宗成庆. 统计自然语言处理[M]. 北京： 清华大学出版社， 2008：14-143.
[2]王希杰. 最大正向匹配分词算法的VC 实现[J]. 福建电脑， 2011（4）：71-72.
[3]WOLK K， MARASEK K. A sentence meaning based alignment method for parallel text corpora preparation[J]. Advances in Intelligent Systems and Computing，2014， 275（275）：229-237.
[4][JP3]张俊. 基于神经网络的拼音汉字转换[D]. 南京：南京理工大学，2004.[JP]
[5]刘刚，丁晓青，彭良瑞，等. 多知识综合判决的字符切分算法[J]. 计算机工程与应用，2002（17）：59-61，72.
[6]崔刚. 从语言处理的复杂性与高效性看联结主义[J]. 外语与外语教学，2007（5）：1-4，41.
[7]徐志明， 王曉龙， 姜守旭. 一种语句级汉字输入技术的研究[J]. 高技术通讯， 2000（1）：51-55.
[8] 邹荣. 大词汇量连续语音识别系统中统计语言模型的研究[D]. 北京：北京邮电大学， 2006.
[9]（美）CORMEN T H， LEISERSON C E， RIVEST R L，等著. 算法导论[M]. 殷建平，徐云，王刚，等译. 北京：机械工业出版社， 2013：78-301.
[10]吴军. 数学之美[M]. 北京：人民邮电出版社，2012：154-208.
[11]FIGUEROA A， ATKINSON J. Contextual language models for ranking answers to natural language definition questions[J].Computational Intelligence， 2012，28（4）：528-548.
[12]（美）MANNING C D，（德）SCHTZEH， H著. 统计自然语言处理基础[M]. 苑春法，李庆中，王 昀，等译. 北京：电子工业出版社，2005：37-111.