1、中文分词入门之最大匹配法发表于 2009 年 01 月 12 号 由 52nlp 中文分词在中文信息处理中是最最基础的，无论机器翻译亦或信息检索还是其他相关应用，如果涉及中文，都离不开中文分词，因此中文分词具有极高的地位。中文分词入门最简单应该是最大匹配法了，当年师兄布置给我的第一个学习任务就是实现最大匹配法的分词算法（正向、逆向）。记得当时对自己参考学习最有帮助的是北大詹卫东老师“中文信息处理基础” 的课件和源程序，不过他实现的是 mfc 程序，词表存储在数据库里。自己实现时用纯 c+实现，利用hash_map 存储词表。这里我介绍一下相关的知识和一个简单的程序示例，部分参考自詹老师的讲义。
2、正向最大匹配法算法如下所示：（注：以上最大匹配算法图来自于詹老师讲义）逆向匹配法思想与正向一样，只是从右向左切分，这里举一个例子：输入例句：S1=” 计算语言学课程有意思” ；定义：最大词长 MaxLen = 5；S2= ” “；分隔符 = “/”；假设存在词表：，计算语言学，课程，意思，；最大逆向匹配分词算法过程如下：（1）S2=”“；S1 不为空，从 S1 右边取出候选子串 W=”课程有意思 ”；（2）查词表，W 不在词表中，将 W 最左边一个字去掉，得到 W=”程有意思” ；（3）查词表，W 不在词表中，将 W 最左边一个字去掉，得到 W=”有意思” ；（4）查词表，W 不在词表中，将
3、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 加入
4、到 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 不为空，于是
5、从 S1 左边取出候选子串 W=”计算语言学 ”；（17）查词表，“计算语言学” 在词表中，将 W 加入到 S2 中，S2=“计算语言学/ 课程/ 有/ 意思/”，并将 W 从 S1 中去掉，此时 S1=”“；（18 ） S1 为空，输出 S2 作为分词结果，分词过程结束。相应程序示例：准备文件：建立一个词表文件 wordlexicon，格式如下计算语言学课程意思输入文件：test,格式如下计算语言学课程有意思编译后执行如下：SegWord.exe test输出分词结果文件：SegmentResult.txt源代码如下：/ Dictionary.h#include #include #incl
6、ude #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
7、;/将词典文件读入并构造为一个哈希词典CDictionary:CDictionary()ifstream infile(“wordlexicon”); / 打开词典if (!infile.is_open() / 打开词典失败则退出程序cerr word; /读入每行第一个词wordhash.insert(sipair(word, 1); /插入到哈希中CDictionary:CDictionary()/在哈希词典中查找词，若找到，则返回，否则返回int CDictionary:FindWord(string w)if (wordhash.find(w) != wordhash.end()ret
8、urn 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 M
9、axWordLength) / 如果输入串长度大于最大词长len = MaxWordLength; / 只在最大词长范围内进行处理/string w = s1.substr(0, len); / （正向用）将输入串左边等于最大词长长度串取出作为候选词string w = s1.substr(s1.length() len, len); /逆向用int n = WordDic.FindWord(w); / 在词典中查找相应的词while(len 2 / 从候选词右边减掉一个汉字，将剩下的部分作为候选词/w = w.substr(0, len); /正向用w = s1.substr(s1.leng
10、th() 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 (
11、string s1)string s2 = “”; /用 s2 存放分词结果int i;int dd;while(!s1.empty() )unsigned char ch = (unsigned char)s10;if (ch = 161)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); /
12、 打开输入文件if (!infile.is_open() / 打开输入文件失败则退出程序cerr “Unable to open input file: “ argv1 “ - bailing out!“ endl;exit(-1);ofstream outfile1(“SegmentResult.txt“); /确定输出文件if (!outfile1.is_open()cerr “Unable to open file：SegmentResult.txt“ “-bailing out!“ endl;exit(-1);while (getline(infile, strtmp, n) /读入语料库中的每一行并用最大匹配法处理line = strtmp;line = SegmentSentenceMM(line); / 调用分词函数进行分词处理outfile1 line endl; / 将分词结果写入目标文件return 0;
