摘 要： 针对正向最大匹配算法的长词丢失、匹配次数较多、歧义字段处理的准确率较低等问题，基于Trie树词典提出了3种正向增字最大匹配算法，分别使用逐词扫描、尾部折半扫描和尾部减一扫描这3种扫描方式采集歧义字段，并建立了一套歧义处理方法。实验结果表明,该3种算法在分词速度和准确率上均有显著提高,错误率降低到了原算法的三分之一以下。当文本规模大于200 MB时，3种正向增字最大匹配算法的分词速度均比原最大匹配算法提高30%以上。

　　关键词： 中文分词；Trie树；逐词扫描；正向增字匹配

　　随着互联网行业的飞速发展，计算机在人们的日常生活中起着越来越大的作用。因此, 中文信息处理技术在我国信息化建设中占据了一个非常重要的地位。而汉语文本中词与词之间却没有明显的分隔标记，是连续的汉字串，因而如何进行汉语分词是中文信息处理中最为基础、最为重要的问题, 是汉语文本自动标注、搜索引擎、机器翻译以及Web 信息处理等核心应用中的关键步骤[1]。随着信息时代数据的急剧膨胀，需要对海量的中文信息进行处理，而基于词典的分词算法因效率高而受到人们的密切关注。

　　本文选取正向最大匹配算法(FMM算法)进行改进研究。在对正向最大匹配算法的众多研究中，参考文献[2]提出了一种改进的FMM算法，提出了动态确定最大词长的匹配算法，提升了效率。参考文献[3] 提出先寻找长度为i(词典中最长词的长度) 的词, 再寻找长度为i-1的词,……, 直到整个句子被切分完毕。参考文献[4]提出根据一个词是否是其他词的前缀来寻找长词并切分和判断是否为组合歧义。参考文献[5]提出了一种改进的FMM分词方法，采用“正向扫描+增字最大匹配(包括跳跃匹配)+词尾歧义检查+归右原则(对连续型交集，需左部结合)”，可以消除某些类型的歧义，提高了切词的精度。

　　本文基于Trie树词典，分别使用逐词扫描、尾部折半扫描、尾部减一扫描3种扫描方法采集歧义字段，对正向增字最大匹配算法进行了研究，并提出了一套歧义处理的机制，相比原FMM算法大大提高了分词速度和准确度。

1 正向最大匹配算法

　　FMM 算法的基本思想是:

　　(1)找出分词词典中最长词条所含的汉字个数，设为MaxLen.

　　(2)读入一句待切分字符串S1，从开始处截取一个长度为MaxLen的字符串W，令W同分词词典中的词条进行匹配。

　　(3)如果没有匹配成功，就从W的尾部减去一个字，继续与词典中词条匹配。

　　(4)重复上述过程，直到匹配成功某一个词条，或者W长度为0为止。

　　(5)如果匹配成功，则把W作为一个词元从S1中切分出去，然后从S1的开始处截取另一个长度为MaxLen的字符串，重复匹配过程，到把句子切分成功为止。

　　正向最大匹配算法存在着关于匹配词长初始值MaxLen的选取问题，这个长度限制是FMM算法在效率与词长之间的一种妥协，如果词长过短，长词就会被切错[5]。如果词长过长，效率又会比较低。

　　另外，FMM算法对交集型歧义字段的处理精度不高。

　　例如以下句子：

　　句子1：“当中华人民共和国成立的时候”。

　　句子2：“处理机器发生的故障”。

　　句子1的切分结果是：“当中/华人/民/共和国/成立/的/时候”，句子2的切分结果是“处理机/器/发生/的/故障”，两个句子的切分都是错误的。

　　参考文献[6]表明语料库中的词主要是短词，可是在FMM分词过程中，必须从字串长词开始匹配，因而在匹配过程中多数匹配操作都是无意义的，降低了分词的速度。

　　针对以上问题，采取了正向增字最大匹配算法，利用Trie树词典的查询机制进行增字查询，避免了设置最大词长的问题，减少了冗余匹配。

　　为了提高歧义处理的精度，分别采用逐词扫描、尾部折半扫描、尾部减一扫描3种方法采集歧义字段，并建立了一套歧义处理的机制，大大提高了分词的准确度。

2 逐词扫描的正向增字最大匹配算法

　　2.1 逐词扫描的正向增字最大匹配算法

　　逐词扫描的正向增字最大匹配算法的基本思想是：先根据汉语标点符号把汉语句子切分为短句，然后再逐字向后推进，对每一个字进行增字最大匹配，得出以该字为首的最长词元，然后后移一字重新开始匹配新字符串，并对前后两词元判断是否存在歧义字段，如有歧义则对歧义进行处理。

