基于二字词检测位图表的MM自动分词算法

摘　要：中文自动分词是中文信息处理中的重要步骤，它是机器翻译、计算机人机接口等诸多中文信息应用领域的基础，因此，对其研究具有重要的理论和现实意义，利用最大匹配法（MM）进行自动分词经实践证明是有效的、可行的汉语分词法。

关键词：自动分词；最大匹配法；二字词函数
一、汉语自动分词及分词评价系统简介
　　汉语自动分词是对汉语文本进行自动分析的第一个步骤。词是最小的、能独立活动的、有意义的语言成分。分词体现了汉语与英语的显著的不同。英语文本是小字符集上的已充分分隔开的词串，而汉语文本是大字符集上的连续字串。把连续的字串分隔成词串，就是分词系统需要做的工作。可以这样设想汉语自动分词过程的困难：如果把某个英语文本中的所有空格符都去掉，然后让计算机自动恢复文本中原有的空格符，这就是词的识别过程，这个过程需要解决的首要问题就是歧义字段的切分问题。
　　分词可以由人工完成，也可以由计算机根据事先编好的程序来自动完成。人工分词工作量大，难以处理大规模语料。计算机自动分词速度快，一致性好，但是难以运用人工的各种分词知识，一般来说分词结果的准确率要低于人工分词。现在通常是先由计算机自动分词，然后辅之以人工校对。
　　分词算法的好坏，分词系统性能的高低采用三个指标评价：正确率、召回率、F值。
二、MM分词模型
　　MM即最大匹配法（Maximum Mateh Method）的缩写形式，是目前书面汉语自动分词算法中的典型算法。最大匹配法（MM）在一定程度上模拟了人工分词的心理过程。所谓“最大匹配”，就是尽可能地用最长的词来匹配句中的汉字串，从而使得切出来的词尽可能长，词的数量尽可能少。
　　对于MM分词方法，可以建立一个一般的模型，形式地表示为：ASM(d，a，m)，即Automatic Segmentation Model。其中，?d：匹配方向，+1表示正向，-1表示逆向；?a：每次匹配失败后增加/减少字串长度（字符数），+1为增字，-1为减字；?m：最大/最小匹配标志，+1为最大匹配，-1为最小匹配。
三、基于二字词检测位图表的MM自动分词算法描述
　　根据汉语中二字词较多的特点，在算法上增加二字词检测位图表对分词词典数据结构优化，实现快速判断二字词与匹配词典分词交叉进行的分词算法。
　　如前所述，首先建立的分词模型包括ASM(+，+，+)，即正向增字最大匹配法(FMM方法)模型，还包括ASM(-，+，+)，即反向增字最大匹配法(RMM方法)模型。FMM和RMM双向匹配可以检测出大多数交集型歧义字段。
　　设有汉字串S，长度为n，改进最大匹配算法的伪代码描述如下：
　　CurPos<-0;            //设置当前处理位置为字符串起始处
　　WordLen<-1;          //设置词的长度为1
　　While(CurPos+WordLen<=n)
　　{
　　  If(WordLen==1)
　　  MayBeWord=FindWord(S,CurPos,WordLen);    //匹配单字词
　　  Else
　　    {
　　      If(WordLen==2)
　　      MayBeWord=Check2CWord(S,CurPos,WordLen);  //判断二字词
　　      Else
　　      MayBeWord=FindWord(S,CurPos,WordLen);        //匹配
　　      }
　　    If(MayBeWord)
　　        {
　　          PushWord(S,CurPos,WordLen);          //保留中间分词结果
　　          WordLen<- WordLen+1
　　          }
　　        Else
　　          {CurPos<- CurPos+1
　　          WordLen<-1;
　　          }
　　    }
　　该算法应用于全切分、正/反向最大匹配算法都是如此。
四、实验结果及结论
　　选取人民日报切分标注语料库PFR1.0作为样本进行实验测试，设调用函数Fnidword匹配一个词需要时间为Tf，调用函数Check2CWord判断一个二字词需要时间为Tc，在PⅢ1GCPU，376M内存以及20G硬盘，操作系统为wnidows2003的实验平台下，通过实验测试得到Tf的平均时间消耗为0.000008秒，Tc的平均时间消耗为0.000002秒，由此可见，调用函数Check2CWord判断二字词比调用函数FindWord匹配词的速度提高75%。由此证明基于二字词检测位图表的MM自动分词算法是进行汉语自动分词的较好方式。
参考文献：
[1]奉国和, 郑伟. 国内中文自动分词技术研究综述[J]. 图书情报工作,2011(2).
[2]刘韬. 设立切分标志法在中文地址自动分词中的改进与应用[J].电脑知识与技术（学术交流）,2009(11).
[3]卢俊之. 分词不一致不同成因的自动识别研究[J].现代语文（语言研究）,2007(11).
[4]萧克曦. 在线英语语料库自动分词和分句的实现[J].电脑知识与技术,2010(28). 本文链接：http://www.qk112.com/lwfw/jsjlw/jisuanjiyingyong/242408.html