实验报告1 双向匹配中文分词
•小组信息
目录
摘要--------------------------------------------------------------------------------------- 1
理论描述--------------------------------------------------------------------------------- 1
算法描述--------------------------------------------------------------------------------- 2
详例描述--------------------------------------------------------------------------------- 3
软件演示--------------------------------------------------------------------------------- 4
总结--------------------------------------------------------------------------------------- 6
•摘要
这次实验的内容是中文分词，现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。
按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。
而我们用到的分词算法是基于字符串的分词方法（又称机械分词方法）中的正向最大匹配算法和逆向匹配算法。
一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。
统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。
•理论描述
中文分词指的是将一个汉字序列切分成一个一个单独的词。
中文分词是文本挖掘的基础，对于输入的一段中文，成功的进行中文分词，可以达到电脑自动识别语句含义的效果。
它是信息提取、信息检索、机器翻译、文本分类、自动文摘、语音识别、文本语音转换、自然语言理解等中文信息处理领域的基础。
双向最大匹配算法是两个算法的集合，主要包括:正向最大匹配算法和逆向最大匹配算法．如果两个算法得到相同的分词结果，那就认为是切分成功，否则，就出现了歧义现象或者是未登录词问题。
正向最大匹配算法：从左到右将待分词文本中的几个连续字符与词表匹配，如果匹配上，则切分出一个词。
逆向最大匹配算法：从右到左将待分词文本中的几个连续字符与词表匹配，如果匹配上，则切分出一个词。
•算法描述
本文实现双向匹配算法，具体算法描述如下：
正向最大匹配算法MM：
//对纯中文句子s1的正向减字最大匹配分词
string CHzSeg::SegmentHzStrMM(CDict &dict,string s1)const
{
string s2="";//保存句子s1的分词结果
while(!s1.empty())
{
unsigned int len=s1.size();
//如果待切分的句子大于最大切分单元
//len=最大切分单元,否则len=句子的长度
if(len>MAX_WORD_LENGTH)
len=MAX_WORD_LENGTH;
//取s1句子最左边长度len为的子句子
string w=s1.substr(0,len);
//判断刚刚取出来的子句子是不是一个词
bool isw=dict.IsWord(w);
//当w中至少有一个中文字&&不能构成字的时候,减去最右边的一个中文字while(len>2&&isw==false)
{
///减去最右边的一个中文字
len-=2;
w=w.substr(0,len);
//再次判断减字后的w是不是构成一个词
isw=dict.IsWord(w);
}
s2+=w+SEPARATOR;
s1=s1.substr(w.size());
}//end while
return s2;
}
逆向最大匹配算法RMM：
//对纯中文句子s1的逆向减字最大匹配分词
string CHzSeg::SegmentHzStrRMM(CDict &dict,string s1)const
{
string s2="";//保存句子s1的分词结果
while(!s1.empty())
{
unsigned int len=s1.size();
//如果待切分的句子大于最大切分单元
//len=最大切分单元,否则len=句子的长度
if(len>MAX_WORD_LENGTH)
len=MAX_WORD_LENGTH;
//取s1句子最右边长度len为的子句子
string w=s1.substr(s1.length()-len,len);
//判断刚刚取出来的子句子是不是一个词
bool isw=dict.IsWord(w);
//当w中至少有一个中文字&&不能构成字的时候,减去最左边的一个中文字while(len>2&&isw==false)
{
//减去最左边的一个中文字
len-=2;
w=s1.substr(s1.length()-len,len);
//再次判断减字后的w是不是构成一个词
isw=dict.IsWord(w);
}
w=w+SEPARATOR;
s2=w+s2;
//分出一个词后的s1
s1=s1.substr(0,s1.length()-len);
}
return s2;
}
•详例描述：
逆向最大匹配思想是从右向左切分，以“对外经济技术合作与交流不断扩大”为例，详细描述算法如下：
输入例句：S1=“对外经济技术合作与交流不断扩大”；
定义：最大词长MaxLen = 6；S2= “”；分隔符= “/ ”；
逆向减字最大匹配分词算法过程如下：
（1）S2=“”；S1不为空，从S1右边取出候选子串W=“断扩大”；
（2）查词表，W不在词表中，将W最左边一个字去掉，得到W=“扩大”；（3）查词表，“扩大”在词表中，将W加入到S2中，S2=“扩大/ ”，并将W 从S1中去掉，此时S1=“对外经济技术合作与交流不断”；
（4）S1不为空，于是从S1左边取出候选子串W=“流不断”；
（5）查词表，W不在词表中，将W最左边一个字去掉，得到W=“不断”；（6）查词表，“不断”在词表中，将W加入到S2中，S2=“不断/ 扩大/ ”，并将W从S1中去掉，此时S1=“对外经济技术合作与交流”；
（7）S1不为空，于是从S1左边取出候选子串W=“与交流”；
（8）查词表，W不在词表中，将W最左边一个字去掉，得到W=“交流”；（9）查词表，“交流”在词表中，将W加入到S2中，S2=“交流/ 不断/ 扩大/ ”，并将W从S1中去掉，此时S1=“对外经济技术合作与”；
（10）S1不为空，于是从S1左边取出候选子串W=“合作与”；
（11）查词表，W不在词表中，将W最左边一个字去掉，得到W=“作与”；（12）查词表，W不在词表中，将W最左边一个字去掉，得到W=“与”；（13）查词表，“与”在词表中，将W加入到S2中，S2=“与/ 交流/ 不断/ 扩大/ ”，并将W从S1中去掉，此时S1=“对外经济技术合作”；
（14）S1不为空，于是从S1左边取出候选子串W=“术合作”；
（15）查词表，W不在词表中，将W最左边一个字去掉，得到W=“合作”；（16）查词表，“交流”在词表中，将W加入到S2中，S2=“合作/ 与/ 交流/ 不断/ 扩大/ ”，并将W从S1中去掉，此时S1=“对外经济技术”；
（17）S1不为空，于是从S1左边取出候选子串W=“济技术”；
（18）查词表，W不在词表中，将W最左边一个字去掉，得到W=“技术”；（19）查词表，“交流”在词表中，将W加入到S2中，S2=“技术/ 合作/ 与/ 交流/ 不断/ 扩大/”，并将W从S1中去掉，此时S1=“对外经济
（20）S1不为空，于是从S1左边取出候选子串W=“外经济”；
（21）查词表，W不在词表中，将W最左边一个字去掉，得到W=“经济”；（22）查词表，“交流”在词表中，将W加入到S2中，S2=“经济/ 技术/ 合作/ 与/ 交流/ 不断/ 扩大/ ”，并将W从S1中去掉，此时S1=“对外”；（23）S1不为空，由于此时S1只剩下“对外”于是从S1左边取出候选子串W=“对外”；
（24）查词表，“对外”在词表中，将W加入到S2中，S2=“对外/ 经济/ 技术/ 合作/ 与/ 交流/ 不断/ 扩大/ ”，并将W从S1中去掉，此时S1=“”；（25）S1为空，输出S2作为分词结果，分词过程结束。
正向匹配法思想与逆向一样，只是从左向右切分，因此只举例逆向最大匹配算法描述。
•软件演示：
软件界面：
选择分词所要的方式（正向或逆向），然后输入所要分词的内容，分词结果就会在右边显示出来。
正向最大匹配分词结果：
逆向最大匹配分词结果：
•总结：
1.使用哈希表存储字典，启动时间延长，内存占用增加，但是，可以实现实时分词。
2.两个算法相对而言，逆向算法的出错率更低，例如“幼儿园地节目”，正向会分为幼儿园/地/节目，而逆向为幼儿/园地/节目。
3.对于最大长度的选择要谨慎，若太长会导致运行时间太长，而太短则可能
会导致一些词语无法识别。