中文分词算法入门

中文分词在中文信息处理中是最最基础的，无论机器翻译亦或信息检索还是其他相关应用，如果涉及中文，都离不开中文分词，因此中文分词具有极高的地位。中文分词入门最简单应该是正向减字最大匹配法了.

中文分词，纯粹从效率上来说<<一种改进的快速分词算法>>陈桂林,王永成等发表的那篇论文,所介绍的数据结构和算法应该是目前效率最高的，分词的复杂度当然也是最低的,有兴趣的同学可以拜读一下，讲解的非常好.

刚刚入门，不讲难的，来点简单的，容易实现的:正向减字最大匹配算法

正向:从左到右扫描句子

逆向:从右到左扫描句子

减字:没有匹配成功,减一个字,如果是正向,则减最右边的一个字,如果是逆向,则减最左边的一个字

最大:所谓最大，就是一个句子被分词后，结果集中词的个数最少，因为中文的单字成词的特点,所以只能是最大,如果是最小匹配,我们都不用分词了,每个字就是一个词.

<正向减字最大匹配算法流程图>

（注：以上正向减字最大匹配算法图来自于詹老师讲义）
逆向匹配法思想与正向一样，只是从右向左切分，这里举一个例子：
输入例句：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作为分词结果，分词过程结束。

正向减字最大匹配分词算法解决上例,是个相反的过程，按照流程图，你自己分词一下.

下面贴一下我实现的分词[正向和逆向]

Dict.h

#ifndef DICT_H_

#define DICT_H_

#include<iostream>

#include<fstream>

#include<string>

#include<hash_map>

#include<cstdlib>

using namespace std;

using namespace __gnu_cxx;

//在SGI STL中没有struct hash<string>

//对于string类型，就必须自定义hash函数

struct str_hash

{

size_t operator()(const string& str)const

{

unsigned long __h=0;

for (size_t i=0;i<str.size();i++)

__h=31*__h+str[i];

return size_t(__h);

}

};

class CDict

{

public:

CDict();

~CDict();

//查找字符串是否在词典中

bool IsWord(string &s)const;//定义一个常成员函数

private:

//用于读取词典后的哈希表

hash_map<string,int,str_hash> hash_mapDict;//私有的成员变量

void OpenDict();//打开词典

};

#endif/* DICT_H_ */

Dict.cpp

#include"Dict.h"

//无参构造函数调用打开词典的函数

CDict::CDict()

{

OpenDict();

}

//析构函数--词典清空

CDict::~CDict()

{

hash_mapDict.clear();

}

//打开词典

void CDict::OpenDict()

{

FILE*fp;

fp=fopen("words.dict","r");

if(fp==NULL)

{

cout<<"词典不能打开"<<endl;

exit(1);

}

char word[16];

int id,freq;

while(fscanf(fp,"%d %s %d",&id,word,&freq)!=EOF)

{//将从词典文件中读取的数据插入hash_mapDict容器中

hash_mapDict.insert(pair<string,int>(word,0));

}

fclose(fp);

}

//查找字符串是否在词典中

//常对象只能引用常成员函数

//非常对象也能引用常成员函数

bool CDict::IsWord(string &str)const

{

if(hash_mapDict.find(str)!=hash_mapDict.end())

return true;//找到了

return false;//没有找到

}

HzSeg.h

* HzSeg.h

* Created on: 2011-11-6

* Author: qiuxiong

* function: 句子的分词

* 中文搜索引擎为什么要进行中文分词?

* 中文分词技术是实现中文全文检索的基础

* 中文不像英文，英文一句中的每个词是由

* 空格断开的，如果中文不能断开，就不能

* 针对性的对一句话中的某一个词进行检索

* 分词的好坏直接影响着搜索的质量.

#ifndef HZSEG_H_

#define HZSEG_H_

#include<iostream>

#include<string>

#include<cstring>

#include<cstdlib>

#include<fstream>

#include"Dict.h"

using namespace std;

class CHzSeg

