基于二字词检测位图表的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).