中文分词之最大匹配

转载&＃xff1a;http://apps.hi.baidu.com/share/detail/15014495

中文分词在中文信息处理中是最最基础的&＃xff0c;无论机器翻译亦或信息检索还是其他相关应用&＃xff0c;如果涉及中文&＃xff0c;都离不开中文分词&＃xff0c;因此中文分词具有极高的地 位。中文分词入门最简单应该是最大匹配法了&＃xff0c;当年师兄布置给我的第一个学习任务就是实现最大匹配 法的分词算法&＃xff08;正向、逆向&＃xff09;。记得当时对自己参考学习最有帮助的是北大詹卫东老师“中文信息处理基础”的课件和源程序&＃xff0c;不过他实现的是mfc程序&＃xff0c;词表存 储在数据库里。自己实现时用纯c&＃43;&＃43;实现&＃xff0c;利用hash_map存储词表。这里我介绍一下相关的知识和一个简单的程序示例&＃xff0c;部分参考自詹老师的讲义。
正向最大匹配法算法如下所示&＃xff1a;

&＃xff08;注&＃xff1a;以上最大匹配算法图来自于詹老师讲义&＃xff09;
逆向匹配法思想与正向一样&＃xff0c;只是从右向左切分&＃xff0c;这里举一个例子&＃xff1a;
输入例句&＃xff1a;S1&＃61;”计算语言学课程有意思” &＃xff1b;
定义&＃xff1a;最大词长MaxLen &＃61; 5&＃xff1b;S2&＃61; ” “&＃xff1b;分隔符 &＃61; “/”&＃xff1b;
假设存在词表&＃xff1a;…&＃xff0c;计算语言学&＃xff0c;课程&＃xff0c;意思&＃xff0c;…&＃xff1b;
最大逆向匹配分词算法过程如下&＃xff1a;
&＃xff08;1&＃xff09;S2&＃61;”"&＃xff1b;S1不为空&＃xff0c;从S1右边取出候选子串W&＃61;”课程有意思”&＃xff1b;
&＃xff08;2&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”程有意思”&＃xff1b;
&＃xff08;3&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”有意思”&＃xff1b;
&＃xff08;4&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”意思”
&＃xff08;5&＃xff09;查词表&＃xff0c;“意思”在词表中&＃xff0c;将W加入到S2中&＃xff0c;S2&＃61;” 意思/”&＃xff0c;并将W从S1中去掉&＃xff0c;此时S1&＃61;”计算语言学课程有”&＃xff1b;
&＃xff08;6&＃xff09;S1不为空&＃xff0c;于是从S1左边取出候选子串W&＃61;”言学课程有”&＃xff1b;
&＃xff08;7&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”学课程有”&＃xff1b;
&＃xff08;8&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”课程有”&＃xff1b;
&＃xff08;9&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”程有”&＃xff1b;
&＃xff08;10&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”有”&＃xff0c;这W是单字&＃xff0c;将W加入到S2中&＃xff0c;S2&＃61;“ /有 /意思”&＃xff0c;并将W从S1中去掉&＃xff0c;此时S1&＃61;”计算语言学课程”&＃xff1b;
&＃xff08;11&＃xff09;S1不为空&＃xff0c;于是从S1左边取出候选子串W&＃61;”语言学课程”&＃xff1b;
&＃xff08;12&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”言学课程”&＃xff1b;
&＃xff08;13&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”学课程”&＃xff1b;
&＃xff08;14&＃xff09;查词表&＃xff0c;W不在词表中&＃xff0c;将W最左边一个字去掉&＃xff0c;得到W&＃61;”课程”&＃xff1b;
&＃xff08;15&＃xff09;查词表&＃xff0c;“意思”在词表中&＃xff0c;将W加入到S2中&＃xff0c;S2&＃61;“ 课程/ 有/ 意思/”&＃xff0c;并将W从S1中去掉&＃xff0c;此时S1&＃61;”计算语言学”&＃xff1b;
&＃xff08;16&＃xff09;S1不为空&＃xff0c;于是从S1左边取出候选子串W&＃61;”计算语言学”&＃xff1b;
&＃xff08;17&＃xff09;查词表&＃xff0c;“计算语言学”在词表中&＃xff0c;将W加入到S2中&＃xff0c;S2&＃61;“计算语言学/ 课程/ 有/ 意思/”&＃xff0c;并将W从S1中去掉&＃xff0c;此时S1&＃61;”"&＃xff1b;
&＃xff08;18&＃xff09;S1为空&＃xff0c;输出S2作为分词结果&＃xff0c;分词过程结束。

