Sunday, April 23, 2006

 

Some notes on Chinese Words Segmentation - 3

1.
From http://blog.csdn.net/group/ictclas4j/

(一)分词思想

ICTClAS分词系统是由中科院计算所的张华平、刘群所开发的一套获得广泛好评的分词系统,难能可贵的是该版的Free版开放了源代码,为我们很多初学者提供了宝贵的学习材料。

但有一点不完美的是,该源代码没有配套的文档,阅读起来可能有一定的障碍,尤其是对C/C++不熟的人来说.本人就一直用Java/VB作为主要的开发语言,C/C++上大学时倒是学过,不过工作之后一直没有再使用过,语法什么的忘的几乎一干二净了.但语言这东西,基本的东西都相通的,况且Java也是在C/C++的基础上形成的,有一定的相似处.阅读一遍源代码,主要的语法都应该不成问题了.

虽然在ICTCLAS的系统中没有完整的文档说明,但是我们可以通过查阅张华平和刘群发表的一些相关论文资料,还是可以窥探出主要的思路.

该分词系统的主要是思想是先通过CHMM(层叠形马尔可夫模型)进行分词,通过分层,既增加了分词的准确性,又保证了分词的效率.共分五层

基本思路:先进行原子切分,然后在此基础上进行N-最短路径粗切分,找出前N个最符合的切分结果,生成二元分词表,然后生成分词结果,接着进行词性标注并完成主要分词步骤.

下面是对源代码的主要内容的研究:

1.首先,ICTCLAS分词程序首先调用CICTCLAS_WinDlg::OnBtnRun()开始程序的执行.并且可以从看出它的处理方法是把源字符串分段处理。并且在分词前,完成词典的加载过程,即生成m_ICTCLAS对象时调用构造函数完成词典库的加载。关于词典结构的分析,请参加分词系统研究(二)。

void CICTCLAS_WinDlg::OnBtnRun()
{

......

//在此处进行分词和词性标记

if(!m_ICTCLAS.ParagraphProcessing((char *)(LPCTSTR)m_sSource,sResult))
m_sResult.Format("错误:程序初始化异常!");
else
m_sResult.Format("%s",sResult);//输出最终分词结果

......

}

2.在OnBtnRun()方法里面调用分段分词处理方法bool CResult::ParagraphProcessing(char *sParagraph,char *sResult)完成分词的整个处理过程,包括分词的词性标注.其中第一个参数为源字符串,第二个参数为分词后的字符串.在这两个方法中即完成了整个分词处理过程,下面需要了解的是在此方法中,如何调用其它方法一步步按照上图所示的分析框架完成分词过程.为了简单起见,我们先不做未登录词的分析。

//Paragraph Segment and POS Tagging
bool CResult::ParagraphProcessing(char *sParagraph,char *sResult)
{

........

Processing(sSentence,1); //Processing and output the result of current sentence.
Output(m_pResult[0],sSentenceResult,bFirstIgnore); //Output to the imediate result

.......

}

3.主要的分词处理是在Processing()方法里面发生的,下面我们对它进行进一步的分析.

bool CResult::Processing(char *sSentence,unsigned int nCount)
{

......

//进行二叉分词

m_Seg.BiSegment(sSentence, m_dSmoothingPara,m_dictCore,m_dictBigram,nCount);

......

//在此处进行词性标注

m_POSTagger.POSTagging(m_Seg.m_pWordSeg[nIndex],m_dictCore,m_dictCore);

......

}

4.现在我们先不管词性标注,把注意力集中在二叉分词上,因为这个是分词的两大关键步骤的第一步.

参考文章:

1.<<基于层叠隐马模型的汉语词法分析>>,刘群 张华平等

2.<<基于N-最短路径的中文词语粗分模型>>,张华平 刘群

(二)词典结构

ICTCLAS的词典结构是理解分词的重要依据,通过这么一个数据结构设计合理访问速度高效的词典才能达到快速准备的分词的目的。

通过阅读和分析源代码,我们可以知道,是程序运行初,先把词典加载到内存中,以提高访问的速度。源代码在Result.cpp的构造函数CResult()内实现了词典和分词规则库的加载。如下代码所示:

CResult::CResult()
{
……

m_dictCore.Load("data\\coreDict.dct");
m_POSTagger.LoadContext("data\\lexical.ctx");

……

}

我们再跳进Load方法具体分析它是怎样读取数据词典的,看Load的源代码:

