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

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

作者 52nlp

《中文分词入门之最大匹配法》有119条评论
  1. 您好,也是因为刚接触这个,所以希望博主也给我发一份,谢谢!!1835977342@qq.com

    [回复]

    52nlp 回复:

    已经发了!

    [回复]

  2. 你好,请问wordhash.insert(sipair(word, 1)); 中参数1的含义是什么?

    [回复]

    52nlp 回复:

    仅仅是用来计数站位用的,可以Google一下hashmap已经pair的用法。

    [回复]

  3. 看到这个程序好激动,但编译后出现了这样的错误:“Cannot open include file: 'hash_map.h': No such file or directory”,初学c++,出现这种情况不知怎么办才好,希望大侠指点迷津,小女子感激不尽!!!

    [回复]

    52nlp 回复:

    Google 一下Hash_map或者这个问题,这份代码只是调用了hash_map,并不提供hash_map。

    [回复]

  4. 您好!能否将代码发一份到kongcsdn@gmail.com ! 谢谢了!感觉很受用!

    [回复]

    52nlp 回复:

    代码这里已经是完整的了,自己整理一下就可以了。

    [回复]

  5. 学长,能否给我发一份源程序,谢谢,我想学习一下!邮箱tieshushjg@163.com

    [回复]

  6. 我也出现了那个哈希词表的问题,可以将完整的CPP程序发给我一下吗?包括词典的。偶是初学的菜鸟啊,恳请博主指教一二。328860932@qq.com

    [回复]

    52nlp 回复:

    这个哈希表的问题根本就不是问题啊,应该自己去google一下解决,另外这里就是全部代码了。

    [回复]

  7. getline(infile, strtmp, '\n');最后一个参数(分隔符)应该是'斜杠n',不知道是不是页面显示的问题。这样读词典的时候就正确了。学习中......

    [回复]

    52nlp 回复:

    是显示时斜杠被屏蔽了,我修改了,多谢!

    [回复]

  8. 你好。我正在学习中文分词呢。学长,你能把代码发我一份吗?
    我邮箱是yingkai19851208@126.com
    多谢多谢了啊。

    [回复]

    kaizibaby 回复:

    我在把你的代码进行试验的时候碰到了一些问题

    [回复]

  9. 在txt文件中的文本有一个句子分布在两行。这样的话,分词效果会降低

    [回复]

    52nlp 回复:

    这样的话最好先断句,一句一行。

    [回复]

  10. 你好。我正在学习中文分词呢,您能把代码发我一份吗?
    我邮箱是530996899@qq.com
    多谢多谢了啊

    [回复]

    52nlp 回复:

    代码就在上面啊,自己整理一下就可以了。

    [回复]

    黄小莹 回复:

    可是代码运行编译时遇到了些小问题,可能是哪里出现了问题、、、、、(*^__^*)

    [回复]

  11. 楼主,你好,能加你QQ么,或者你加我QQ:382001926也行,我是大四学生正在做毕业设计,希望能够和楼主交流下,真心求交流!!!

    [回复]

    52nlp 回复:

    抱歉,目前很忙,没时间qq,如果有问题,可以在这里抛出来。

    [回复]

    勇敢的心 回复:

    楼主不知道你用的什么软件,因为vc6.0不包含hash_map,所以我用的vs2008,就像你说的那样,头文件是"Dictionary.h",源文件是“WinMain”,运行还是有错啊,1>MSVCRTD.lib(crtexew.obj) : error LNK2019: 無法解析的外部符號 _WinMain@16 在函式 ___tmainCRTStartup 中被參考
    1>D:\用户目录\Documents\Visual Studio 2008\Projects\WinMain\Debug\WinMain.exe : fatal error LNK1120: 1 個無法解析的外部符號
    楼主,求解啊。。。

    [回复]

    52nlp 回复:

    印象当时用得是vs2005, 主程序应该是main.cpp吧。

  12. 如何加入词典?

    [回复]

    52nlp 回复:

    文章中已经写了,词表文件就是词典:
    相应程序示例:
      准备文件:建立一个词表文件wordlexicon,格式如下
        计算语言学
        课程
        意思
    ...
      

    [回复]

    知秋一叶 回复:

    你好,我想再问一下,建立词典,并且搜索词语,需要用到数据库知识吗?要sql?

    [回复]

    52nlp 回复:

    纯文本,不需要。

  13. 哇,终于在这里发现干活了。这段时间一直关注中文分词。算法很多,介绍都不够细致。52nlp可以提供一些这些信息了

    [回复]

  14. 你好,我是个初学者,我想问一下我这个字典如何加到工程中啊?

    [回复]

    52nlp 回复:

    相应程序示例:
      准备文件:建立一个词典文件wordlexicon,格式如下
        计算语言学
        课程
        意思
      输入文件:test, 格式如下
           计算语言学课程有意思
      编译后执行如下:SegWord.exe test
      输出分词结果文件:SegmentResult.txt

    [回复]

    charmaine 回复:

    这个我看过了,我是想说我的wordlexicon文件放在什么地方?在什么路径下能读取到啊?

    [回复]

    52nlp 回复:

    与可执行文件放到一起就ok了

  15. 我在做一个关键字提取的MFC,分词程序是用的这一篇,不过一直显示:
    fatal error C1083: Cannot open include file: 'hash_map': No such file or directory
    我用的是VC++6.0,请问这一问题要怎么解决?

    [回复]

    52nlp 回复:

    貌似你的vc6太老了:http://zhidao.baidu.com/question/186662977.html

    或者考虑把代码里的hash_map换成map吧

    [回复]

  16. 课程设计需要用到中文分词,希望学兄能发源代码到505333971@qq.com 用作学习.感激不尽

    [回复]

    Cany_chan 回复:

    已经在网盘看到了喔.在下载.谢谢了.呵呵

    [回复]

发表回复

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