{

public:

CHzSeg();

~CHzSeg();

//对纯中文句子s1的正向减字最大匹配分词

string SegmentHzStrMM(CDict &dict,string s1)const;

//对纯中文句子s1的逆向减字最大匹配分词

string SegmentHzStrRMM(CDict &dict,string s1)const;

//对任意句子s1的正向减字最大匹配分词

string SegmentSentenceMM(CDict &dict,string s1)const;

//对URL带16进制字符参数的分词

string SegmentURL(CDict &dict,string url)const;

//将sourct中用十六进制表示的ASCII字符,转化为正常的字符

void Translate(char *source)const;

};

#endif /* HZSEG_H_ */

HzSeg.cpp

* HzSeg.cpp

* Created on: 2011-11-6

* Author: qiuxiong

#include"HzSeg.h"

#include"Dict.h"

//这是一个经验值,过长影响切分的效率

//过短将长词切分

const unsigned int MAX_WORD_LENGTH=8;//最长的切分单元

const string SEPARATOR("/ ");//词间分割符

CHzSeg::CHzSeg()

{

}

CHzSeg::~CHzSeg()

{

}

//对纯中文句子s1的正向减字最大匹配分词

string CHzSeg::SegmentHzStrMM(CDict &dict,string s1)const

{

string s2="";//保存句子s1的分词结果

while(!s1.empty())

{

unsigned int len=s1.size();

//如果待切分的句子大于最大切分单元

//len=最大切分单元,否则len=句子的长度

if(len>MAX_WORD_LENGTH)

len=MAX_WORD_LENGTH;

//取s1句子最左边长度len为的子句子

string w=s1.substr(0,len);

//判断刚刚取出来的子句子是不是一个词

bool isw=dict.IsWord(w);

//当w中至少有2个中文字&&不能构成字的时候,减去最右边的一个中文字

while(len>2&&isw==false)

{

///减去最右边的一个中文字

len-=2;

w=w.substr(0,len);

//再次判断减字后的w是不是构成一个词

isw=dict.IsWord(w);

}

s2+=w+SEPARATOR;

s1=s1.substr(w.size());

}//end while

return s2;

}

//对纯中文句子s1的逆向减字最大匹配分词

string CHzSeg::SegmentHzStrRMM(CDict &dict,string s1)const

{

string s2="";//保存句子s1的分词结果

while(!s1.empty())

{

unsigned int len=s1.size();

//如果待切分的句子大于最大切分单元

//len=最大切分单元,否则len=句子的长度

if(len>MAX_WORD_LENGTH)

len=MAX_WORD_LENGTH;

//取s1句子最右边长度len为的子句子

string w=s1.substr(s1.length()-len,len);

//判断刚刚取出来的子句子是不是一个词

bool isw=dict.IsWord(w);

//当w中至少有2个中文字&&不能构成字的时候,减去最左边的一个中文字

while(len>2&&isw==false)

{

//减去最左边的一个中文字

len-=2;

w=s1.substr(s1.length()-len,len);

//再次判断减字后的w是不是构成一个词

isw=dict.IsWord(w);

}

w=w+SEPARATOR;

s2=w+s2;

//分出一个词后的s1

s1=s1.substr(0,s1.length()-len);

}

return s2;

}

//对任意句子s1的正向减字最大匹配分词

string CHzSeg::SegmentSentenceMM(CDict &dict,string s1)const

