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