首页 > 建筑理工 > 数学 >

最大正向匹配分词算法的VC++实现

作者:王希杰更新时间:2011-01-23 15:23 点击:次

【论文发表关健词】中文分词；正向最大匹配；MFC

【职称论文摘要】

做为最直接的分词思路，最大匹配具有直观、实现简单等优点，但也存在着精度低的致命缺点。本文对正向匹配算法做了实现和分析，为该方法的进一步改进打下了基础。

　作为中文信息处理的基础，汉语自动分词是智能化中文信息处理的关键，因为“在中文信息处理中，凡是涉及句法、语义等研究项目都要以词为基本单位[1，2]。而中文并不像英文那样，词之间有着自然的分割，汉语语句只是连续的字符串，语句中的“词”与“词”之间没有明显的分割符号，再加上汉语中“未登录词”的大量存在和“歧义词”对分词精度的影响，使得汉语的自动分词成了制约中文信息处理的“瓶颈”。因此分词作为自然语言处理的热点和难点，汉语的自动分词一直以来备受国内众多学者的关注。本文在研究“机械匹配算法”[2]的基础上，利用MFC对正向最大匹配算法进行了实现，并对该系统进行了分析，提出了改进的意见，为下一步更加深入的研究分词提供了一个实验的平台。
　　一、“机械匹配”算法和正向最大匹配
　　“机械匹配”算法可以分为增字匹配和减字匹配，增字匹配是从单个字符开始逐次增加词中字符的个数，直到匹配成功；而减字匹配遵循“长词优先”原则，首先取“最长“字符串进行匹配，若匹配不成功则减掉一个汉字（两英文字符），重复以上过程直到匹配成功。按照匹配过程中匹配的方向，“机械匹配”可以分为正向匹配[3]、逆向匹配和双向匹配，这些算法的基本思想类似，本文以减字匹配为例进行说明。其基本思路是在计算机中存放一个已知的词表（词典），然后从被切分的语料中，按照给定的方向顺序截取一个定长的字符串（通常为6至8个汉字，这个字符串的长度叫做最大词长，记作maxlen），把这个长度为maxlen的字符串与词表中的词相匹配，若匹配成功，则可确定这个字符串为“词”，然后将字符指针向后移动maxlen个汉字继续进行匹配；否则则把该字符串逐次减一“字”（两个英文字符），再与词表中的词进行匹配，直到成功为止。
　　二、最大正向匹配算法的VC++实现
　　根据以上对最大正向匹配算法的分析，利用Visual C++中的MFC对最大正向匹配算法进行了实现，以下是程序中实现正向最大匹配的关键代码：
　　#define maxlen8//最大词长为8字符（即4个汉字）
　　#define Separator" "//词界标记为空格
　　CMyDictionary MyDict;//定义分词词典
　　CString SegmentHzStrMM (CString sr)//对sr进行正向最大匹配分词
　　{CString st=""; //用于存放分词结果
　　 while(!sr.IsEmpty())//源串不空则循环分词
　　{int len=sr.GetLength();//取源串的长度
　　if (len>maxlen)//如果源串串长度大于最大词长
　　len=maxlen;
　　CString w=sr.Left(len);//正向最大匹配，从左边取出长度为len的子串
　　 intn=MyDict.match(w);//在词典中进行匹配，返回値为0或1
　　while(len>2&&n==0)//不是词且字串长度大于一个汉字
　　{len-=2;//从候选词右边减掉一个汉字，继续进行匹配
　　w=w.Left(len);
　　 n=MyDict.match(w);}
　　 st+=w+Separator;//将匹配得到的词连同词界标记加到输出串末尾
　　 sr=sr.Mid(w.GetLength());}
　　 return st;}
　　三、实验分析
　　系统开发完成后，我们利用从互联网上随机下载的数据进行了测试，从测试结果来看，基于“机械匹配”的分词方法确实存在着分词准确率较低的问题。分析此问题，我认为主要有以下原因：
　　（一）词典对分词精度的影响：由于“机械匹配方法”是直接取一个字串和词典中的“词条”进行匹配，匹配成功就认为是一个词，匹配失败则认为不是一个“词”，因此在此类方法中，词典对分词的精度影响是最大和最直接的。但是由于汉语中“词”的灵活性和汉语中大量未登录词的存在，因此要建立一个完备的词典基本上是不可能的事情。
　　（二）最大字串长度对分词的影响：为了保证分词系统的分词效率，一般情况下基于“机械匹配”的方法中，对最大词的长度都有一个初始化的长度，但这一长度对分词精度也会有影响。比如设定最大词长为八，则在分词时“中华人民共和国”将不会最为一个词来处理。
　　（三）“未登录”词对分词精度的影响：“未登录”词主要指汉语中的人名、地名、机构名、组织名，由于这类词在汉语中具有更大的灵活性，而且随着时间的推移，“未登录”词词条和的数目也会产生变化，因此在词典中不可能也没有办法收录全部的“未登录”词，所以“未登录”词的存在会对该方法产生很大的影响[1]。
　　（四）“歧义”词对分词精度的影响：歧义可分为交集型歧义、组合型歧义和混合型歧义，比如“不同意见”可以切分为“不同意见”，也可分成“不同意见”。而由于自然语言本身存在的二义性，使得“歧义”对分词精度也会产生很大的影响。但这中情况在其他的分词放过中也会存在，并不是“机械匹配”算法独有的问题。
　　四、总结
　　虽然“机械匹配”方法存在着一定的缺陷，但是此方法却具有不需要训练模型、匹配速度快、实现简单等优点，因此我们有理由认为作为通用的分词算法该方法可能存在着不尽如人意的地方，但对某一专业领域来讲，建立该领域的专用词典利用“机械匹配”算法进行分词还是一个值得考虑的思路，而这也正是我们下一步要努力的目标，也是我们本次试验的目的。
　　
　　参考文献：
　　[1]黄昌宁.中文信息处理中的分词问题[J].语言文字应用,1997,(1):72-78.
　　[2]殷建平.汉语自动分词方法[J].计算机工程与科学,1998,20,(3):60-66.
　　[3]王艳,元昌安.基于VC++/MFC的中文自动分词算法及其软件的实现[J].广西师范学院学报,2008,25,(3):104-108.