　　算法基本过程如下：

　　输入：待切分字符串N1N2N3…Nn （N1为字）

　　输出：分词之后的词串，词之间用“/”间隔

　　算法基本过程：

　　(1)对N1进行正向增字最大匹配，取得以该字为首的最长词元。即：先取一字N1，在词典中查找N1，若成词则保存为词元，若为词前缀则再取一字N1N2在词典中匹配，重复此过程，直到N1N2…Ni既不成词也不为词前缀为止，则最后保存的词元即为以N1为首的最长词元；

　　(2)指针后移一字，对N2进行正向增字最大匹配，取得以N2为首的最长词元；

　　(3)判断两个词元是否存在歧义字段，若有则对其进行歧义处理；

　　(4)指针后移一字，重复上述过程。

　　例如，对于句子“当中华人民共和国成立的时候”，该算法先后切分出以下词元：“当中”“中华人民共和国”“华人”“人民”“共和国”“成立”“时候”，经歧义处理后得到最后结果：“当/中华人民共和国/成立/的/时候”。显然比FMM算法准确，而且匹配次数更少。

　　该算法使用逐词扫描，在成功匹配出词元之后保存当前词元及词长等信息，并从词首的下一字进行下次匹配，切分出了字符串中所有可以匹配的词元，能识别所有的交集歧义字段，大大提高了分词精度。

　　2.2 尾部折半扫描的正向增字最大匹配算法

　　对于逐词扫描方法，如果存在长词，就可能出现冗余匹配。例如对于“中华人民共和国”，“华人”“人民”“共和国”都是不必要切分出来的，造成了时间的浪费。因此本文提出了一种“尾部折半”的扫描方式来减少冗余。

　　该方法与逐词扫描方法的区别是：对字符串中某一个字进行增字最大匹配后，得出以该字为首的最长词元的长度n，然后将指针后移n/2个字，重新开始匹配。

　　该方法相比逐词扫描方法减少了匹配次数，提高了分词速度，且基本没有降低精度。

　　2.3 尾部减一扫描的正向增字最大匹配算法

　　为了更进一步提高分词速度，本文提出了尾部减一扫描的方法。

　　该方法与前两种方法的区别是：对字符串中某一个字进行增字最大匹配后，得出以该字为首的最长词元的长度n，然后将指针后移n-1个字，即来到该词元尾部最后一个字的位置，重新开始匹配。

　　该方法进一步减少了匹配次数，但没有考虑到链长为2及以上的歧义字段，在一定程度上使准确率稍有降低。

　　2.4 歧义处理

　　对占歧义字段85%以上的交集型歧义字段的研究已成为分词方法中研究的重点，歧义字段的切分是这一转换过程的主要困难之一[7]。又由统计可知，交集型歧义字段中，链长为1和2的歧义字段合计占到了歧义字段的97.61%，字段出现次数的95.41%[8]。

　　因此本文对链长为1,2,3的交集型歧义字段进行处理，设定消歧规则如下：

　　规则1：尽量不切分长词；

　　规则2：尽量不造成单字；

　　规则3：如果两词元权重相同，则逆向最大匹配优先；

　　规则4：如果3个词元相互有交集型歧义字段，则将中间词元拆分给前后两个词元；

　　规则5：对于链长为2、3的交集型歧义字段，将歧义部分划分给前词元。

　　根据以上规则，本文消歧算法如下：

　　输入：一组未消歧的词元L1，L2，…，Ln（有前后位置的区别）

　　输出：一组消歧后的词元组成的词串，词之间用“/”间隔。

　　算法基本过程：

　　(1)取出最前面的两个词元L1、L2，设定初始权重为词元长度，获取它们的交集型歧义字段的链长N；

　　(2)若链长为0，则无歧义，将前词元L1存入最终结果集，后词元L2继续与下一个词元L3比较；

　　(3)如果L1权重大于L2，假如将歧义字段分给L1会造成L2只剩单字、且不能与后字连接成词的话，判断减去歧义字段后能否成词，若能成词，则将歧义字段分给L2，否则歧义字段分给L1；

　　(4)如果L1权重小于L2，假如将歧义字段分给L2会造成L1单字，判断减去歧义字段后能否成词，若能成词，则将歧义字段分给L1，否则将歧义字段分给L2；

　　(5)如果L1权重等于L2，分3种情况讨论：① 歧义字段链长为1，判断L2与后一个词元L3是否有歧义，若有则将L2拆分给L1和L3，且L3权重加一，否则将歧义字段分给L2；② 歧义字段链长为2，且L2拆分后能成词，则将歧义字段划分给L1，否则分给L2；③ 歧义字段链长为3，且L2拆分后能成词，则将歧义字段划分给L1，否则分给L2。划分完毕后将L1存入最终结果集；

