中文分词入门之最大匹配法.doc

中文分词入门之最大匹配法发表于 2009年01月12号 由 52nlp 中文分词在中文信息处理中是最最基础的，无论机器翻译亦或信息检索还是其他相关应用，如果涉及中文，都离不开中文分词，因此中文分词具有极高的地位。中文分词入门最简单应该是最大匹配法了，当年师兄布置给我的第一个学习任务就是实现最大匹配法的分词算法（正向、逆向）。记得当时对自己参考学习最有帮助的是北大詹卫东老师“中文信息处理基础”的课件和源程序，不过他实现的是mfc程序，词表存储在数据库里。自己实现时用纯c+实现，利用hash_map存储词表。这里我介绍一下相关的知识和一个简单的程序示例，部分参考自詹老师的讲义。正向最大匹配法算法如下所示：（注：以上最大匹配算法图来自于詹老师讲义）逆向匹配法思想与正向一样，只是从右向左切分，这里举一个例子：输入例句：S1=”计算语言学课程有意思” ；定义：最大词长MaxLen = 5；S2= ” “；分隔符 = “/”；假设存在词表：，计算语言学，课程，意思，；最大逆向匹配分词算法过程如下：（1）S2=”；S1不为空，从S1右边取出候选子串W=”课程有意思”；（2）查词表，W不在词表中，将W最左边一个字去掉，得到W=”程有意思”；（3）查词表，W不在词表中，将W最左边一个字去掉，得到W=”有意思”；（4）查词表，W不在词表中，将W最左边一个字去掉，得到W=”意思”（5）查词表，“意思”在词表中，将W加入到S2中，S2=” 意思/”，并将W从S1中去掉，此时S1=”计算语言学课程有”；（6）S1不为空，于是从S1左边取出候选子串W=”言学课程有”；（7）查词表，W不在词表中，将W最左边一个字去掉，得到W=”学课程有”；（8）查词表，W不在词表中，将W最左边一个字去掉，得到W=”课程有”；（9）查词表，W不在词表中，将W最左边一个字去掉，得到W=”程有”；（10）查词表，W不在词表中，将W最左边一个字去掉，得到W=”有”，这W是单字，将W加入到S2中，S2=“ /有 /意思”，并将W从S1中去掉，此时S1=”计算语言学课程”；（11）S1不为空，于是从S1左边取出候选子串W=”语言学课程”；（12）查词表，W不在词表中，将W最左边一个字去掉，得到W=”言学课程”；（13）查词表，W不在词表中，将W最左边一个字去掉，得到W=”学课程”；（14）查词表，W不在词表中，将W最左边一个字去掉，得到W=”课程”；（15）查词表，“意思”在词表中，将W加入到S2中，S2=“ 课程/ 有/ 意思/”，并将W从S1中去掉，此时S1=”计算语言学”；（16）S1不为空，于是从S1左边取出候选子串W=”计算语言学”；（17）查词表，“计算语言学”在词表中，将W加入到S2中，S2=“计算语言学/ 课程/ 有/ 意思/”，并将W从S1中去掉，此时S1=”；（18）S1为空，输出S2作为分词结果，分词过程结束。相应程序示例：准备文件：建立一个词表文件wordlexicon，格式如下计算语言学课程意思输入文件：test,格式如下 计算语言学课程有意思编译后执行如下：SegWord.exe test输出分词结果文件：SegmentResult.txt源代码如下：/ Dictionary.h#include #include #include #include #include using namespace std;using namespace stdext;class CDictionarypublic:CDictionary(); /将词典文件读入并构造为一个哈希词典CDictionary();int FindWord(string w); /在哈希词典中查找词private:string strtmp; /读取词典的每一行string word; /保存每个词hash_map wordhash; / 用于读取词典后的哈希hash_map:iterator worditer; /typedef pair sipair;/将词典文件读入并构造为一个哈希词典CDictionary:CDictionary()ifstream infile(“wordlexicon”); / 打开词典if (!infile.is_open() / 打开词典失败则退出程序cerr Unable to open input file: wordlexicon - bailing out! word; /读入每行第一个词wordhash.insert(sipair(word, 1); /插入到哈希中CDictionary:CDictionary()/在哈希词典中查找词，若找到，则返回，否则返回int CDictionary:FindWord(string w)if (wordhash.find(w) != wordhash.end()return 1;elsereturn 0;/ 主程序main.cpp#include “Dictionary.h”# define MaxWordLength 10 / 最大词长为个字节（即个汉字）# define Separator “/ ” / 词界标记CDictionary WordDic; /初始化一个词典/对字符串用最大匹配法（正向或逆向）处理string SegmentSentence(string s1)string s2 = “”; /用s2存放分词结果while(!s1.empty()int len =(int) s1.length(); / 取输入串长度if (len MaxWordLength) / 如果输入串长度大于最大词长len = MaxWordLength; / 只在最大词长范围内进行处理/string w = s1.substr(0, len); / （正向用）将输入串左边等于最大词长长度串取出作为候选词string w = s1.substr(s1.length() len, len); /逆向用int n = WordDic.FindWord(w); / 在词典中查找相应的词while(len 2 & n = 0) / 如果不是词len -= 2; / 从候选词右边减掉一个汉字，将剩下的部分作为候选词/w = w.substr(0, len); /正向用w = s1.substr(s1.length() len, len); /逆向用n = WordDic.FindWord(w);/s2 += w + Separator; / (正向用）将匹配得到的词连同词界标记加到输出串末尾w = w + Separator; / (逆向用)s2 = w + s2 ; / (逆向用)/s1 = s1.substr(w.length(), s1.length(); /(正向用)从s1-w处开始s1 = s1.substr(0, s1.length() len); / (逆向用)return s2;/对句子进行最大匹配法处理，包含对特殊字符的处理string SegmentSentenceMM (string s1)string s2 = “”; /用s2存放分词结果int i;int dd;while(!s1.empty() )unsigned char ch = (unsigned char)s10;if (ch 128) / 处理西文字符i = 1;dd = (int)s1.length();while (i dd & (unsigned char)s1i 128) & (s1i != 10) & (s1i != 13) / s1i不能是换行符或回车符i+;if (ch != 32) & (ch != 10) & (ch != 13) / 如果不是西文空格或换行或回车符s2 += s1.substr(0,i) + Separator;else/if (ch = 10 | ch = 13) / 如果是换行或回车符，将它拷贝给s2输出if (ch = 10 | ch = 13 | ch = 32) /谢谢读者mces89的指正s2 += s1.substr(0, i);s1 = s1.substr(i,dd);continue;elseif (ch 176) / 中文标点等非汉字字符i = 0;dd = (int)s1.length();while(i dd & (unsigned char)s1i = 161)& (!(unsigned char)s1i = 161 & (unsigned char)s1i+1 = 162 & (unsigned char)s1i+1 = 171 & (unsigned char)s1i+1 = 191)& (!(unsigned char)s1i = 163 & (unsigned char)s1i+1 = 172 | (unsigned char)s1i+1 = 161)| (unsigned char)s1i+1 = 168 | (unsigned char)s1i+1 = 169 | (unsigned char)s1i+1 = 186| (unsigned char)s1i+1 = 187 | (unsigned char)s1i+1 = 191)i = i + 2; / 假定没有半个汉字if (i = 0)i = i + 2;if (!(ch = 161 & (unsigned char)s11 = 161) / 不处理中文空格s2+=s1.substr(0, i) + Separator; / 其他的非汉字双字节字符可能连续输出s1 = s1.substr(i, dd);continue;/ 以下处理汉字串i = 2;dd = (int)s1.length();while(i = 176)i += 2;s2 += SegmentSentence(s1.substr(0, i);s1 = s1.substr(i,dd);return s2;int main(int argc, char *argv)string strtmp; /用于保存从语料库中读入的每一行string line; /用于输出每一行的结果ifstream infile(argv1); / 打开输入文件if (!infile.is_open() / 打开输入文件失败则退出程序cerr Unable to open input file: argv1 - bailing out! endl;exit(-1);ofstream outfile1(SegmentResult.txt); /确定输出文件if (!outfile1.is