相应程序示例&＃xff1a;
准备文件&＃xff1a;建立一个词表文件wordlexicon&＃xff0c;格式如下
计算语言学
课程
意思
输入文件&＃xff1a;test,格式如下
计算语言学课程有意思
编译后执行如下&＃xff1a;SegWord.exe test
输出分词结果文件&＃xff1a;SegmentResult.txt
源代码如下&＃xff1a;
// Dictionary.h
#include
#include
#include
#include
#include

using namespace std;
using namespace stdext;

class CDictionary
{
public:
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!" < exit(-1);
}
while (getline(infile, strtmp, &＃39;n&＃39;)) // 读入词典的每一行并将其添加入哈希中
{
istringstream istr(strtmp);
istr >> word; //读入每行第一个词
wordhash.insert(sipair(word, 1)); //插入到哈希中
}
}

CDictionary::~CDictionary()
{
}

//在哈希词典中查找词&＃xff0c;若找到&＃xff0c;则返回&＃xff0c;否则返回
int CDictionary::FindWord(string w)
{
if (wordhash.find(w) !&＃61; wordhash.end())
{
return 1;
}
else
{
return 0;
}
}

// 主程序main.cpp
#include “Dictionary.h”

# define MaxWordLength 10 // 最大词长为个字节&＃xff08;即个汉字&＃xff09;
# define Separator “/ ” // 词界标记

CDictionary WordDic; //初始化一个词典

//对字符串用最大匹配法&＃xff08;正向或逆向&＃xff09;处理
string SegmentSentence(string s1)
{
string s2 &＃61; “”; //用s2存放分词结果

while(!s1.empty())
{
int len &＃61;(int) s1.length(); // 取输入串长度
if (len > MaxWordLength) // 如果输入串长度大于最大词长
{
len &＃61; MaxWordLength; // 只在最大词长范围内进行处理
}

//string w &＃61; s1.substr(0, len); // &＃xff08;正向用&＃xff09;将输入串左边等于最大词长长度串取出作为候选词
string w &＃61; s1.substr(s1.length() – len, len); //逆向用
int n &＃61; WordDic.FindWord(w); // 在词典中查找相应的词
while(len > 2 && n &＃61;&＃61; 0) // 如果不是词
{
len -&＃61; 2; // 从候选词右边减掉一个汉字&＃xff0c;将剩下的部分作为候选词
//w &＃61; w.substr(0, len); //正向用
w &＃61; s1.substr(s1.length() – len, len); //逆向用
n &＃61; WordDic.FindWord(w);
}
//s2 &＃43;&＃61; w &＃43; Separator; // (正向用&＃xff09;将匹配得到的词连同词界标记加到输出串末尾
w &＃61; w &＃43; Separator; // (逆向用)
s2 &＃61; w &＃43; s2 ; // (逆向用)
//s1 &＃61; s1.substr(w.length(), s1.length()); //(正向用)从s1-w处开始
s1 &＃61; s1.substr(0, s1.length() – len); // (逆向用)
}
return s2;
}

//对句子进行最大匹配法处理&＃xff0c;包含对特殊字符的处理
string SegmentSentenceMM (string s1)
{
string s2 &＃61; “”; //用s2存放分词结果
int i;
int dd;
while(!s1.empty() )
{
unsigned char ch &＃61; (unsigned char)s1[0];
if (ch <128) // 处理西文字符
{
i &＃61; 1;
dd &＃61; (int)s1.length();
while (i