　　(6)重复以上过程，直到将所有词元都处理完毕。

　　该算法有效地避免了生成单字，例如对于句子“处理机器发生的故障”中的前两个词元“处理机”“机器”，它们的歧义字段为“机”，如果将“机”划分给前词元，则后词元只剩下单字“器”，且不能与后字成词。而如果将“机”划分给后词元，前词元剩下两字“处理”可以单独成词。因此本算法将“处理机器”切分为“处理/机器”，比正向最大匹配算法要准确。

3 实验结果及分析

　　3.1 实验环境描述

　　实验平台：Inter(R) Core(TM) i5-3470四核四线程3.20 GHz处理器；三级缓存6 MB；4 GB内存；编译环境为Java7.0版本，编译器是Eclipse Java EE IDE。

　　词典：SCWS简体中文分词词典，共有284 726个词条，词典大小2.75 MB，最长词条的长度为18。

　　正向最大匹配算法MaxLen选取：虽然最长词条长度为18，但为了分词速度不太慢，这里取MaxLen为9。

　　文本：分别选取5 MB，20 MB，50 MB，100 MMB，200 MB文本进行实验，多次重复实验后取平均值。文本编码方式为utf-8。

　　测试性能指标：不同文本规模下的分词速度；分词的准确率。

　　3.2 实验结果

　　3.2.1 分词速度

　　采用逐词扫描的正向增字最大匹配算法、尾部折半扫描的正向增字最大匹配算法、尾部减一扫描的正向增字最大匹配算法、FMM算法4种算法进行对比实验。

　　图1为在不同文本规模时，4组算法分词所耗时间对比图。4组算法对照运行时，分词词典和文本相同。

　　4组算法对比得出，3种正向增字最大匹配算法与原FMM算法相比，在分词速度上均有明显提升。其中逐词扫描、尾部折半扫描、尾部减一扫描这3种方法的速度依次提高。

　　当文本大小超过20 MB时，3种正向增字最大匹配算法均比原FMM算法速度提升20%以上。随着数据量的增大，速度的提升更加明显。当文本规模大于200 MB时，3种正向增字最大匹配算法均比FMM算法提高30%以上。

　　3.2.2 分词的准确率

　　本文用准确率和错误切分率来计算分词的准确度。

　　准确率的计算公式为：

　　错误切分率的计算公式为：

　　对1998年1月的人民日报的第一篇文章《迈向充满希望的新世纪》的正文进行中文分词，将北大标注的经人工分词的1998年1月的人民日报语料作为结果检验语料。由于词库的区别，如果将短词合并为长词也视为正确。 实验结果如表1所示。

　　对比得知，3种正向增字最大匹配算法的正确率均高于原FMM算法，错误切分率降低到了FMM算法的1/3以下。其中尾部减一扫描算法由于没考虑到链长为2以上的交集型歧义字段，正确率比其他两种方法略低一些。

　　本文在经典的FMM算法的基础上，提出了3种不同扫描方式的正向增字最大匹配算法，显著提高了分词速度和准确率。实验证明，当文本规模大于200 MB时，3种正向增字最大匹配算法均比FMM算法提高30%以上。综合分词速度和准确率，尾部折半扫描的正向增字最大匹配算法最优。下一步工作将考虑未登录词识别、数量词合并的问题。

参考文献

　　[1] 周程远，朱敏，杨云．基于词典的中文分词算法研究[J]．计算机与数字工程，2009, 37(3)：68-71．

　　[2] 王瑞雷，栾静，潘晓花，等．一种改进的中文分词正向最大匹配算法[J]．计算机应用与软件，2011，28(3)：195-197．

　　[3] 郭辉, 苏中义, 王文，等. 一种改进的MM分词算法[ J] . 微型电脑应用,2002, 18(1): 13-15.

　　[4] 杨宪泽. 机器翻译的词处理研究[J] . 计算机工程与科学, 2009, 31(5): 156-158.

　　[5] 王惠仙, 龙华.基于改进的正向最大匹配中文分词算法研究[J].贵州大学学报（自然科学版）,2011,28(5): 112-115

　　[6] 金春辉，金顺福．基于优化最大匹配与统计结合的汉语分词方法[J].燕山大学学报，2009，33(2): 124-129．

　　[7] 闫引堂，周晓强．交集型歧义字段切分方法研究[J]．情报学报，2000，19(6): 637-643．

　　[8] 翟风文，赫枫龄，左万利．字典与统计相结合的中文分词方法[J].小型微型计算机系统，2006，27(9): 1766-1771．