bool CDictionary::Load(char *sFilename,bool bReset)
{
FILE *fp;
int i,j,nBuffer[3];

//首先判断词典文件能否以二进制读取的方式打开
if((fp=fopen(sFilename,"rb"))==NULL)
return false;//fail while opening the file

//为新文件释放内存空间
for( i=0;iri delete m_IndexTable[i].pWordItemHead[j].sWord;
delete [] m_IndexTable[i].pWordItemHead;
}
DelModified();//删除掉修改过的,可以先不管它

//CC_NUM:6768,应该是GB2312编码中常用汉字的数目6763个加上5个空位码
for(i=0;i {

//读取一个整形数字(词块的数目)
fread(&(m_IndexTable[i].nCount),sizeof(int),1,fp);
if(m_IndexTable[i].nCount>0)
m_IndexTable[i].pWordItemHead=new WORD_ITEM[m_IndexTable[i].nCount];
else
{
m_IndexTable[i].pWordItemHead=0;
continue;
}
j=0;

//根据前面读到的词块数目,循环读取一个个词块
while(j {

//读取三字整数,分别为频度(Frequency)/词内容长度(WordLen)/句柄(Handle)
fread(nBuffer,sizeof(int),3,fp);
m_IndexTable[i].pWordItemHead[j].sWord=new char[nBuffer[1]+1];

//读取词内容
if(nBuffer[1])//String length is more than 0
{
fread(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
}
m_IndexTable[i].pWordItemHead[j].sWord[nBuffer[1]]=0;
if(bReset)//Reset the frequency
m_IndexTable[i].pWordItemHead[j].nFrequency=0;
else
m_IndexTable[i].pWordItemHead[j].nFrequency=nBuffer[0];
m_IndexTable[i].pWordItemHead[j].nWordLen=nBuffer[1];
m_IndexTable[i].pWordItemHead[j].nHandle=nBuffer[2];
j+=1;//Get next item in the original table.
}
}
fclose(fp);
return true;
}

看完上面的源代码,词典的结构也应该基本清楚了.修改表的数据结构和上图差不多,但是在词块数目后面多了一个nDelete数目,即删除的数目

GB2312(1980年)一共收录了7445个字符,包括6763个汉字和682个其它符号。汉字区的内码范围高字节从B0-F7,低字节从A1-FE,占用的码位是72*94=6768。其中有5个空位是D7FA-D7FE。词典库图一所示的6768个块即对应GB2312编码中的这个6768个区位.图一中每一个大块代表以该字开头的所有词组,括号内的字为区位码对应的汉字,词典表中并不存在,为了说明方便才添加上去的.如下所示:

块6759
count:5
wordLen:2 frequency:0 handle:24832 word:(黯)淡
wordLen:2 frequency:1 handle:24942 word:(黯)淡
wordLen:2 frequency:3 handle:31232 word:(黯)然
wordLen:6 frequency:0 handle:27648 word:(黯)然神伤
wordLen:6 frequency:0 handle:26880 word:(黯)然失色
块6760
count:1
wordLen:2 frequency:0 handle:28160 word:(鼢)鼠

块6761
count:2
wordLen:4 frequency:0 handle:28160 word:(鼬)鼠皮
wordLen:2 frequency:0 handle:28160 word:(鼬)獾



对修改后如何保存的源代码进行分析:

bool CDictionary::Save(char *sFilename)
{
FILE *fp;
int i,j,nCount,nBuffer[3];
PWORD_CHAIN pCur;
if((fp=fopen(sFilename,"wb"))==NULL)
return false;//fail while opening the file

//对图一中所示的6768个数据块进行遍历
for(i=0;i {
pCur=NULL;
if(m_pModifyTable)
{

//计算修改后有效词块的数目

nCount=m_IndexTable[i].nCount+m_pModifyTable[i].nCount-m_pModifyTable[i].nDelete;
fwrite(&nCount,sizeof(int),1,fp);
pCur=m_pModifyTable[i].pWordItemHead;
j=0;

//对原表中的词块和修改表中的词块进行遍历,并把修改后的添加到原表中
while(pCur!=NULL&&j {

//如果修改表中的词长度小于原表中对应位置的词的长度或者长度相等但nHandle值比原表中的小,则把修改表中的写入到词典文件当中.

if(strcmp(pCur->data.sWord,m_IndexTable[i].pWordItemHead[j].sWord)<0||(strcmp(pCur->data.sWord,m_IndexTable[i].pWordItemHead[j].sWord)==0&&pCur->data.nHandle {//Output the modified data to the file
nBuffer[0]=pCur->data.nFrequency;
nBuffer[1]=pCur->data.nWordLen;
nBuffer[2]=pCur->data.nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(pCur->data.sWord,sizeof(char),nBuffer[1],fp);
pCur=pCur->next;//Get next item in the modify table.
}

//频度nFrequecy等于-1说明该词已被删除,跳过它
else if(m_IndexTable[i].pWordItemHead[j].nFrequency==-1)
{
j+=1;
}

//如果修改表中的词长度比原表中的长度大或 长度相等但句柄值要多,就把原表的词写入的词典文件中
else if(strcmp(pCur->data.sWord,m_IndexTable[i].pWordItemHead[j].sWord)>0||(strcmp(pCur->data.sWord,m_IndexTable[i].pWordItemHead[j].sWord)==0&&pCur->data.nHandle>m_IndexTable[i].pWordItemHead[j].nHandle))
{//Output the index table data to the file
nBuffer[0]=m_IndexTable[i].pWordItemHead[j].nFrequency;
nBuffer[1]=m_IndexTable[i].pWordItemHead[j].nWordLen;
nBuffer[2]=m_IndexTable[i].pWordItemHead[j].nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
j+=1;//Get next item in the original table.
}
}

//把原表中剩余的词写入的词典文件当中
if(j {
while(j {
if(m_IndexTable[i].pWordItemHead[j].nFrequency!=-1)
{//Has been deleted
nBuffer[0]=m_IndexTable[i].pWordItemHead[j].nFrequency;
nBuffer[1]=m_IndexTable[i].pWordItemHead[j].nWordLen;
nBuffer[2]=m_IndexTable[i].pWordItemHead[j].nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
}
j+=1;//Get next item in the original table.
}
}
else////原表已到尾部但修改表还没有遍历完,把修改表中剩余的词写入到词典文件当中
while(pCur!=NULL)//Add the rest data to the file.
{
nBuffer[0]=pCur->data.nFrequency;
nBuffer[1]=pCur->data.nWordLen;
nBuffer[2]=pCur->data.nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(pCur->data.sWord,sizeof(char),nBuffer[1],fp);
pCur=pCur->next;//Get next item in the modify table.
}
}



//不是修改标记,则把原表的数据全部写入到词典文件当中
else
{
fwrite(&m_IndexTable[i].nCount,sizeof(int),1,fp);
//write to the file
j=0;
while(j {
nBuffer[0]=m_IndexTable[i].pWordItemHead[j].nFrequency;
nBuffer[1]=m_IndexTable[i].pWordItemHead[j].nWordLen;
nBuffer[2]=m_IndexTable[i].pWordItemHead[j].nHandle;
fwrite(nBuffer,sizeof(int),3,fp);
if(nBuffer[1])//String length is more than 0
fwrite(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
j+=1;//Get next item in the original table.
}
}
}
fclose(fp);
return true;
}

增加一个词条目:

bool CDictionary::AddItem(char *sWord, int nHandle,int nFrequency)
{

char sWordAdd[WORD_MAXLENGTH-2];
int nPos,nFoundPos;
PWORD_CHAIN pRet,pTemp,pNext;
int i=0;

//预处理,去掉词的前后的空格
if(!PreProcessing(sWord, &nPos,sWordAdd,true))
return false;

//查找词典原表中该词是否存在
if(FindInOriginalTable(nPos,sWordAdd,nHandle,&nFoundPos))
{//The word exists in the original table, so add the frequency
//Operation in the index table and its items
if(m_IndexTable[nPos].pWordItemHead[nFoundPos].nFrequency==-1)
{//The word item has been removed
m_IndexTable[nPos].pWordItemHead[nFoundPos].nFrequency=nFrequency;
if(!m_pModifyTable)//Not prepare the buffer
{
m_pModifyTable=new MODIFY_TABLE[CC_NUM];
memset(m_pModifyTable,0,CC_NUM*sizeof(MODIFY_TABLE));
}
m_pModifyTable[nPos].nDelete-=1;
}
else
m_IndexTable[nPos].pWordItemHead[nFoundPos].nFrequency+=nFrequency;
return true;
}

//如果修改表为空,为它初始化空间

if(!m_pModifyTable)//Not prepare the buffer
{
m_pModifyTable=new MODIFY_TABLE[CC_NUM];
memset(m_pModifyTable,0,CC_NUM*sizeof(MODIFY_TABLE));
}

//在修改表中查询该词是否存在,如果存在增加该词的频度
if(FindInModifyTable(nPos,sWordAdd,nHandle,&pRet))
{
if(pRet!=NULL)
pRet=pRet->next;
else
pRet=m_pModifyTable[nPos].pWordItemHead;
pRet->data.nFrequency+=nFrequency;
return true;
}


//如果没有在修改表中找到,则添加进去

pTemp=new WORD_CHAIN;//Allocate the word chain node
if(pTemp==NULL)//Allocate memory failure
return false;
memset(pTemp,0,sizeof(WORD_CHAIN));//init it with 0
pTemp->data.nHandle=nHandle;//store the handle
pTemp->data.nWordLen=strlen(sWordAdd);
pTemp->data.sWord=new char[1+pTemp->data.nWordLen];
strcpy(pTemp->data.sWord,sWordAdd);
pTemp->data.nFrequency=nFrequency;
pTemp->next=NULL;

//插入到修改表中
if(pRet!=NULL)
{
pNext=pRet->next;//Get the next item before the current item
pRet->next=pTemp;//link the node to the chain
}
else
{
pNext=m_pModifyTable[nPos].pWordItemHead;
m_pModifyTable[nPos].pWordItemHead=pTemp;//Set the pAdd as the head node
}
pTemp->next=pNext;//Very important!!!! or else it will lose some node
//把词块数目加一
m_pModifyTable[nPos].nCount++;//the number increase by one
return true;
}



删除修改过的词条

bool CDictionary::DelModified()
{
PWORD_CHAIN pTemp,pCur;
if(!m_pModifyTable)
return true;


for(int i=0;i {
pCur=m_pModifyTable[i].pWordItemHead;

//删除链表上的节点
while(pCur!=NULL)
{
pTemp=pCur;
pCur=pCur->next;
delete pTemp->data.sWord;
delete pTemp;
}
}
delete [] m_pModifyTable;
m_pModifyTable=NULL;
return true;
}

//采用二分法进行查找

bool CDictionary::FindInOriginalTable(int nInnerCode,char *sWord,int nHandle,int *nPosRet)
{
PWORD_ITEM pItems=m_IndexTable[nInnerCode].pWordItemHead;
int nStart=0,nEnd=m_IndexTable[nInnerCode].nCount-1,nMid=(nStart+nEnd)/2,nCount=0,nCmpValue;
while(nStart<=nEnd)//Binary search
{
nCmpValue=strcmp(pItems[nMid].sWord,sWord);

//如果中间那个正好是要查找的
if(nCmpValue==0&&(pItems[nMid].nHandle==nHandle||nHandle==-1))
{
if(nPosRet)
{
if(nHandle==-1)//Not very strict match
{//Add in 2002-1-28
nMid-=1;

//Get the first item which match the current word
while(nMid>=0&&strcmp(pItems[nMid].sWord,sWord)==0)
nMid--;
if(nMid<0||strcmp(pItems[nMid].sWord,sWord)!=0)
nMid++;
}
*nPosRet=nMid;
return true;
}
if(nPosRet)
*nPosRet=nMid;
return true;//find it
}
else if(nCmpValue<0||(nCmpValue==0&&pItems[nMid].nHandle {
nStart=nMid+1;
}
else if(nCmpValue>0||(nCmpValue==0&&pItems[nMid].nHandle>nHandle&&nHandle!=-1))
{
nEnd=nMid-1;
}
nMid=(nStart+nEnd)/2;
}
if(nPosRet)
{
//Get the previous position
*nPosRet=nMid-1;
}
return false;
}



//在修改表中查询

bool CDictionary::FindInModifyTable(int nInnerCode,char *sWord,int nHandle,PWORD_CHAIN *pFindRet)
{
PWORD_CHAIN pCur,pPre;
if(m_pModifyTable==NULL)//empty
return false;
pCur=m_pModifyTable[nInnerCode].pWordItemHead;
pPre=NULL;

//sWord相等且句柄(nHandle)相等
while(pCur!=NULL&&(_stricmp(pCur->data.sWord,sWord)<0||(_stricmp(pCur->data.sWord,sWord)==0&&pCur->data.nHandle //sort the link chain as alphabet
{
pPre=pCur;
pCur=pCur->next;
}
if(pFindRet)
*pFindRet=pPre;
if(pCur!=NULL && _stricmp(pCur->data.sWord,sWord)==0&&(pCur->data.nHandle==nHandle||nHandle<0))
{//The node exists, delete the node and return
return true;
}
return false;
}



得到词的类型,共三种汉字、分隔符和其他

int CDictionary::GetWordType(char *sWord)
{
int nType=charType((unsigned char *)sWord),nLen=strlen(sWord);
if(nLen>0&&nType==CT_CHINESE&&IsAllChinese((unsigned char *)sWord))
return WT_CHINESE;//Chinese word
else if(nLen>0&&nType==CT_DELIMITER)
return WT_DELIMITER;//Delimiter
else
return WT_OTHER;//other invalid
}

(三)原子切分

ICTCLAS分词的第一步就是原子分词。但在进行原子切分之前,首先要进行断句处理。所谓断句,就是根据分隔符、回车换行符等语句的分隔标志,把源字符串分隔成多个稍微简单一点的短句,再进行分词处理,最后再把各个分词结果合起来,形成最终的分词结果。

分成短句之后,即可进行原子分词,所谓原子,是指该短句中不可分割的最小语素单位。一个汉字、短句前后的开始结束标识字段、全角标点符号、连在一起的数字字母单字节字符等。最后一种情况可以举例说明,比如:三星SHX-132型号的手机1元钱,则SHX-132、1都是一个原子,其它的每个汉字是一个原子。

按照这种方式,通过简单的汉字分割就形成了原子分词的结果,并对每个原子单位进行词性标注。nPOS=1表示是开始标记,nPOS=4表示结束标记,nPOS=0表示未识别词。

经过原子分词之后,下面即可进行初次分词。

(四)初次切分

经过原子分词后,源字符串成了一个个独立的最小语素单位。下面的初次切分,就是把原子之间所有可能的组合都先找出来。算法是用两个循环来实现,第一层遍历整个原子单位,第二层是当找到一个原子时,不断把后面相邻的原子和该原子组合到一起,访问词典库看它能否构成一个有意义有词组。

用数学方法可以做如下描述:

有一个原子序列:A(n)(0<=n
用伪码表示:

for(int I=0;I
String s=A[I];

for(int j=I+1;j
s+=A[j];

if(s是一个词组){

把s加入到初次切分的列表中;

记录该词组的词性;

记录该词组所在表中的坐标位置及其它信息;

}

else

break;

}

}

从上图三可以看出,在二维表中,初次切分后的词组,第一次字相同的在同一行,最后一个字相同的在同一列,原来的原子在对称轴上.

对上述过程进行处理的参考源代码如下:

bool CSegment::BiSegment(char *sSentence, double dSmoothingPara, CDictionary &dictCore, CDictionary &dictBinary, unsigned int nResultCount)
{

......

//在此处完成上图一的处理结果,生成一个链表结构

m_graphSeg.GenerateWordNet(sSentence,dictCore,true);//Generate words array


......

在生成图二所示的表结构之后,进一步生成二叉图表.

....

//Generate the biword link net

BiGraphGenerate(m_graphSeg.m_segGraph,aBiwordsNet,dSmoothingPara,dictBinary,dictCore);

....

对该函数进行深入分析:

bool CSegment::BiGraphGenerate(CDynamicArray &aWord, CDynamicArray &aBinaryWordNet,double dSmoothingPara,CDictionary &DictBinary,CDictionary &DictCore)
{
......

//获取链表的长度
m_nWordCount=aWord.GetTail(&pTail);//Get tail element and return the words count
if(m_npWordPosMapTable)
{//free buffer
delete [] m_npWordPosMapTable;
m_npWordPosMapTable=0;
}

//分配一个数组,存贮图二中每个结点的词的位置,如下图四所示
if(m_nWordCount>0)//Word count is greater than 0
m_npWordPosMapTable=new int[m_nWordCount];//Record the position of possible words


//把指针指向当前链表的开头,并计算每个词的位置,然后把它放到数组中

pCur=aWord.GetHead();
while(pCur!=NULL)//Set the position map of words
{
m_npWordPosMapTable[nWordIndex++]=pCur->row*MAX_SENTENCE_LEN+pCur->col;
pCur=pCur->next;
}

//遍历所有的结点,并计算相临两个词之间的平滑值

pCur=aWord.GetHead();
while(pCur!=NULL)//
{
if(pCur->nPOS>=0)//It's not an unknown words
dCurFreqency=pCur->value;
else//Unknown words
dCurFreqency=DictCore.GetFrequency(pCur->sWord,2);

//取得和当前结点列值(col)相同的下个结点
aWord.GetElement(pCur->col,-1,pCur,&pNextWords);
while(pNextWords&&pNextWords->row==pCur->col)//Next words
{
//前后两个词用@分隔符连接起来

strcpy(sTwoWords,pCur->sWord);
strcat(sTwoWords,WORD_SEGMENTER);
strcat(sTwoWords,pNextWords->sWord);

//计算两个连接词的边长
nTwoWordsFreq=DictBinary.GetFrequency(sTwoWords,3);
//Two linked Words frequency
dTemp=(double)1/MAX_FREQUENCE;
//计算平滑值
dValue=-log(dSmoothingPara*(1+dCurFreqency)/(MAX_FREQUENCE+80000)+(1-dSmoothingPara)*((1-dTemp)*nTwoWordsFreq/(1+dCurFreqency)+dTemp));
//-log{a*P(Ci-1)+(1-a)P(Ci|Ci-1)} Note 0 if(pCur->nPOS<0)//Unknown words: P(Wi|Ci);while known words:1
dValue+=pCur->value;

//Get the position index of current word in the position map table
nCurWordIndex=BinarySearch(pCur->row*MAX_SENTENCE_LEN+pCur->col,m_npWordPosMapTable,m_nWordCount);
nNextWordIndex=BinarySearch(pNextWords->row*MAX_SENTENCE_LEN+pNextWords->col,m_npWordPosMapTable,m_nWordCount);

//把当前结点在位置表中的位置和下个结点在位置表中的位置及平滑值/词性插入到二叉链表中
aBinaryWordNet.SetElement(nCurWordIndex,nNextWordIndex,dValue,pCur->nPOS);
pNextWords=pNextWords->next;//Get next word
}
pCur=pCur->next;
}
return true;
}

其中小数值代表了相临两个词之间的耦合成度,即构成更大长度词的可能性的机率,值越小说明两个词独立成词的可能性越大。

# 飞天小猪 发表于2006-05-26 00:17:00 IP: 58.49.193.*
一直关注中 偶也在做中文词性标注的毕业论文 请问 如图五所示的nPOS值是24832是什么意思?
急盼指点 谢谢

# sinboy 发表于2006-05-26 17:53:00 IP: 124.90.23.*
nPOS指的应该是词性

# sinboy 发表于2006-05-26 18:05:00 IP: 124.90.23.*
我现在还没有开始研究词性标记的处理部分,只是先分析分词的过程。读源代码累,搞清楚里面的原理更是困难。如果你也在研究这方面的东西,我们有时间多多交流一下。

# 飞天小猪 发表于2006-05-27 02:29:00 IP: 58.49.197.*
请教一下: 如果按照刘群和张化平的关于N最短路径求法的论文中介绍: 他说的确实在理 切分为他/说/的/确实/在理

然而用中科院的程序运行得到的结果为: 他/说/的/确实/在/理

与论文不符 请问这是怎么回事?盼指点

# 飞天小猪 发表于2006-05-27 02:40:00 IP: 58.49.197.*
对于图六中的数据是怎么计算得到的呢?

# sinboy 发表于2006-05-27 15:08:00 IP: 124.90.19.*
从源程序运行的结果来(对照图六),他认为分成:在/理两个词比成一个词的更好,从(9,11),(10,12)这两个的值得知。按照N-最短路径的思想,应该是生成N条最短路径,然后再选一个最佳的。但在源程序里面,我分析N可能被设置成了1。图六的生成结果是在函数BiGraphGenerate()里面实现的,就是计算(我想应该是统计它们在语料库中出现的概率)相邻两个词的耦合度。

(五)N最短路径

ICTCLAS和别的分司系统不一样的地方就是于--N最短路径分词算法。所谓N最短路径其实就是最短路径和最大路径的折中,保留前N个最优路径。这样做的目的就是对这两种方法取长补短,既能达到一个比较理解的分词不达意效果,又能保证分词不达意速度。在此处,我们中国人的中庸思想被完美体现:)。

在源程序中,N最短路径是在CNShortPath类里里面实现的。

bool CSegment::BiSegment(char *sSentence, double dSmoothingPara, CDictionary &dictCore, CDictionary &dictBinary, unsigned int nResultCount)
{

......

//调用构造函数,生成一个二维链表,如下图一所示。每个链表节点是一个队列,数据结构如下图二所示
CNShortPath sp(&aBiwordsNet,nResultCount);

//最短路径算法实现
sp.ShortPath();

//输出最短路径
sp.Output(nSegRoute,false,&m_nSegmentCount);

.....

}

对NShortPath的构造函数分进一步分析:

CNShortPath::CNShortPath(CDynamicArray *apCost,unsigned int nValueKind)
{
//研究(四)中图五所示的链表

m_apCost=apCost;//Set the cost
m_nValueKind=nValueKind;//Set the value kind

//顶点数
m_nVertex=apCost->m_nCol+1;
if(m_nVertexm_nRow+1)
m_nVertex=apCost->m_nRow+1;//Get the vertex numbers

m_pParent=new CQueue*[m_nVertex-1];//not including the first node
m_pWeight=new ELEMENT_TYPE *[m_nVertex-1];


for(unsigned int i=0;i {
m_pParent[i]=new CQueue[nValueKind];
m_pWeight[i]=new ELEMENT_TYPE[nValueKind];

}
}




int CNShortPath::ShortPath()
{
unsigned int nCurNode=1,nPreNode,i,nIndex;
ELEMENT_TYPE eWeight;
PARRAY_CHAIN pEdgeList;

for(;nCurNode {
CQueue queWork;
eWeight=m_apCost->GetElement(-1,nCurNode,0,&pEdgeList);//Get all the edges

//对研究(四)中的图六所示的表,按列优进行遍历,把每个列的数据放到一个临时工作队列中
while(pEdgeList!=0 && pEdgeList->col==nCurNode)
{
nPreNode=pEdgeList->row;
eWeight=pEdgeList->value;//Get the value of edges
for(i=0;i {
if(nPreNode>0)//Push the weight and the pre node infomation
{
if(m_pWeight[nPreNode-1][i]==INFINITE_VALUE)
break;

//把行值(ROW)放入队列中,并且保证队列的排序是按Weight值从小到大排列

queWork.Push(nPreNode,i,eWeight+m_pWeight[nPreNode-1][i]);
}
else
{
queWork.Push(nPreNode,i,eWeight);
break;
}
}//end for
pEdgeList=pEdgeList->next;

}//end while

//Now get the result queue which sort as weight.
//Set the current node information
for(i=0;i {
m_pWeight[nCurNode-1][i]=INFINITE_VALUE;
}
//memset((void *),(int),sizeof(ELEMENT_TYPE)*);
//init the weight
i=0;

//临时工作队列中取出前面的一个,并记路路径长度的和
while(i {//Set the current node weight and parent
if(m_pWeight[nCurNode-1][i]==INFINITE_VALUE)
m_pWeight[nCurNode-1][i]=eWeight;
else if(m_pWeight[nCurNode-1][i] {
i++;//Go next queue and record next weight
if(i==m_nValueKind)//Get the last position
break;
m_pWeight[nCurNode-1][i]=eWeight;
}
m_pParent[nCurNode-1][i].Push(nPreNode,nIndex);
}
}//end for

return 1;
}

int CNShortPath::Output(int **nResult,bool bBest,int *npCount)
{//sResult is a string array

......
GetPaths(m_nVertex-1,i,nResult,bBest);

}

//获取分词输出路径。指研究(四)中的图四

void CNShortPath::GetPaths(unsigned int nNode,unsigned int nIndex,int **nResult,bool bBest)
{
CQueue queResult;
unsigned int nCurNode,nCurIndex,nParentNode,nParentIndex,nResultIndex=0;

if(m_nResultCount>=MAX_SEGMENT_NUM)//Only need 10 result
return ;
nResult[m_nResultCount][nResultIndex]=-1;//Init the result
queResult.Push(nNode,nIndex);
nCurNode=nNode;
nCurIndex=nIndex;
bool bFirstGet;
while(!queResult.IsEmpty())
{
while(nCurNode>0)//
{//Get its parent and store them in nParentNode,nParentIndex
if(m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,0,false,true)!=-1)
{
nCurNode=nParentNode;
nCurIndex=nParentIndex;
}
if(nCurNode>0)
queResult.Push(nCurNode,nCurIndex);
}
if(nCurNode==0)
{ //Get a path and output
nResult[m_nResultCount][nResultIndex++]=nCurNode;//Get the first node
bFirstGet=true;
nParentNode=nCurNode;
while(queResult.Pop(&nCurNode,&nCurIndex,0,false,bFirstGet)!=-1)
{
nResult[m_nResultCount][nResultIndex++]=nCurNode;
bFirstGet=false;
nParentNode=nCurNode;
}
nResult[m_nResultCount][nResultIndex]=-1;//Set the end
m_nResultCount+=1;//The number of result add by 1
if(m_nResultCount>=MAX_SEGMENT_NUM)//Only need 10 result
return ;
nResultIndex=0;
nResult[m_nResultCount][nResultIndex]=-1;//Init the result

if(bBest)//Return the best result, ignore others
return ;
}
queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top node
while(queResult.IsEmpty()==false&&(m_pParent[nCurNode-1][nCurIndex].IsSingle()||m_pParent[nCurNode-1][nCurIndex].IsEmpty(true)))
{
queResult.Pop(&nCurNode,&nCurIndex,0);//Get rid of it
queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top node
}
if(queResult.IsEmpty()==false&&m_pParent[nCurNode-1][nCurIndex].IsEmpty(true)==false)
{
m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,0,false,false);
nCurNode=nParentNode;
nCurIndex=nParentIndex;
if(nCurNode>0)
queResult.Push(nCurNode,nCurIndex);
}
}
}


最终得到最短路么(0,1,2,3,6,9,11,12),里面的数值分别对应研究(四)中图四的下标,到此分词的第一大步就结束了,并形成最终结果:始##始/他/说/的/确实/在/理/末##末

2.
From http://qxred.yculblog.com/post.1204714.html

ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注

风暴红QxRed @ 2006-04-20 20:38


中科院分词系统概述

这几天看完了中科院分词程序的代码,现在来做一个概述,并对一些关键的数据结构作出解释


〇、总体流程

考虑输入的一句话,sSentence="张华平欢迎您"

总体流程:

一、分词 "张/华/平/欢迎/您"

二、posTagging "张/q 华/j 平/j 欢迎/v 您/r"

三、NE识别:人名识别,音译名识别,地名识别 "张/q 华/j 平/j 欢迎/v 您/r" "张华平/nr"

四、重新分词:"张华平/欢迎/您"

五、重新posTagging: "张华平/nr 欢迎/v 您/r"




技术细节

一、分词

分词程序首先在其头末添加开始符和结束符
sSentence="始##始张华平欢迎您末##末"

然后是分词,基本思想就是分词的得到的词的联合概率最大

假设 "张华平欢迎您" 分为 "w_1/w_2/.../w_k" 则
w_1/w_2/.../w_k=argmax_{w_1'/w_2'/.../w_k'}P(w_1',w_2',...,w_k')=argmax_{w_1'/w_2'/.../w_k'}P(w_1')P(w_2')...P(w_k')

细节:

首先给原句按字划分,所有汉字一个一段,连续的字母,数字一段,比如"始##始张华平2006欢迎您asdf末##末"被划为"始##始/张/华/平/2006/欢/迎/您/asdf/末##末"

接着找出这个句子中所有可能出现的词,比如"始##始张华平欢迎您末##末",出现的词有"始##始","张","华","平","欢","迎","您","末##末","欢迎"
并查找这些词所有可能的词性和这些词出现的频率。

将这些词保存在一个结构中,具体实现如下:

m_segGraph中有一个(PARRAY_CHAIN)m_pHead,是一个链

(PARRAY_CHAIN)p->row//记录该词的头位置
(PARRAY_CHAIN)p->col//记录该词的末位置
(PARRAY_CHAIN)p->value//记录该词的-log(出现的概率),出现的频率指所有该词的所有词性下出现的概率的总和。
(PARRAY_CHAIN)p->nPos//记录该词的词性,比如人名标记为'nr',则对应的nPos='n'*256+'r',如果该词有很多词性,则nPos=0
(PARRAY_CHAIN)p->sWord//记录该词
(PARRAY_CHAIN)p->nWordLen//记录该词的长度

举个例子:
"0 始##始 1 张 2 华 3 平 4 欢 5 迎 6 您 7 末##末 8"

对于"张"来说,
row=1
col=2
value=-log[("张"出现的频率+1)/(MAX_FREQUENCE)]
nPos=0//"张"有5种词性
sWord="张"
nWordLen=2

保存的顺序是按col升序row升序的次序排列

m_segGraph.m_pHead "始##始"
"张"
"华"
"平"
"欢"
"欢迎"
"迎"
"您"
"末##末"

m_segGraph.m_nRow=7
m_segGraph.m_nCol=8


然后是生成一幅给予各种组合情况的图,并按照出现的概率大小保存概率最大的前m_nValueKind个结果。

细节:

初始化,
(CNShortPath)sp.m_apCost=m_segGraph;
(CNShortPath)sp.m_nVertex=m_segGraph.m_nCol+1
(CNShortPath)sp.m_pParent=CQueue[m_segGraph.m_nCol][m_nValueKind]
(CNShortPath)sp.m_pWeight=ELEMENT_TYPE[m_segGraph.m_nCol][m_nValueKind]//m_pWeight[0][0]表示1处的weight

sp.ShortPath()函数中,
for(nCurNode=1;nCurNode{
CQueue queWork;//零时的CQueue
eWeight=m_apCost->GetElement(-1,nCurNode,0,&pEdgeList);//取出col=nCurNode的第一个PARRAY_CHAIN的value,比如nCurNode=6,则pEdgeList指向"欢迎",eWeight="pEdgeList->value
while(pEdgeList&&pEdgeList->col==nCurNode)//对每一个col=nCurNode的pEdgeList
{

for(i=0;i {
queWork.Push(pEdgeList->row,0,eWeight+m_pWeight[pEdgeList->row-1][i]);
//将所有col=nCurNode的pEdgeList按照其weight升序放到queWork中
}
}//比如
/*
"欢迎" m_pWeight[3][0]=0.2 eWight=0.2 =>queWork.Push(4,0,0.4);
"0 始##始 1 张 2 华 3 平 4 欢 5 迎 6 您 7 末##末 8"
"欢" m_pWeight[4][0]=0.5 eWight=0.1 =>queWork.Push(5,0,0.6);
m_pWeight[4][1]=0.6 eWight=0.1 =>queWork.Push(5,0,0.7);

queWork "欢迎" 0.4
"迎" 0.6
"迎" 0.7

*/
for(i=0;i while(ivalue
{
m_pWeight[nCurNode-1][i]=eWeight;//取前m_nValueKind个结果
m_pParent[nCurNode-1][i].Push(nPreNode,nIndex);//按照pEdgeList->value的升序,也就是P的降序放入m_pParent
}
}

得到m_pParent之后,按照m_pWeight[m_segGraph.m_nCol-1]的升序,生成path
CNShortPath::GetPaths(unsigned int nNode,unsigned int nIndex,int **nResult,bool bBest)
//nNode=m_segGraph.m_nCol,nIndex从0取到m_nValueKind-1,nResult输出结果,bBest=true只输出最佳结果
比如"始##始张华平欢迎您末##末"的结果为
nResult[0]={0,1,2,3,4,6,7,8,-1} "始##始/张/华/平/欢迎/您/末##末"
nResult[1]={0,1,2,3,4,5,6,7,8,-1} "始##始/张/华/平/欢/迎/您/末##末"
没有第三种结果

取出所有nResult[i]作为分词结果,结果保存在m_graphOptimum中,m_graphOptimum和m_segGraph结构一样,只不过只存nResult[i]中的结果:

如果m_nValueKind=1则
m_graphOptimum.m_pHead "始##始"
"张"
"华"
"平"
"欢迎"
"您"
"末##末"

m_graphOptimum.m_nRow=7
m_graphOptimum.m_nCol=8


如果m_nValueKind=2则

m_graphOptimum.m_pHead "始##始"
"张"
"华"
"平"
"欢"
"欢迎"
"迎"
"您"
"末##末"

m_graphOptimum.m_nRow=7
m_graphOptimum.m_nCol=8


见 bool CSegment::GenerateWord(int **nSegRoute, int nIndex)这里的nSegRoute=上面的nResult,是输入参数;nIndex表示第nIndex个分词结果


同时,CResult.m_Seg.m_pWordSeg[nIndex][k]中保存了第nIndex个结果的第k个词的信息:

CResult.m_Seg.m_pWordSeg[nIndex][k].sWord//词
CResult.m_Seg.m_pWordSeg[nIndex][k].nHandle//词性
CResult.m_Seg.m_pWordSeg[nIndex][k].dValue//-logP

至此,分词部分结束

二、posTagging


m_POSTagger.POSTagging(m_Seg.m_pWordSeg[nIndex],m_dictCore,m_dictCore);//对第nIndex个分词结果用标准的字典标注
方便起见,下面假设m_nValueKind=1


m_POSTagger用HMM对分词进行标注,这里输出概率为P(w_i|c_i),c_i为词性,w_i为词;转移概率为P(c_i|c_{i-1}),初始状态为P(c_0)即P("始##始"的词性)
用维特比算法求出一个c_1/c_2/.../c_k=argmax_{c_1'/c_2'/.../c_k'}P(w_1',w_2',...,w_k')

将句子分成若干段,每段以有唯一pos的w结尾,也就是分词中CResult.m_Seg.m_pWordSeg[0][k].nHandle>0的那些词

比如,举个例子
"0 始##始 1 张 2 华 3 平 4 欢迎 5 您 6 末##末 7"
pos1 pos1 pos1 pos1 pos1 pos1 pos1
pos2 pos2 pos2 pos2
pos3 pos3 pos3
pos4
pos5

则该句被划分为
"0 始##始"
"1 张 2 华 3 平 4 欢迎 5 您"
"6 末##末"
对每一段用维特比算法确定一个唯一的postag

细节:

首先P(w,c)的输出概率存储在dict中,比如dictCore,dictUnknow,通过dict.GetFrequency(char *sWord, int nHandle)函数获取 sWord pos为nHandle的函数
概率P(c)存储在context中,比如m_context,通过context.GetFrequency(int nKey, int nSymbol)函数获取 pos为nSymbol的函数,nKey=0
转移概率P(c|c')存储在context中,比如m_context,通过context.GetContextPossibility(int nKey, int nPrev, int nCur)函数获取 c'=nPrev,c=nCur的转移概率,nKey=0

重要的数据结构

m_nTags[i][k]表示第i个w的第k个pos
在GetFrom函数中表示 -log(第i个w的第k个pos的输出概率)
在CSpan::Disamb()函数中
m_dFrequency[i][k]表示 -log(从第0个w到第i个w的第k个pos的联合最大输出概率),比如


w_j w_{j+1}
m_dFrequency[j][0]-- m_dFrequency[j+1][0]
m_dFrequency[j][1] -- m_dFrequency[j+1][1]
--m_dFrequency[j+1][2]



则 图中的路径的权为W([j,0]->[j+1,2])=m_dFrequency[j][0]-log(m_context.GetContextPossibility(0,m_nTags[j][0],m_nTags[j+1][2]))
这样,选择
m_dFrequency[j+1][2]=min{W([j,0]->[j+1,2]),W([j,1]->[j+1,2])}


m_nCurLength表示当前段的w个数+1

在m_POSTagger.POSTagging中,以上面的例子为例
while(i>-1&&pWordItems[i].sWord[0]!=0)//将执行段的个数次,比如上例中将执行3次
{
i=GetFrom(pWordItems,nStartPos,dictCore,dictUnknown);//i=GetFrom(pWordItems,0,dictCore,dictUnknown)=1
//i=GetFrom(pWordItems,1,dictCore,dictUnknown)=6
//i=GetFrom(pWordItems,6,dictCore,dictUnknown)=7
//从nStartPos向前取w,一直取到一个有唯一pos的w为止,该过程中记录每个w的pos,保存在m_nTags中,记录log(w|c)输出概率保存在m_dFrequency中
GetBestPOS();//调用Disamb()函数,用维特比算法找出该段的最佳(联合输出概率最大)的标注,最佳路径保存在m_nBestTag中
通过读取m_nBestTag对pWordItems.nHandle进行赋值
}


三、NE识别:人名识别,音译名识别,地名识别

其基本思路和PosTagging一样,只不过词性c换成了role r,以人名识别为例,首先识别出人名的tag(即pos),见
"Chinese Named Entity Recognition Using Role Model"
在函数CUnknowWord::Recognition(PWORD_RESULT pWordSegResult, CDynamicArray &graphOptimum,CSegGraph &graphSeg,CDictionary &dictCore)中
每个被切开的段被识别完之后,用m_roleTag.POSTagging(pWordSegResult,dictCore,m_dict);对第一步分词的结果进行一次标记。
首先用dictUnknown.GetHandle(m_sWords[i],&nCount,aPOS,aFreq);获得m_sWords[i]在NE词典中的role,
接着用dictCore.GetHandle(m_sWords[i],&nCount,aPOS,aFreq);获得m_sWords[i]在标准词典中的tag,这里只要m_sWords[i]在标准词典中有tag,那么tag一律标记为0,该tag下的输出概率为P(w|c)=P(sum_{aFreq}|c=0)
接下来用SplitPersonPOS(dictUnknown)函数将其中tag为LH和TR的w拆成两个
比如"张/SS 华/GH 平欢/TR 迎/RC 您/RC"中"平欢"被拆成"平/GT" "欢/12"
接着在PersonRecognize(dictUnknown);函数中,用一些模板进行匹配,"SS/GH/TR"将匹配到"张华平"。匹配得到的片断保存在m_nUnknownWords中,其nHandle被设置为人名,地名,音译名中的一个
对第一步中的graphOptimum,加入m_nUnknownWords的边:
graphOptimum.GetElement(nAtomStart,nAtomEnd,&dValue,&nPOSOriginal);
if(dValue>m_roleTag.m_dWordsPossibility[i])//Set the element with less frequency
graphOptimum.SetElement(nAtomStart,nAtomEnd,m_roleTag.m_dWordsPossibility[i],m_nPOS);

四、重新分词

对上一步的graphOptimum,用第一步中对m_segGraph分词的方法,找出一个联合概率最大的分词结果:
m_Seg.OptimumSegmet(nCount);

五、重新标注

对于四中分好的结果,用标准词典对其进行posTagging:
for(nIndex=0;nIndex{
m_POSTagger.POSTagging(m_Seg.m_pWordSeg[nIndex],m_dictCore,m_dictCore);
}


最后,用Sort();对标注结果按照联合输出概率的大小降序排序,并按照用户的需求输出前几个

3.
From http://www.cnblogs.com/zhenyulu/articles/653254.html

(按:作者有点言过其实,制造噱头的嫌疑,^_^,以下未删节)

ICTCLAS分词系统是由中科院计算所的张华平、刘群所开发的一套获得广泛好评的分词系统,该版的Free版开放了源代码,为初学者提供了宝贵的学习材料。我们可以在“http://sewm.pku.edu.cn/QA/”找到FreeICTCLASLinux.tar的C++代码。

可是目前该版本的ICTCLAS并没有提供完善的文档,所以阅读起来有一定的难度,所幸网上可以找到一些对ICTCLAS进行代码分析的文章,对理解分词系统的内部运行机制提供了很大的帮助。这些文章包括:

1)http://blog.csdn.net/group/ictclas4j/;《ICTCLAS分词系统研究(一)~(六)》作者:sinboy。

2)http://qxred.yculblog.com/post.1204714.html;《ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注》作者:风暴红QxRed 。

按照上面这些文章的思路去读ICTCLAS的代码,可以比较容易的理顺思路。然而在我阅读代码的过程中,越来越对ICTCLAS天书般的代码感到厌烦。我不得不佩服中科院计算所的人思维缜密,头脑清晰,能写出滴水不漏而又让那些“头脑简单”的人百思不得其解的代码。将一件本来很简单的事情做得无比复杂...

ICTCLAS中有一个名为CDynamicArray的类,存放在DynamicArray.cpp与DynamicArray.h两个文件中,这个DynamicArray是干什么用的?经过一番研究后终于明白是一个经过排序的链表。为了表达的更明白些,我们不妨看下面这张图:



(图一)

上面这张图是一个按照index值进行了排序的链表,当插入新结点时必须确保index值的有序性。DynamicArray类完成的功能基本上与上面这个链表差不多,只是排序规则不是index,而是row和col两个数据,如下图:



(图二)

大家可以看到,这个有序链表的排序规则是先按row排序,row相同的按照col排序。当然排序规则是可以改变的,如果先按col排,再按row排,则上面的链表必须表述成:



(图三)

在了解了这些内容的基础上,不妨让我们看看ICTCLAS中DynamicArray.cpp中的代码实现(这里我们只看GetElement方法的实现,其基本功能为给出row与col,然后将对应的元素取出来)。

Copy CodeDynamicArray.cpp
ELEMENT_TYPE CDynamicArray::GetElement(int nRow, int nCol, PARRAY_CHAIN pStart,
PARRAY_CHAIN *pRet)
{
PARRAY_CHAIN pCur = pStart;
if (pStart == 0)
pCur = m_pHead;
if (pRet != 0)
*pRet = NULL;
if (nRow > (int)m_nRow || nCol > (int)m_nCol)
//Judge if the row and col is overflow
return INFINITE_VALUE;
if (m_bRowFirst)
{
while (pCur != NULL && (nRow != - 1 && (int)pCur->row < nRow || (nCol !=
- 1 && (int)pCur->row == nRow && (int)pCur->col < nCol)))
{
if (pRet != 0)
*pRet = pCur;
pCur = pCur->next;
}
}
else
{
while (pCur != NULL && (nCol != - 1 && (int)pCur->col < nCol || ((int)pCur
->col == nCol && nRow != - 1 && (int)pCur->row < nRow)))
{
if (pRet != 0)
*pRet = pCur;
pCur = pCur->next;
}
}
if (pCur != NULL && ((int)pCur->row == nRow || nRow == - 1) && ((int)pCur
->col == nCol || nCol == - 1))
//Find the same position
{
//Find it and return the value
if (pRet != 0)
*pRet = pCur;
return pCur->value;
}
return INFINITE_VALUE;
}
这里我先要说明的是程序中的m_bRowFirst变量,它表示是先按row大小排列还是先按col大小排列。如果m_bRowFirst为逻辑真值,那么链表就如上面图二所示,如果为假,则如图三所示。

除了这个外,看到上面长长的条件表达式,你一定会吓坏了吧!更让人吓坏的是调用这段程序的代码:

Copy Code对GetElement方法的调用

//来自NShortPath.cpp中ShortPath方法
eWeight = m_apCost->GetElement( -1, nCurNode, 0, &pEdgeList);

//来自Segment.cpp中BiGraphGenerate方法
aWord.GetElement(pCur->col, -1, pCur, &pNextWords);//Get next words which begin with pCur->col
 
先分析第一个调用
第一个调用给GetElement方法的nRow传递了-1,他想干什么呢?

假设这时候变量m_bRowFirst为true,并且传递过去的nCol!=-1,那么while (pCur != NULL && (nRow != - 1 && (int)pCur->row < nRow || (nCol != -1 && (int)pCur->row == nRow && (int)pCur->col < nCol))) 等价于while (pCur != NULL && ( (int)pCur->row == -1 && (int)pCur->col < nCol))) ,注意红色部分在程序运行时永远为false(因为根本就不存在row为-1的结点),因此,上面的表达式等价于while(false)!这对于该段程序没有任何意义!

因此我们可以得到这样一个结论:如果GetElement方法的nRow参数取-1,当且仅当m_bRowFirst为false时才有意义。这时候,代码中第二个while得到执行,让我们分析一下:

while (pCur != NULL && (nCol != - 1 && (int)pCur->col < nCol || ((int)pCur->col == nCol && nRow != - 1 && (int)pCur->row < nRow))) 在nRow为-1时等价于while (pCur != NULL && ((int)pCur->col < nCol ) ,这就容易解释的多了:在如图三所示的链表中查找col=nCol 的第一个结点。

My God!

再分析第二个调用
上面的第二个调用就更让人摸不着头脑了:将pCur->col传递给GetElement的nRow参数,并将-1传递给nCol参数,这想干什么呢?要想分析清楚这个问题,没有个把钟头恐怕不行(再次佩服这些中科院的牛人们)。

按照“分析第一个调用”中的结论可知,如果GetElement方法的nCol参数取-1,当且仅当m_bRowFirst为true时才有意义。因此链表排序一定是先按照行排(如图二),此时对DynamicArray的GetElement方法的调用可以简化成:

Copy Code对方法调用进行剥离和简化
//来自Segment.cpp中BiGraphGenerate方法
aWord.GetElement(pCur->col, -1, pCur, &pNextWords);

//======================================================================

ELEMENT_TYPE CDynamicArray::GetElement(int nRow, int nCol, PARRAY_CHAIN pStart, PARRAY_CHAIN *pRet)
// 经过调用后,上面的形参对应的值分别是:nRow:pStart->col, nCol:-1, pStart, &pNextWords
// 注意,为了和下面代码中的pCur以示区分,这里用了pStart这个变量名。
{
......

while (pCur != NULL && ((int)pCur->row < pStart->col))
{
if (pRet != 0)
*pRet = pCur;
pCur = pCur->next;
}

if (pCur != NULL && ((int)pCur->row == pStart->col)
//Find the same position
{
//Find it and return the value
if (pRet != 0)
*pRet = pCur;
return pCur->value;
}
return INFINITE_VALUE;
} 
此时的意义就比较明显了,其实就是找pCur->row == pStart->col的那个结点。

可有人会问,干吗把row和col扯到一起呢?这又是一个非常复杂的问题。具体内容可以参考sinboy的《ICTCLAS分词系统研究(四)--初次切分》一文。这里简单解释如下:

如图四,这是row优先排列的一个链表:



图四

用二维表来表示图四中的链表结构如下图五所示:



图五

然后找出相邻两个词的平滑值。例如“他@说”、“的@确”、“的@确实”、“的确@实”、“的确@实在”等。如果仔细观察的话,可以注意到以下特点:例如“的确”这个词,它的col = 5,需要和它计算平滑值的有两个,分别是“实”和“实在”,你会发现这两个词的row = 5。同样道理,“确”的col = 5,它也需要和“实”与“实在”(row = 5)分别计算平滑值。

其实,这就是为什么上面分析的找pCur->row == pStart->col的那个结点的原因了。最终得到的平滑值图可以表述成图六:



图六

到此为止才明白代码作者的真正用意:

Copy Code将该调用放到上下文中再次查看
//========= 来自Segment.cpp中BiGraphGenerate方法 ===========
...... 
//取得和当前结点列值(col)相同的下个结点
aWord.GetElement(pCur->col, -1, pCur, &pNextWords);
while(pNextWords&&pNextWords->row==pCur->col)//Next words
{
//前后两个词用@分隔符连接起来
strcpy(sTwoWords,pCur->sWord);
strcat(sTwoWords,WORD_SEGMENTER);
strcat(sTwoWords,pNextWords->sWord);
......
}

小结
想不到短短一个GetElement方法中竟然综合考虑了1)row优先排序的链表;2)col优先排序的链表;3)当nRow为-1时的行为(只有m_bRowFirst为false时才能这么做,代码中没有指,所以非常容易出错!);4)当nCol为-1时的行为;5)当nRow与nCol都不为-1时的行为。

这也难怪我们会看到诸如while (pCur != NULL && (nRow != - 1 && (int)pCur->row < nRow || (nCol != -1 && (int)pCur->row == nRow && (int)pCur->col < nCol))) 这样的逻辑表达式了!我们也不得不佩服代码书写者复杂的逻辑思维能力(离散数学的谓词逻辑一定学得超级好)和给代码阅读者制造障碍的能力!类似代码在ICTCLAS中比比皆是,看来我只能恨自己脑筋太简单了!

4.
http://www.cnblogs.com/zhenyulu/articles/657017.html

上篇文章《天书般的ICTCLAS分词系统代码(一)》 说了说ICTCLAS分词系统有些代码让人无所适从,需要好一番努力才能弄明白究竟是怎么回事。尽管有很多人支持应当写简单、清晰的代码,但也有人持不同意见。主要集中在(1)如果效率高,代码复杂点也行; (2)只要注释写得好就行;(3)软件关键在思路(这我同意),就好像买了一台电脑,不管包装箱内的电脑本身怎么,一群人偏在死扣那个外面透明胶带帖歪了(这我坚决不同意,因为只有好思路出不来好电脑,好电脑还要性能稳定,即插即用的好硬件;另外天书般的代码不仅仅是透明胶带 贴歪的问题,他甚至可能意味着电脑中的绝缘胶带失效了...)。

这两天在抓紧学习ICTCLAS分词系统的思路的同时,也在消化学习它的代码实现,然而我看到的代码已经不仅仅是为了效率牺牲代码清晰度的问题了,我看到的是连作者都不知道自己真正想要做什么了,尽管程序的执行结果是正确的!

为了说明这种情况的严重性,我们需要从CQueue.cpp这个文件着手。我对CQueue这个类颇有些微辞,明明是个Queue,里面确用的是Push、Pop方法(让人感觉是个Stack而不是Queue),而且Pop方法纯粹是个大杂烩,不过这些都不是原则性问题,毕竟每个人有每个人写代码的习惯。CQueue完成的工作是制造一个排序队列(按照eWeight从小到大排序),如图一:



(图一)

在了解了这些内容的基础上,让我们看看ICTCLAS中NShortPath.cpp中的代码实现(这里我们只看ShortPath方法的实现) ,为了让问题暴露得更清晰一些,我简化了代码中一些不相关的内容。

Copy Code来自NShortPath.cpp中的ShortPath方法
int CNShortPath::ShortPath()
{
......
for (; nCurNode < m_nVertex; nCurNode++)
{
CQueue queWork;

//此处省略的代码主要负责将一些结点按照eWeight从
//小到大的顺序放入队列queWork
......

//初始化权重
for (i = 0; i < m_nValueKind; i++)
m_pWeight[nCurNode - 1][i] = INFINITE_VALUE;

i = 0;
while (i < m_nValueKind && queWork.Pop(&nPreNode, &nIndex, &eWeight) != -1)
{
//Set the current node weight and parent
if (m_pWeight[nCurNode - 1][i] == INFINITE_VALUE)
m_pWeight[nCurNode - 1][i] = eWeight;
else if (m_pWeight[nCurNode - 1][i] < eWeight)
//Next queue
{
i++; //Go next queue and record next weight
if (i == m_nValueKind)
//Get the last position
break;
m_pWeight[nCurNode - 1][i] = eWeight;
}
m_pParent[nCurNode - 1][i].Push(nPreNode, nIndex);
}
}
......
}
上面的代码作者想干什么?让我们来分析一番:

变量queWork中存放的是一个按照eWeight从小到大排列的队列, 我们不妨假设里面有4个元素,其eWeight值分别是5、6、7、8。另外我们假设变量m_nValueKind的值为2,即查找最短的两条路径(注意:这种说法不完全正确,后面会解释为什么)。在此假设基础上,我们看看程序是如何运行的:

1)将所有m_pWeight[nCurNode - 1][i]初始化为INFINITE_VALUE。

2)在第一轮循环中,我们从queWork中取出第一个元素,其eWeight为5,注意表达式“if (m_pWeight[nCurNode - 1][i] == INFINITE_VALUE) ”没有任何作用,因为我们在第一步将所有m_pWeight[nCurNode - 1][i] 均初始化成了INFINITE_VALUE,所以第一轮循环该条件一定为true。

3)在第二轮循环中,我们从queWork中取出第二个元素,其eWeight为6,此时表达式“else if (m_pWeight[nCurNode - 1][i] < eWeight) ”似乎就没有什么作用了,因为queWork是经过排序的,第二个元素的eWeight不会小于第一个eWeight,对于我们这个例子来说, 该表达式一定为true,于是就让 i++。

4)紧接着你会发现程序重新进入了步骤2)的循环。

程序执行结果如图二:



(图二)

如果真是这样的话,上面的代码似乎可以简化成:

Copy Code简化后的程序
int CNShortPath::ShortPath()
{
......
for (; nCurNode < m_nVertex; nCurNode++)
{
CQueue queWork;

//此处省略的代码主要负责将一些结点按照eWeight从
//小到大的顺序放入队列queWork
......

//初始化权重
for (i = 0; i < m_nValueKind; i++)
m_pWeight[nCurNode - 1][i] = INFINITE_VALUE;

i = 0;
while (i < m_nValueKind && queWork.Pop(&nPreNode, &nIndex, &eWeight) != -1)
{
m_pWeight[nCurNode - 1][i] = eWeight;
m_pParent[nCurNode - 1][i].Push(nPreNode, nIndex);
i++;
}
}
......
}
对于上面这个案例,简化后的程序与ICTCLAS中的程序执行结果完全相同。可作者写出如此复杂的代码应当是有理由的,难道我们对代码的分析有什么问题吗?

是的!作者将一个最为重要的内容作为隐含条件放入了代码之中,我们只能通过 if 条件以及 else if 条件中的内容推断出这个隐含条件究竟是什么,而这个隐含的条件恰恰应当是这段代码中最关键的内容。如果没能将最关键的内容展现在代码当中,而是需要读者去推断的话,我只能说连作者自己都不清楚究竟什么是最关键的东西,仅仅是让程序执行没有错误而已。

那么究竟隐藏了什么关键的内容呢?那就是“m_pWeight[nCurNode - 1][i] = eWeight”这个条件。在ShortPath方法代码中,作者用了 if 条件、 else if 条件,但都没有提及等于eWeight时程序的执行行为,他将这个留给了读者去推敲,看出来这个隐含条件就看出来了,看不出来就只能怪你自己笨了。

我们更换一组数据来看看:假设queWork里面有4个元素,其eWeight值分别是5、6、6、7,还假设变量m_nValueKind的值为2,那么ICTCLAS中ShortPath程序执行结果是什么呢?读者可以根据代码自己推敲一下,然后再看看下面的结果,与你预期的一样不一样。如图三。



(图三)

这里m_Parent[nCurNode - 1][2]是一个CQueue,里面存入了eWeight为6的两个结点。这也是为什么我前文说,NShortPath中 N 如果取2,并不意味着只有两条路径。

如果那位有耐心看到这里,对ICTCLAS中的NShortPath.cpp代码有什么感觉呢?其实要想写出一个比较清晰的代码并不复杂,只要你真正了解究竟什么是最重要的东西,对于NShortPath.cpp中的代码,只要我们稍加修改,就可以让这天书般的代码改善不少。经过调整后的代码如下:

Copy Code重新改造后的代码
int CNShortPath::ShortPath()
{
......
for (; nCurNode < m_nVertex; nCurNode++)
{
CQueue queWork;

//此处省略的代码主要负责将一些结点按照eWeight从
//小到大的顺序放入队列queWork
......

//初始化权重
for (i = 0; i < m_nValueKind; i++)
m_pWeight[nCurNode - 1][i] = INFINITE_VALUE;

if(queWork.Pop(&nPreNode, &nIndex, &eWeight) != -1)
{
for(i=0; i < m_nValueKind ; i++)
{
m_pWeight[nCurNode - 1][i] = eWeight;
do
{
m_pParent[nCurNode - 1][i].Push(nPreNode, nIndex);
if(queWork.Pop(&nPreNode, &nIndex, &new_eWeight) == -1)
goto finish;
}while(new_eWeight == eWeight)

eWeight = new_eWeight;
}
}
}
finish:
......
}
经过改造的代码使用了一个do...while循环,并利用了goto命令简化代码结构,我想这样的代码读起来应当清晰多了吧。

小结
(1)软件关键在思路,只有真正了解思路的人才能写出清晰的代码。如果代码不清晰,说明思路根本不清晰。

(2)注释写得好不如代码结构清晰。

(3)除非经过测试,否则不要为了一点效率提升而损失代码的可读性。



<< Home

This page is powered by Blogger. Isn't yours?