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

中文分词在中文信息处理中是最最基础的,无论机器翻译亦或信息检索还是其他相关应用,如果涉及中文,都离不开中文分词,因此中文分词具有极高的地位。中文分词入门最简单应该是最大匹配法了,当年师兄布置给我的第一个学习任务就是实现最大匹配法的分词算法(正向、逆向)。记得当时对自己参考学习最有帮助的是北大詹卫东老师“中文信息处理基础”的课件和源程序,不过他实现的是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输出 if (ch == 10 || ch == 13 || ch == 32) //谢谢读者mces89的指正 { 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;
}

注:原创文章,转载请注明出处“我爱自然语言处理”:www.52nlp.cn

本文链接地址:
http://www.52nlp.cn/maximum-matching-method-of-chinese-word-segmentation/

此条目发表在中文分词分类目录,贴了, , , 标签。将固定链接加入收藏夹。

中文分词入门之最大匹配法》有 116 条评论

  1. 陈明说:

    为什么我用Vs2010编译的时候,打开词典总是失败的,要么就运行不了???

    [回复]

    Cany_chan 回复:

    同问

    [回复]

  2. Howard说:

    非常好的文章,简单易懂

    [回复]

  3. sysu512说:

    想问下 基于统计的方法中的语料库 中的“语料库”的定义是啥 它与训练集有什么关系吗

    [回复]

  4. Pingback引用通告: 中文分词算法之最大匹配法 | iyizhan.com

  5. 蒙奇奇说:

    兄台您好,现在不知道你是否还在搞这个,有点不太懂,能否发个源程序?232162670@qq.com。谢谢。

    [回复]

    52nlp 回复:

    好多年了,电脑都换了几台,源程序都不知道放哪里去了;代码其实上面是现成的,稍作整理即可,整理的过程也是一个学习的过程

    [回复]

    蒙奇奇 回复:

    52nlp老兄还真是客气,我开始认为这上面是很多不同的楼主发的不同的文章,结果发现来来回回就是你们几个,这么多年过去了,真是佩服佩服。
    我刚开始学中文分词,大概开始了2个月,很幸运能够在学习的初始就找到这个网站,对我帮助挺大,从刚开始的VC写最大匹配算法,到现在在学习perl,感觉是一个非常漫长的路,至于这个程序,最后我还是没有运行出来,应该是STL中哈希表的缘故,不过我已经绕过哈希表,直接查找文本文件来进行词语的对比,只不过要慢很多。
    开始的时候别人给我推荐python,感觉是不错,但是只是在处理英文方面,处理中文方面最后我还是找到了perl,在您发的中文分词之入门之文献一文中。
    我对linux不熟,在那篇文章中的score程序又调试不通过,我是win7的系统。
    看来又要开始慢慢的摸索了。
    不过目前在学习Perl,一步一步来吧。
    说这么多,最想说的还是感谢您的辛苦指导,这也算是一种指导吧!谢谢!

    [回复]

    52nlp 回复:

    谢谢支持,python方面推荐结巴分词,可以看看 https://github.com/fxsjy/jieba

  6. 夏忆说:

    浏览了评论,感觉版主给了代码,却没给代码下载和对初学者提示运行方法是个极大的失误啊,大家居然一直都在问同样的问题!大家都不先自己找原因的么!

    搜索自然语言处理到此,很好的分享,mark一下,版主加油!

    [回复]

    52nlp 回复:

    其实一开始还是给了一点运行方法提示的,只是大家习惯了在互联网上伸手拿来而已~谢谢支持

    [回复]

    蒙奇奇 回复:

    对你的建议是找一门你熟悉的语言,把文件操作和字符串操作弄熟,再看清楚这个最大匹配的算法,能够实现,并且有一个直观的认识就好。源码其实意义真的不大。

    [回复]

    蒙奇奇 回复:

    你要源码我可以发一个给你噢~不过没有52nlp这个程序快,因为他用了STL,我写的程序是蜗牛一样的速度,但是大概也是同样的过程。VC的,十分简单。100行不到。

    [回复]

  7. 雨丝说:

    代码怎么运行不了呀,生成exe时老是提示debug assertion failed!program d:\……..\fenci.exe ,file:f:\dd\vctools\crt_bld\self.x86\crt\src\fopen.c, 另外词典文件wordlexicon是什么格式的,怎么存储的?运行时需要的test和wordlexicon的关系?希望您不吝赐教。

    [回复]

  8. yu说:

    你好, 代码好像格式有些问题了, 请问可否重新调整下?

    [回复]

    52nlp 回复:

    谢谢提醒,简单修改了一下,请自行添加缩进对齐。

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注