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

72

福建电脑2011年第4期

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

王希杰

（安阳师范学院河南安阳455000）

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

【关键词】：中文分词正向最大匹配MFC作为中文信息处理的基础，汉语自动分词是智能化中文信息处理的关键，因为"在中文信息处理中，凡是涉及句法、语义等研究项目都要以词为基本单位[1，2]。而中文并不像英文那样，词之间有着自然的分割，汉语语句只是连续的字符串，语句中的"词"与"词"之间没有明显的分割符号，再加上汉语中"未登录词"的大量存在和"歧义词"对分词精度的影响，使得汉语的自动分词成了制约中文信息处理的"瓶颈"。因此分词作为自然语言处理的热点和难点，汉语的自动分词一直以来备受国内众多学者的关注。本文在研究"机械匹配算法"[2]的基础上，利用MFC对正向最大匹配算法进行了实现，并对该系统进行了分析，提出了改进的意见，为下一步更加深入的研究分词提供了一个实验的平台。1、"机械匹配"算法和正向最大匹配

"机械匹配"算法可以分为增字匹配和减字匹配，增字匹配是从单个字符开始逐次增加词中字符的个数，直到匹配成功；而减字匹配遵循"长词优先"原则，首先取"最长"字符串进行匹配，若匹配不成功则减掉一个汉字（两英文字符），重复以上过程直到匹配成功。按照匹配过程中匹配的方向，"机械匹配"可以分为正向匹配[3]、逆向匹配和双向匹配，这些算法的基本思想类似，本文以减字匹配为例进行说明。其基本思路是在计算机中存放一个已知的词表（词典），然后从被切分的语料中，按照给定的方向顺序截取一个定长的字符串（通常为6至8个汉字，这个字符串的长度叫做最大词长，记作maxlen），把这个长度为maxlen的字符串与词表中的词相匹配，若匹配成功，则可确定这个字符串为"词"，然后将字符指针向后移动maxlen个汉字继续进行匹配；否则则把该字符串逐次减一"字"（两个英文字符），再与词表中的词进行匹配，直到成功为止[4,5]。其流程图如图1所示。下面例子简单说明了此算法的执行过程。

例：设sr="我们是中华人民共和国的公民"，maxlen=8，则执行过程如下：

1）取w="我们是中"；

2）查字典判断w中的字符串不是词；3）从w右边减掉一个字后w="我们是"；

4）判断w中的字串不是词；

5）从w右边减掉一个字后w="我们"；

6）判断w中的字符串是一个词，则输出到st中，st="我们/"。

2.最大正向匹配算法的VC++实现

根据以上对最大正向匹配算法的分析，利用VisualC++中的MFC对最大正向匹配算法进行了实现，以下

是程序中实现正向最大匹配的关键代码：

#definemaxlen8//最大词长为8字符（即4个汉字）#defineSeparator""//词界标记为空格CMyDictionaryMyDict;//定义分词词典

CStringSegmentHzStrMM(CStringsr)//对sr进行正向最大匹配分词{CStringst="";//用于存放分词结果

while(!sr.IsEmpty())//源串不空则循环分词{

intlen=sr.GetLength();//取源串的长度

if(len>maxlen)//如果源串串长度大于最大词长

len=maxlen;

CStringw=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());

returnst;}

}

3、实验分析：

系统开发完成后，我们利用从互联网上随机下载的数据进行了测试，从测试结果来看，基于"机械匹配"的分词方法确实存在着分词准确率较低的问题。分析此问题，我认为主要有以下原因：

1）词典对分词精度的影响：由于"机械匹配方法"是直接取一个字串和词典中的"词条"进行匹配，匹配成功就认为是一个词，匹配失败则认为不是一个"词"，因此在此类方法中，词典对分词的精度影响是最大和最直接的。但是由于汉语中"词"的灵活性和汉语中大量未登录词的存在，因此要建立一个完备的词典基本上是不可能的事情[6]。

（下转第71页）

2011年第4期福建电脑

71

第三，对于利用用户名字段进行增益Gain（用户名），利用公式（4），考虑坠1=0

E（用户名）=（4/8+0）*I（s11，s21）+（4/8+0）*I（s12，s22）=0.487

Gain（用户名）=I(s1，s2)-E（年龄）=0.1385

考虑密码坠2=0.3，验证码坠3=0.3同理可得，Gain（密码）=0.0574，Gain（验证码）=0.0574

第四，找出最大的字段信息增益:Gain（用户名），所以以"用户名"字段作为节点,并根据用户名的2个不同的取值产生2个不同的分支。

第五，对分支重复以上步骤建立新的分支，最后得出分类树如图2所示。

最后，8组用例测试用例被简化为4组，如图2所示。

表1测试结果对比表

从表1中可以分析得到，在基本达到同样覆盖率的条件下，使用的测试用例较少，并且耗费的时间也比较短。尤其是针对具有较多分支的web服务接口，测试用例的减少更为明显，有效地提高了测试效率。5、结束语

实验证明本文提出的基于改进的ID3算法的测试用例生成策略，结合Nunit进行对web服务接口的测试是一种有效的单元测试手段，并且对嵌入式web服务的自动化单元测试具有显著的指导意义。

参考文献：

图2生成的登录模块接口决策树

4、结合接口测试工具NUnit实验

实验利用以上提出的ID3算法生成测试用例，然后结合Nunit[5]进行单元测试。以下表格是使用这种方法前后对某项目web服务接口进行单元测试的对比表格(见表1)。

[1]李毅,顾健,顾铁军.面向服务软件架构中的软件测试[C].上海:全国计算机安全学术交流会论文集

[2]杨利利,李必信.Web服务测试问题综述[J].计算机科学,2008.Vol35.No9

[3]夏火松.数据仓库与数据挖掘技术[M].北京:科学出版社,2004.[4]邹永贵,范程华.基于属性重要度的ID3改进算法[J].计算机应用,June2008.Vol28

[5]http://doc.guandang.net/[OL]

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（上接第72页）

2）最大字串长度对分词的影响：为了保证分词系可能存在着不尽如人意的地方，但对某一专业领域来统的分词效率，一般情况下基于"机械匹配"的方法中，讲，建立该领域的专用词典利用"机械匹配"算法进行

对最大词的长度都有一个初始化的长度，但这一长度对分词精度也会有影响。比如设定最大词长为八，则在分词时"中华人民共和国"将不会最为一个词来处理。

3）"未登录"[7,8]词对分词精度的影响："未登录"词主要指汉语中的人名、地名、机构名、组织名，由于这类词在汉语中具有更大的灵活性，而且随着时间的推移， …… 此处隐藏：2305字，全部文档内容请下载后查看。喜欢就下载吧 ……