中文分詞在中文信息處理中是最最基礎的，無(wú)論機器翻譯亦或信息檢索還是其他相關(guān)應用，如果涉及中文，都離不開(kāi)中文分詞，因此中文分詞具有極高的地 位。中文分詞入門(mén)最簡(jiǎn)單應該是正向減字最大匹配法了.
中文分詞，純粹從效率上來(lái)說(shuō)<<一種改進(jìn)的快速分詞算法>>陳桂林,王永成等發(fā)表的那篇論文,所介紹的數據結構和算法應該是目前效率最高的，分詞的復雜度當然也是最低的,有興趣的同學(xué)可以拜讀一下，講解的非常好.
剛剛入門(mén)，不講難的，來(lái)點(diǎn)簡(jiǎn)單的，容易實(shí)現的:正向減字最大匹配算法
正向:從左到右掃描句子
逆向:從右到左掃描句子
減字:沒(méi)有匹配成功,減一個(gè)字,如果是正向,則減最右邊的一個(gè)字,如果是逆向,則減最左邊的一個(gè)字
最大:所謂最大，就是一個(gè)句子被分詞后，結果集中詞的個(gè)數最少，因為中文的單字成詞的特點(diǎn),所以只能是最大,如果是最小匹配,我們都不用分詞了,每個(gè)字就是一個(gè)詞.
<正向減字最大匹配算法流程圖>
（注：以上正向減字最大匹配算法圖來(lái)自于詹老師講義）
逆向匹配法思想與正向一樣，只是從右向左切分，這里舉一個(gè)例子：
輸入例句：S1=”計算語(yǔ)言學(xué)課程有意思” ；
定義：最大詞長(cháng)MaxLen = 5；S2= ” “；分隔符 = “/”；
假設存在詞表：…，計算語(yǔ)言學(xué)，課程，意思，…；
逆向減字最大匹配分詞算法過(guò)程如下：
（1）S2=”"；S1不為空，從S1右邊取出候選子串W=”課程有意思”；
（2）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”程有意思”；
（3）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”有意思”；
（4）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”意思”
（5）查詞表，“意思”在詞表中，將W加入到S2中，S2=” 意思/”，并將W從S1中去掉，此時(shí)S1=”計算語(yǔ)言學(xué)課程有”；
（6）S1不為空，于是從S1左邊取出候選子串W=”言學(xué)課程有”；
（7）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”學(xué)課程有”；
（8）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”課程有”；
（9）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”程有”；
（10）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”有”，這W是單字，將W加入到S2中，S2=“ /有 /意思”，并將W從S1中去掉，此時(shí)S1=”計算語(yǔ)言學(xué)課程”；
（11）S1不為空，于是從S1左邊取出候選子串W=”語(yǔ)言學(xué)課程”；
（12）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”言學(xué)課程”；
（13）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”學(xué)課程”；
（14）查詞表，W不在詞表中，將W最左邊一個(gè)字去掉，得到W=”課程”；
（15）查詞表，“意思”在詞表中，將W加入到S2中，S2=“ 課程/ 有/ 意思/”，并將W從S1中去掉，此時(shí)S1=”計算語(yǔ)言學(xué)”；
（16）S1不為空，于是從S1左邊取出候選子串W=”計算語(yǔ)言學(xué)”；
（17）查詞表，“計算語(yǔ)言學(xué)”在詞表中，將W加入到S2中，S2=“計算語(yǔ)言學(xué)/ 課程/ 有/ 意思/”，并將W從S1中去掉，此時(shí)S1=”"；
（18）S1為空，輸出S2作為分詞結果，分詞過(guò)程結束。
正向減字最大匹配分詞算法解決上例,是個(gè)相反的過(guò)程，按照流程圖，你自己分詞一下.
下面貼一下我實(shí)現的分詞[正向和逆向]
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中沒(méi)有struct hash<string>
//對于string類(lèi)型，就必須自定義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;//定義一個(gè)常成員函數
private:
//用于讀取詞典后的哈希表
hash_map<string,int,str_hash> hash_mapDict;//私有的成員變量
void OpenDict();//打開(kāi)詞典
};
#endif/* DICT_H_ */
Dict.cpp
#include"Dict.h"
//無(wú)參構造函數調用打開(kāi)詞典的函數
CDict::CDict()
{
OpenDict();
}
//析構函數--詞典清空
CDict::~CDict()
{
hash_mapDict.clear();
}
//打開(kāi)詞典
void CDict::OpenDict()
{
FILE*fp;
fp=fopen("words.dict","r");
if(fp==NULL)
{
cout<<"詞典不能打開(kāi)"<<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;//沒(méi)有找到
}
HzSeg.h/*
* HzSeg.h
* Created on: 2011-11-6
* Author: qiuxiong
* function: 句子的分詞
* 中文搜索引擎為什么要進(jìn)行中文分詞?
* 中文分詞技術(shù)是實(shí)現中文全文檢索的基礎
* 中文不像英文，英文一句中的每個(gè)詞是由
* 空格斷開(kāi)的，如果中文不能斷開(kāi)，就不能
* 針對性的對一句話(huà)中的某一個(gè)詞進(jìn)行檢索
* 分詞的好壞直接影響著(zhù)搜索的質(zhì)量.
*/
#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進(jìn)制字符參數的分詞
string SegmentURL(CDict &dict,string url)const;
//將sourct中用十六進(jìn)制表示的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"
//這是一個(gè)經(jīng)驗值,過(guò)長(cháng)影響切分的效率
//過(guò)短將長(cháng)詞切分
const unsigned int MAX_WORD_LENGTH=8;//最長(cháng)的切分單元
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=句子的長(cháng)度
if(len>MAX_WORD_LENGTH)
len=MAX_WORD_LENGTH;
//取s1句子最左邊長(cháng)度len為的子句子
string w=s1.substr(0,len);
//判斷剛剛取出來(lái)的子句子是不是一個(gè)詞
bool isw=dict.IsWord(w);
//當w中至少有2個(gè)中文字&&不能構成字的時(shí)候,減去最右邊的一個(gè)中文字
while(len>2&&isw==false)
{
///減去最右邊的一個(gè)中文字
len-=2;
w=w.substr(0,len);
//再次判斷減字后的w是不是構成一個(gè)詞
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=句子的長(cháng)度
if(len>MAX_WORD_LENGTH)
len=MAX_WORD_LENGTH;
//取s1句子最右邊長(cháng)度len為的子句子
string w=s1.substr(s1.length()-len,len);
//判斷剛剛取出來(lái)的子句子是不是一個(gè)詞
bool isw=dict.IsWord(w);
//當w中至少有2個(gè)中文字&&不能構成字的時(shí)候,減去最左邊的一個(gè)中文字
while(len>2&&isw==false)
{
//減去最左邊的一個(gè)中文字
len-=2;
w=s1.substr(s1.length()-len,len);
//再次判斷減字后的w是不是構成一個(gè)詞
isw=dict.IsWord(w);
}
w=w+SEPARATOR;
s2=w+s2;
//分出一個(gè)詞后的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的二進(jìn)制1000 0000]其實(shí)是負數[中文字符的機內碼是負數]
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]不能是換行符或回車(chē)符\n\r
i++;
}
if(ch!=32&&ch!=10&&ch!=13)//如果不是西文空格或換行或回車(chē)符
s2+=s1.substr(0,i)+SEPARATOR;
else
{
if(ch==10||ch==13)//如果是換行或回車(chē)符，將它拷貝給s2輸出
s2+=s1.substr(0,i);
}
if(i<s1.size())
s1=s1.substr(i);//取s1從下標i開(kāi)始的子字符串
else//i==s1.size()s1分詞完畢
break;
continue;
}
else//ch>=128
{
if(ch<176)//中文標點(diǎn)等非漢字字符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;//假定沒(méi)有半個(gè)漢字
}
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開(kā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中用十六進(jìn)制表示的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
{//按位與'&'的作用是將小寫(xiě)字母變成大寫(xiě)字母
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ìn)制
j+=2;
}
j++;
i++;
}//end while
tempstr[i]='\0';
strcpy(source,tempstr);
if(tempstr)
free(tempstr);
}
//對URL帶16進(jìn)制字符參數的分詞
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);//將十六進(jìn)制表示的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;
}
