一
12
中文分词入门之最大匹配法
分类 中文分词
中文分词在中文信息处理中是最最基础的，无论机器翻译亦或信息检索还是其他相关应用，如果涉及中文，都离不开中文分词，因此中文分词具有极高的地位。中文分词入门最简单应该是最大匹配法了，当年师兄布置给我的第一个学习任务就是实现最大匹配法的分词算法（正向、逆向）。记得当时对自己参考学习最有帮助的是北大詹卫东老师“中文信息处理基础”的课件和源程序，不过他实现的是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 <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <hash_map>
using namespace std;
using namespace stdext;
class CDictionary
{
public:
CDictionary(); //将词典文件读入并构造为一个哈希词典
~CDictionary();
int FindWord(string w); //在哈希词典中查找词
private:
string strtmp; //读取词典的每一行
string word; //保存每个词
hash_map<string, int> wordhash; // 用于读取词典后的哈希
hash_map<string, int >::iterator worditer; //
typedef pair<string, int> sipair;
};
//将词典文件读入并构造为一个哈希词典
CDictionary::CDictionary()
{
ifstream infile(“wordlexicon”); // 打开词典
if (!infile.is_open()) // 打开词典失败则退出程序
{
cerr << "Unable to open input file: " << "wordlexicon"
<< " -- bailing out!" << endl;
exit(-1);
}
while (getline(infile, strtmp, 'n')) // 读入词典的每一行并将其添加入哈希中
{
istringstream istr(strtmp);
istr >> word; //读入每行第一个词
wordhash.insert(sipair(word, 1)); //插入到哈希中
}
}
CDictionary::~CDictionary()
{
}
//在哈希词典中查找词，若找到，则返回，否则返回
int CDictionary::FindWord(string w)
{
if (wordhash.find(w) != wordhash.end())
{
return 1;
}
else
{
return 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)s1[0];
if (ch < 128) // 处理西文字符
{
i = 1;
dd = (int)s1.length();
while (i < dd && ((unsigned char)s1[i] < 128) && (s1[i] != 10) && (s1[i] != 13)) // s1[i]不能是换行符或回车符
{
i++;
}
if ((ch != 32) && (ch != 10) && (ch != 13)) // 如果不是西文空格或换行或回车符
{
s2 += s1.substr(0,i) + Separator;
}
else
{
if (ch == 10 || ch == 13) // 如果是换行或回车符，将它拷贝给s2输出
{
s2 += s1.substr(0, i);
}
}
s1 = s1.substr(i,dd);
continue;
}
else
{
if (ch < 176) // 中文标点等非汉字字符
{
i = 0;
dd = (int)s1.length();
while(i < dd && ((unsigned char)s1[i] < 176) && ((unsigned char)s1[i] >= 161)
&& (!((unsigned char)s1[i] == 161 && ((unsigned char)s1[i+1] >= 162 && (unsigned char)s1[i+1] <= 168)))
&& (!((unsigned char)s1[i] == 161 && ((unsigned char)s1[i+1] >= 171 && (unsigned char)s1[i+1] <= 191)))
&& (!((unsigned char)s1[i] == 163 && ((unsigned char)s1[i+1] == 172 || (unsigned char)s1[i+1] == 161)
|| (unsigned char)s1[i+1] == 168 || (unsigned char)s1[i+1] == 169 || (unsigned char)s1[i+1] == 186
|| (unsigned char)s1[i+1] == 187 || (unsigned char)s1[i+1] == 191)))
{
i = i + 2; // 假定没有半个汉字
}
if (i == 0)
{
i = i + 2;
}
if (!(ch == 161 && (unsigned char)s1[1] == 161)) // 不处理中文空格
{
s2+=s1.substr(0, i) + Separator; // 其他的非汉字双字节字符可能连续输出
}
s1 = s1.substr(i, dd);
continue;
}
}
// 以下处理汉字串
i = 2;
dd = (int)s1.length();
while(i < dd && (unsigned char)s1[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(argv[1]); // 打开输入文件
if (!infile.is_open()) // 打开输入文件失败则退出程序
{
cerr << "Unable to open input file: " << argv[1]
<< " -- 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;
}
补充说明：如果使用正向匹配法，请将源代码中的相关注释 “//"互换。
注：原创文章，转载请注明出处“我爱自然语言处理”：blog.52nlp.org
本文链接地址：
http://blog.52nlp.org/maximum-matching-method-of-chinese-word-segmentation/
相关文章:
- 中文分词入门之最大匹配法扩展2
- 中文分词入门之最大匹配法扩展1
- 中文分词入门之篇外
- 中文分词入门之资源
- 自然语言处理与计算语言学书籍汇总之四：国内书籍
- 中文分词入门之文献
- 中文分词入门之字标注法2
- 基于字标注的中文分词方法
- 中文分词入门之字标注法1
- 冯志伟：我与计算语言学的缘分三
评论
19条回复 to “中文分词入门之最大匹配法”
发表评论
订阅52nlp：
学兄也太搞笑了吧?最大切词法是您这个流程?从句子的后面一个个地吃掉?哈哈为什么不用多线程两端折半去吃?或者从中间再加个precess不是吃的更好?哈哈,20年前就被证明没戏的方法您还在发文?!
[回复]
admin 回复:
四月 5th, 2009 at 20:35
这里只是给了一个中文分词的入门示例，正向匹配的算法流程是詹卫东老师给的，不是我给的。我举得例子是逆向匹配，您大概看错了吧。另外，最大匹配法是中文分词的经典方法，现在看来虽然老，但也不是您所说的“20年前就被证明没戏”，如果有，请给个依据，不能空口说白话的。
你给的方法不过是最大匹配法的一种改进，举得例子是逆向匹配也是是其中一种。现在真正流行的是基于字的中文分词方法，如CRF分词我也接触过。但这里仅仅是中文分词入门的介绍，发文只是希望给有需要的读者一定的启示，另外程序也只是我当初入门时的练习而已，可笑之处，请多多包涵。
如果您对中文分词还有什么高见，欢迎在这里讨论。
[回复]
非常感谢你的这篇文章，对于我这个初学者很有意义。
[回复]
admin 回复:
四月 19th, 2009 at 22:22
不用客气，能对你有所帮助就好。
[回复]
我看了已有的算法实现后得出一个挺极端的结论。
HMM，MMSEG，还有一个什么基于CRF。
发觉只有MMSEG算法好理解，效率高，实用，且好扩展。
其他的算法简直和看天书差不多。而且糟糕的地方是，花了那么大的代价，对中文分词的那些真正老大难的问题。依旧无法解决~~
比如人名啊，地名啊，未登陆词啊。
最靠谱的方法还是MMSEG+词典，加上一个离线的新词发现机制。
不知楼主能否更深入谈谈分词，有没有真正觉得好用的分词方法。
[回复]
admin 回复:
八月 4th, 2009 at 22:55
用MMSEG做中文分词的确简洁有效，但是只属于一个特定的方法，所以比较好理解。而一个好的数学模型，像HMM、CRF虽然开始时比较难理解，但是其用处不仅仅在中文分词，在自然语言处理甚至更多的领域都有用武之地，所以感觉多花一些时间还是值得的。
关于中文分词，自己的掌握也有限，不过有计划在翻译完HMM这个系列之后尝试讲讲如何利用HMM来做词性标注、中文分词，主要从从动手练习的角度入手，欢迎继续关注。
[回复]
学兄，能不能把你的全部源程序发给我
哈希表的构造hash_map.h这部分
谢谢！！
[回复]
我的邮箱是jilei08124@hotmail.com
[回复]
hash_map是属于STL的一个容器，如果你安装了C++的编译器的话，应该自带了，具体可以参考：http://www.stlchina.org/twiki/bin/view.pl/Main/STLDetailHashMap
[回复]
stlport\hash_map(24) : fatal error C1083: Cannot open include file: ‘stl/_prolog.h’: No such file or directory
我把hash_map加进去老是提示这个错误，我查了一下，路径是对的？？？？
还请大虾指点
[回复]
hash_map wordhash;
上边是不是应该还有一句啊？链接是提示hash_map要带参数，我很想学习一下，还请大虾指点一下！！！！
[回复]
admin 回复:
九月 2nd, 2009 at 19:46
抱歉，白天在公司不方便管理博客，现在才给你回复。
非常感谢你的提示，我才发现wordpress在发布代码时屏蔽掉了那个地方的几处尖括号，已经更改了，不好意思啊，是我发布后的粗心没有检查！
[回复]
已将源程序发到你的邮箱了，非常感谢！
[回复]
kathy 回复:
三月 23rd, 2010 at 16:34
可以麻烦你发一份源程序代码给我吗？
[回复]
52nlp 回复:
三月 23rd, 2010 at 21:18
晚上有事刚回来，已经发到你邮箱了。
[回复]
最大匹配法是一个基本的分词算法，还是很有意义的，如正向和逆向一起找到歧义等，有了新方法，老方法并不是一无是处，可以辅助新方法，像现在的机器翻译，统计方法占主流，但是目前商用的基本上都是规则的方法，而现在都是在统计方法中和规则结合。
我硕士时做过基于字位的分词，用最大熵实现的，对于未登录词有很好的效果，如训练语料中没有人名，地名等，但对一些常用词有时会分错。
[回复]
特别欢迎你有空能在这里讲讲最大熵和基于字标注的分词方法！
[回复]
真鄙视这种说空话的人，有本事把Proof和Justification拿出来
[回复]
Kevin 回复:
三月 26th, 2011 at 12:53
我是指的一楼”玉树临风“，可能打错了，是”迂腐临疯“吧
[回复]