{

string s2="";//保存句子s1的分词结果

unsigned int i,len;

while(!s1.empty())

{

unsigned char ch=(unsigned char)s1[0];

//处理西文字符

//ch>128[128的二进制1000 0000]其实是负数[中文字符的机内码是负数]

if(ch<128)//ch<128

{

i=1;

len=s1.size();

while(i<len&&((unsigned char)s1[i]<128)&&s1[i]!=10&&s1[i]!=13)

{//s1[i]不能是换行符或回车符\n\r

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);

}

if(i<s1.size())

s1=s1.substr(i);//取s1从下标i开始的子字符串

else//i==s1.size()s1分词完毕

break;

continue;

}

else//ch>=128

{

if(ch<176)//中文标点等非汉字字符128<=ch<176

{//

i=0;

len=s1.length();

while(i<len&&((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))

{

if(i<=s1.size())

//其他的非汉字双字节字符可能连续输出

s2+=s1.substr(0,i)+SEPARATOR;

else break;

}

if(i<s1.size())

s1=s1.substr(i);//取s1从下标i开始的子字符串

else

break;

continue;

}

//以下处理汉字串

i=2;//ch>=176

len=s1.size();

while(i<len&&(unsigned char)s1[i]>=176)

i+=2;

s2+=SegmentHzStrMM(dict,s1.substr(0,i));

if(i<len)

s1=s1.substr(i);

else

break;

}//end while

return s2;

}

//将sourct中用十六进制表示的ASCII字符,转化为正常的字符

void CHzSeg::Translate(char *source)const

{

int i=0,j=0;

char *tempstr,tempchar1,tempchar2;

tempstr=(char *)malloc(strlen(source)+1);

if(tempstr==NULL)

return;

while(source[j])

{

if((tempstr[i]=source[j])=='%')//%BD

{//按位与'&'的作用是将小写字母变成大写字母

if(source[j+1]>='A')//0xdf=223==11011111

tempchar1=((source[j+1]&0xdf)-'A')+10;

else

tempchar1=source[j+1]-'0';

if(source[j+2]>='A')

tempchar2=((source[j+2]&0xdf)-'A')+10;

else

tempchar2=source[j+2]-'0';

tempstr[i]=16*tempchar1+tempchar2;//转化为10进制

j+=2;

}

j++;

i++;

}//end while

tempstr[i]='\0';

strcpy(source,tempstr);

if(tempstr)

free(tempstr);

}

//对URL带16进制字符参数的分词

string CHzSeg::SegmentURL(CDict &dict,string url)const

{//eg:url==http://www.baidu.com/qiuxiong/eb/index.html

string::size_type idx,nidx;

char *curl=(char *)url.c_str();

this->Translate(curl);//将十六进制表示的ASCII字符,转化为正常的字符

url=curl;

if((idx=url.find("http://",0))!=string::npos)

{

if((nidx=url.find("/",7))!=string::npos)

url=url.substr(nidx+1);

//url==qiuxiong/eb/index.html

}

idx=0;

while((idx=url.find("/",idx))!=string::npos)

{

url.replace(idx,1,SEPARATOR);

idx+=3;

}//url==qiuxiong/ eb/ index.html

if((idx=url.rfind("."))!=string::npos)//删除扩展名

url.erase(idx);//url==qiuxiong/ eb/ index

url+="/ ";//url==qiuxiong/ eb/ index/

idx=0;

nidx=0;

bool isover=false;

string stmp;

while(!isover)

{

if((nidx=url.find(SEPARATOR,idx))==string::npos)

isover=true;

if(nidx-idx>0)

{

stmp=url.substr(idx,nidx-idx);//qiuxiong

//调用处理普通句子的分词函数

stmp=SegmentSentenceMM(dict,stmp);

if(stmp.size()>=3)//处理尾部的"/ "

stmp.erase(stmp.length()-3);

//分词完毕后，再次出入url中

url=url.replace(idx,nidx-idx,stmp);

idx+=stmp.length()+3;

}

else if(nidx==string::npos&&idx<url.length())

{

stmp=url.substr(idx);

stmp=SegmentSentenceMM(dict,stmp);

stmp.erase(stmp.length()-3);

url=url.substr(0,idx)+stmp;

}

else

idx=nidx+3;

}//end while

return url;

}

Main.cpp

#include<iostream>

#include<string>

#include<fstream>

#include<cstdlib>

#include"Dict.h"

#include"HzSeg.h"

using namespace std;

CDict iDict;

int main()

{

string FileName;

cin>>FileName;

ifstream fin(FileName.c_str());

ofstream fout((FileName+".seg").c_str());

string line;

CHzSeg iHzSeg;

while(getline(fin,line))

{

cout<<line<<endl;

line=iHzSeg.SegmentSentenceMM(iDict,line);

//line=iHzSeg.SegmentURL(iDict,line);

cout<<"正向减字最大匹配:"<<line<<endl;

fout<<line<<endl;

}

fin.close();

fout.flush();

fout.close();

return 0;

}