如有需要可以转载，但转载请注明出处，并保留这一块信息，谢谢合作！

部分内容参考互联网,如有异议,请跟我联系!

作者:刀剑笑(Blog:http://blog.csdn.net/jyz3051)

Email:jyz3051 at yahoo dot com dot cn('at'请替换成'@'，'dot'请替换成'.' )

===============================================================================

关键词：中文分词，中文分词算法，基于字符串匹配的分词，基于理解的分词，基于统计的分词

到目前为止，中文分词包括三种方法：1）基于字符串匹配的分词；2）基于理解的分词；3）基于统计的分词。到目前为止，还无法证明哪一种方法更准确，每种方法都有自己的利弊，有强项也有致命弱点，简单的对比见下表所示：

各种分词方法的优劣对比

（1）歧义识别

歧义识别指一个字符串有多种分词方法，计算机难以给出到底哪一种分词算法才是正确的分词系列。如"表面的"可以分为"表面/的"或"表/面的"。计算机无法判断哪一种才是准确的分词系列。

基于字符串的分词算法：仅仅是跟一个电子词典进行比较，故不能进行歧义识别；

基于理解的分词算法：指通过理解字符串的含义，故有很强的歧义识别能力；

基于统计的分词算法：根据字符连续出现次数的多少，得到分词系列，故常常能够给出正确的分词系列选择，但是也有可能判断错误的情况。

（2）新词识别

新词识别也称作未登录词识别，指正确识别词典中没有出现的词语。姓名、机构名、地址、称谓等千变万化，词典中常常不能完全收录这些词语；另外，网络中出现的流行用语也是一种未登录词的常见来源，如"打酱油"为最近出现在网络中，并迅速流行，从而成为一个新词。大量的研究证明新词识别是中文分词准确性的一个重要影响因素。

基于字符串的分词算法：无法正确识别未登录词，因为这种算法仅仅与词典中存在的词语进行比较；

基于理解的分词算法：理解字符串的含义，从而有很强的新词识别能力；

基于统计的分词算法：这种算法对第二种未登录词有很强的识别能力，因为出现次数多，才会当作一个新词；对于第二类未登录词，这类词语有一定的规律，如姓名："姓"+ 名字，如李胜利；机构：前缀+称谓，如希望集团；故需要结合一定的规则进行识别，仅仅统计方法难以正确识别。

（3）需要词典

基于字符串的分词算法：基本思路就是与电子词典进行比较，故电子词典是必须的。并且词典越大，分词的正确率越高，因为词典越大，未登录词越少，从而可以大大减少未登录词识别的错误；

基于理解的分词算法：理解字符串的含义，故不需要一个电子词典；

基于统计的分词算法：仅仅根据统计得到最终的结果，故电子词典不是必须的。

（4）需要语料库

基于字符串的分词算法：分词过程仅仅与一个已经存在的电子词典进行比较，故不需要语料库；

基于理解的分词算法：理解字符串的含义，故不需要电子词典；

基于统计的分词算法：需要语料库进行统计训练，故语料库是必须的；且好的语料库是分词准确性的保证。

（5）需要规则库

基于字符串的分词算法：分词过程仅仅与一个已经存在的电子词典进行比较，不需要规则库来进行分词；

基于理解的分词算法：规则是计算机进行理解的基础，故准确、完备的规则库是这种分词算法的前提；

基于统计的分词算法：根据语料库统计训练，故规则库不是必须的。

（6）算法复杂性

基于字符串的分词算法：仅仅进行字符串的比较操作，故算法简单；

基于理解的分词算法：需要充分处理各种规则，故算法非常复杂；事实上到目前为止，还没有成熟的这类算法；

基于统计的分词算法：需要语料库进行训练，虽然算法也比较复杂，但是已经比较常见，故这种分词的复杂性比第一种大，比第二种容易。现在的实用分词系统都采用这种算法。

（7）技术成熟度

基于字符串的分词算法：是最早出现也是最成熟的算法；

基于理解的分词算法：是最不成熟的一类算法，到目前为止还没有成熟的算法；

基于统计的分词算法：已经有多种成熟的这类算法，基本上能够满足实际的应用。

故技术成熟度：基于匹配的分词算法〉基于理解的分词算法〉基于统计的分词算法。

（8）实施复杂性

同上面的道理，实施复杂性：基于理解的分词算法〉基于统计的分词算法〉基于匹配的分词算法。

（9）分词准确性

到目前为止还没有一个准确的结论，不过从理论上说，基于理解的分词算法有最高的分词准确性，理论上有100%的准确性；而基于匹配的分词算法和基于统计的分词算法是一种"浅理解"的分词方法，不涉及真正的含义理解，故可能会出现错误，难以达到100%的准确性。

（10）分词速度

基于匹配的分词算法：算法简单，操作容易，故分词速度快，所以这种算法常常作为另外两种算法的预处理，进行字符串的粗分；

基于理解的分词算法：这种算法常常需要操作一个巨大的规则库，故速度最慢；

基于统计的分词算法：这种分词算法仅仅是与一个统计结果进行比较，故速度一般。

故一般的分词速度从快到慢依次为：基于匹配的分词算法〉基于统计的分词算法〉基于理解的分词算法。

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

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

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

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

１.首先，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);//输出最终分词结果

    ......

}

２.在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

  .......

}

３.主要的分词处理是在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);

......

}

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

参考文章:

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

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

来源：http://blog.csdn.net/sinboy/archive/2006/03/12/622596.aspx

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

〇、总体流程

考虑输入的一句话，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<sp.m_nVertex;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<m_nValueKind;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<m_nValueKind;i++)m_pWeight[nCurNode-1][i]=INFINITE_VALUE;//初始化当前的m_pWeight[nCurNode-1]
 while(i<m_nValueKind&&queWork.Pop(&nPreNode,&nIndex,&eWeight)!=-1)//从queWork中顺序取出每个pEdgeList的row,nIndex的取值从0到m_nValueKind-1,eWeight=pEdgeList->value
 {
  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_Seg.m_nSegmentCount;nIndex++)//m_Seg.m_nSegmentCount是第四步中的分词结果个数
{
 m_POSTagger.POSTagging(m_Seg.m_pWordSeg[nIndex],m_dictCore,m_dictCore);
}

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

• 下载 SharpICTCLAS 1.0

一、SharpICTCLAS 1.0 版相对于测试版的改进

1、修改了原子分词代码，使得对于全角字母有较好的识别

2、修改了部分词性标注部分的代码

因为词性标注部分的代码存在问题（应当是从ICTCLAS就存在的问题），主要表现在如果某个汉字没有词性，则在词性标注时会出现异常。例如：“这些是永远也没有现成的答桉的”其中“答案”写错了，当对这个有错别字的句子分词时，“桉”字是没有词性的，程序在此时将出现错误。

目前的解决办法是对于这些没有词性的词在最终标注时标注为“字符串”。

2、修改了地名识别的一些问题

这个问题出现在Span类的PlaceRecognize方法中，nStart与nEnd在某些时候会计算错误。在测试版SharpICTCLAS中，句子“明定陵是明十三陵中第十座陵墓”在分词时会因为这个问题导致异常。

3、修改了基于CCID的字符串比较代码

原有代码没有很好考虑对全角、半角混合字符串的比较问题，现在修正过来了。

4、修改了向词库添加词汇的代码

原有代码存在错误，现在改正了过来。

二、仍然有待改进的地方

现在的程序仍然有很多地方有待改进，例如原子分词部分的代码对电子邮件、URL等识别还不是很好，日后可利用正则表达式加以改进；除此之外，对于词性标注以及人名地名识别部分代码 ，我除了修改了部分问题代码外，没有做任何改进和调整，这使得整个代码显得凌乱，有待做一次全面重构。

三、SharpICTCLAS使用时的一些示例代码

为了能够更好的使用SharpICTCLAS，现提供一些示例代码，主要完成的工作包括：1）向词库中添加新词汇；2）对文件的预处理，实现繁体向简体的转换、全角字符向半角字符的转换、利用正则表达式过滤多余HTML标记以及断句等。具体可以访问我的文章《SharpICTCLAS分词系统简介(9)词库扩充》。

目前经过调整后的SharpICTCLAS运行效果还算不错。在对博客园一万五千篇文章进行分词测试过程中，向词库中添加了一千三百多个词汇然后进行分词，效果还不错， 分词异常一共发生了15次，其中有9处是因为存在大量日文字符，另外6处是一句话中单词过多，超出了软件限制（200词）。分词效率也比较令人满意（尽管总体还是比较慢），15000篇文章总用时2.5小时，但这不只是分词的时间，还包括了繁体转简体、利用正则表达式去掉HTML符号，统计词频（这需要进行重复词的判别，我使用了AVL树 ，共统计得到16万词汇）、将分词结果写入SQL Server 2005数据库。如果不考虑这些因素的话，感觉应当和C＋＋程序效率差不多，当然这是没有经过严格测试的结论。

如果大家在使用时发现什么新问题，还请及时告知，我会继续修正这些问题。

• ICTCLAS简介：

计算所汉语词法分析系统ICTCLAS（Institute of Computing Technology, Chinese Lexical Analysis System），功能有：中文分词；词性标注；未登录词识别。分词正确率高达97.58%(973专家评测结果)，未登录词识别召回率均高于90%，其中中国人名的识别召回率接近98%;处理速度为31.5Kbytes/s。

著作权： Copyright(c)2002-2005中科院计算所 职务著作权人：张华平

遵循协议：自然语言处理开放资源许可证1.0

Email: zhanghp@software.ict.ac.cn

Homepage: http://www.i3s.ac.cn

• SharpICTCLAS：

.net平台下的ICTCLAS，是由河北理工大学经管学院吕震宇根据Free版ICTCLAS改编而成，并对原有代码做了部分重写与调整。

Email: zhenyulu@163.com

Blog: http://www.cnblogs.com/zhenyulu

来源：http://www.cnblogs.com/zhenyulu/category/85598.html

如果对SharpICTCLAS目前词库不满意的化，可以考虑扩充现有词库。扩充方法非常简单，代码如下：

Copy Code

词库扩充

static void Main(string[] args)
{
   string DictPath = Path.Combine(Environment.CurrentDirectory, "Data") +
                     Path.DirectorySeparatorChar;
   Console.WriteLine("正在读入字典，请稍候...");

   WordDictionary dict = new WordDictionary();
   dict.Load(DictPath + "coreDict.dct");

   Console.WriteLine("\r\n向字典库插入“设计模式”一词...");
   dict.AddItem("设计模式", Utility.GetPOSValue("n"), 10);

   Console.WriteLine("\r\n修改完成，将字典写入磁盘文件coreDictNew.dct，请稍候...");
   dict.Save(DictPath + "coreDictNew.dct");

   Console.Write("按下回车键退出......");
   Console.ReadLine();
}

通过AddItem方法可以轻松实现添加新词汇，添加时除了要指明词外，还需指明词性、词频。

2、其它工具

SharpICTCLAS示例代码中还提供了一些用于对文件进行预处理的工具类PreProcessUtility，里面提供了将GB2312中繁体汉字转换为简体字的代码，以及将全角字母转换为半角字母的方法，除此之外，还提供了对HTML文件进行预处理，去除HTML标记的方法，用户可酌情使用。

• 小结

有关SharpICTCLAS的系列文章到此为止就全部结束。

来源：http://www.cnblogs.com/zhenyulu/category/85598.html

1、SharpICTCLAS中的事件

分词过程比较复杂，所以很可能有人希望能够追踪分词的过程，设置代码断点比较麻烦，因此SharpICTCLAS中提供了事件机制，可以在分词的不同阶段触发相关事件，使用者可以订阅这些事件并输出中间结果供查错使用。

事件的阶段被定义在SegmentStage枚举当中，代码如下：

Copy Code

SegmentStage程序

public enum SegmentStage
{
   BeginSegment,              //开始分词
   AtomSegment,               //原子切分
   GenSegGraph,               //生成SegGraph
   GenBiSegGraph,             //生成BiSegGraph
   NShortPath,                //N最短路径计算
   BeforeOptimize,            //对N最短路径进一步整理得到的结果
   OptimumSegment,            //初始OptimumSegmentGraph
   PersonAndPlaceRecognition, //人名与地名识别后的OptimumSegmentGraph
   BiOptimumSegment,          //生成BiOptimumSegmentGraph
   FinishSegment              //完成分词，输出结果
}

分别对应分词过程中的10个阶段。

SharpICTCLAS中还定义了一个EventArgs，里面包含了两个元素，分别用来记录该事件元素所处的分词阶段以及该阶段的相关中间结果信息。中间结果信息使用的是string类型数据，日后可以考虑采用更复杂的表示形式输出中间结果。该事件元素定义如下：

Copy Code

SegmentEventArgs的定义

public class SegmentEventArgs : EventArgs
{
   public SegmentStage Stage;
   public string Info = "";

   ......
}

剩下的工作就是定义委派并发布事件了。由于分词过程主要集中在两个类中：WordSegment类与Segment类，而用户通常只需要与WordSegment类打交道，因此WordSegment类中转发了Segment类产生的事件。

委派的定义以及事件的定义如下（部分）：

Copy Code

程序

//---定义委派
public delegate void SegmentEventHandler(object sender, SegmentEventArgs e);

//---定义事件
public event SegmentEventHandler OnSegmentEvent;

//---发布事件的方法
private void SendEvents(SegmentEventArgs e)
{
   if (OnSegmentEvent != null)
      OnSegmentEvent(this, e);
}

//---开始分词
private void OnBeginSegment(string sentence)
{
   SendEvents(new SegmentEventArgs(SegmentStage.BeginSegment, sentence));
}

......

//---结束分词
private void OnFinishSegment(List<WordResult[]> m_pWordSeg)
{
   StringBuilder sb = new StringBuilder();
   for (int k = 0; k < m_pWordSeg.Count; k++)
   {
      for (int j = 0; j < m_pWordSeg[k].Length; j++)
         sb.Append(string.Format("{0} /{1} ", m_pWordSeg[k][j].sWord, 
                   Utility.GetPOSString(m_pWordSeg[k][j].nPOS)));
      sb.Append("\r\n");
   }

   SendEvents(new SegmentEventArgs(SegmentStage.FinishSegment, sb.ToString()));
}

有了这些事件，用户可以根据需要订阅不同的事件来获取分词的中间结果，极大方便了程序调试工作。

2、SharpICTCLAS的使用

下面是一个使用SharpICTCLAS的示例代码：

Copy Code

WordSegmentSample.cs

using System;
using System.Collections.Generic;
using System.Text;
using SharpICTCLAS;

public class WordSegmentSample
{
   private int nKind = 1;  //在NShortPath方法中用来决定初步切分时分成几种结果
   private WordSegment wordSegment;

   //=======================================================
   // 构造函数，在没有指明nKind的情况下，nKind 取 1
   //=======================================================
   public WordSegmentSample(string dictPath) : this(dictPath, 1) { }

   //=======================================================
   // 构造函数
   //=======================================================
   public WordSegmentSample(string dictPath, int nKind)
   {
      this.nKind = nKind;
      this.wordSegment = new WordSegment();

      //---------- 订阅分词过程中的事件 ----------
      wordSegment.OnSegmentEvent += new SegmentEventHandler(this.OnSegmentEventHandler);
      wordSegment.InitWordSegment(dictPath);
   }

   //=======================================================
   // 开始分词
   //=======================================================
   public List<WordResult[]> Segment(string sentence)
   {
      return wordSegment.Segment(sentence, nKind);
   }
   
   //=======================================================
   // 输出分词过程中每一步的中间结果
   //=======================================================
   private void OnSegmentEventHandler(object sender, SegmentEventArgs e)
   {
      switch (e.Stage)
      {
         case SegmentStage.BeginSegment:
            Console.WriteLine("\r\n==== 原始句子：\r\n");
            Console.WriteLine(e.Info + "\r\n");
            break;
         case SegmentStage.AtomSegment:
            Console.WriteLine("\r\n==== 原子切分：\r\n");
            Console.WriteLine(e.Info);
            break;
         case SegmentStage.GenSegGraph:
            Console.WriteLine("\r\n==== 生成 segGraph：\r\n");
            Console.WriteLine(e.Info);
            break;
         case SegmentStage.GenBiSegGraph:
            Console.WriteLine("\r\n==== 生成 biSegGraph：\r\n");
            Console.WriteLine(e.Info);
            break;
         case SegmentStage.NShortPath:
            Console.WriteLine("\r\n==== NShortPath 初步切分的到的 N 个结果：\r\n");
            Console.WriteLine(e.Info);
            break;
         case SegmentStage.BeforeOptimize:
            Console.WriteLine("\r\n==== 经过数字、日期合并等策略处理后的 N 个结果：\r\n");
            Console.WriteLine(e.Info);
            break;
         case SegmentStage.OptimumSegment:
            Console.WriteLine("\r\n==== 将 N 个结果归并入OptimumSegment：\r\n");
            Console.WriteLine(e.Info);
            break;
         case SegmentStage.PersonAndPlaceRecognition:
            Console.WriteLine("\r\n==== 加入对姓名、翻译人名以及地名的识别：\r\n");
            Console.WriteLine(e.Info);
            break;
         case SegmentStage.BiOptimumSegment:
            Console.WriteLine("\r\n==== 对加入对姓名、地名的OptimumSegment生成BiOptimumSegment：\r\n");
            Console.WriteLine(e.Info);
            break;
         case SegmentStage.FinishSegment:
            Console.WriteLine("\r\n==== 最终识别结果：\r\n");
            Console.WriteLine(e.Info);
            break;
      }
   }
}

从中我们可以看出，首先添加对SharpICTCLAS命名空间的引用，然后创建WordSegment类的一个实例。如果需要拦截分词过程中的事件的话，那么可以订阅WordSegment类的OnSegmentEvent事件，上面的代码用OnSegmentEventHandler方法订阅了事件，并且输出了所有分词Stage的中间结果。

WordSegmentSample类中的 nKind 属性是在NShortPath方法中用来决定初步切分时分成几种结果。如果不特殊指明，nKind取1，用户也可以自己定义一个1～10之间的整数（超过10，系统自动取10），数越大分词准确率越高（可以参考张华平的论文），但系统执行效率会下降。

WordSegment类的InitWordSegment方法主要用来初始化各个词典，用户在这里需要提供词典所在的目录信息，系统自动到该目录下搜索所有词典。

有了WordSegmentSample类，主程序如下：

Copy Code

程序

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using SharpICTCLAS;

class Program
{
   static void Main(string[] args)
   {
      List<WordResult[]> result;

      string DictPath = Path.Combine(Environment.CurrentDirectory, "Data") + 
         Path.DirectorySeparatorChar;
         
      Console.WriteLine("正在初始化字典库，请稍候...");
      WordSegmentSample sample = new WordSegmentSample(DictPath, 5);

      result = sample.Segment(@"王晓平在1月份滦南大会上说的确实在理");

      //---------- 输出结果 ----------
      //Console.WriteLine("\r\n==== 最终识别结果：\r\n");
      //for (int i = 0; i < result.Count; i++)
      //{
      //   for (int j = 0; j < result[i].Length; j++)
      //      Console.Write("{0} /{1} ", result[i][j].sWord, Utility.GetPOSString(result[i][j].nPOS));
      //   Console.WriteLine();
      //}

      Console.Write("按下回车键退出......");
      Console.ReadLine();
   }
}

内容比较简单，此处就不再多说。由于我们在WordSegmentSample中订阅了所有阶段的事件，因此程序会输出整个过程各个阶段的中间结果，也包括最终分词结果，因此上面代码中我将输出结果部分的代码注释起来了。如果没有订阅任何事件的话，可以使用注释起来的这段代码输出分词最终结果。

该程序的执行结果如下：

Copy Code

WordSegmentSample程序执行结果

正在初始化字典库，请稍候...

//==== 原始句子：

王晓平在1月份滦南大会上说的确实在理


//==== 原子切分：

始##始, 王, 晓, 平, 在, 1, 月, 份, 滦, 南, 大, 会, 上, 说, 的, 确, 实, 在, 理, 末##末, 


//==== 生成 segGraph：

row:  0,  col:  1,  eWeight: 329805.00,   nPOS:      1,   sWord:始##始
row:  1,  col:  2,  eWeight:    218.00,   nPOS:      0,   sWord:王
row:  2,  col:  3,  eWeight:      9.00,   nPOS:      0,   sWord:晓
row:  3,  col:  4,  eWeight:    271.00,   nPOS:      0,   sWord:平
row:  4,  col:  5,  eWeight:  78484.00,   nPOS:      0,   sWord:在
row:  5,  col:  6,  eWeight:      0.00,   nPOS: -27904,   sWord:未##数
row:  6,  col:  7,  eWeight:   1900.00,   nPOS:      0,   sWord:月
row:  6,  col:  8,  eWeight:     11.00,   nPOS:  28160,   sWord:月份
row:  7,  col:  8,  eWeight:   1234.00,   nPOS:      0,   sWord:份
row:  8,  col:  9,  eWeight:      1.00,   nPOS:  27136,   sWord:滦
row:  9,  col: 10,  eWeight:    813.00,   nPOS:      0,   sWord:南
row: 10,  col: 11,  eWeight:  14536.00,   nPOS:      0,   sWord:大
row: 10,  col: 12,  eWeight:   1333.00,   nPOS:  28160,   sWord:大会
row: 11,  col: 12,  eWeight:   6136.00,   nPOS:      0,   sWord:会
row: 11,  col: 13,  eWeight:    469.00,   nPOS:      0,   sWord:会上
row: 12,  col: 13,  eWeight:  23706.00,   nPOS:      0,   sWord:上
row: 13,  col: 14,  eWeight:  17649.00,   nPOS:      0,   sWord:说
row: 14,  col: 15,  eWeight: 358156.00,   nPOS:      0,   sWord:的
row: 14,  col: 16,  eWeight:    210.00,   nPOS:  25600,   sWord:的确
row: 15,  col: 16,  eWeight:    181.00,   nPOS:      0,   sWord:确
row: 15,  col: 17,  eWeight:    361.00,   nPOS:      0,   sWord:确实
row: 16,  col: 17,  eWeight:    357.00,   nPOS:      0,   sWord:实
row: 16,  col: 18,  eWeight:    295.00,   nPOS:      0,   sWord:实在
row: 17,  col: 18,  eWeight:  78484.00,   nPOS:      0,   sWord:在
row: 17,  col: 19,  eWeight:      3.00,   nPOS:  24832,   sWord:在理
row: 18,  col: 19,  eWeight:    129.00,   nPOS:      0,   sWord:理
row: 19,  col: 20,  eWeight:2079997.00,   nPOS:      4,   sWord:末##末


//==== 生成 biSegGraph：

row:  0,  col:  1,  eWeight:      4.18,   nPOS:      1,   sWord:始##始@王
row:  1,  col:  2,  eWeight:     11.46,   nPOS:      0,   sWord:王@晓
row:  2,  col:  3,  eWeight:     13.93,   nPOS:      0,   sWord:晓@平
row:  3,  col:  4,  eWeight:     11.25,   nPOS:      0,   sWord:平@在
row:  4,  col:  5,  eWeight:      3.74,   nPOS:      0,   sWord:在@未##数
row:  5,  col:  6,  eWeight: -27898.79,   nPOS: -27904,   sWord:未##数@月
row:  5,  col:  7,  eWeight: -27898.75,   nPOS: -27904,   sWord:未##数@月份
row:  6,  col:  8,  eWeight:      9.33,   nPOS:      0,   sWord:月@份
row:  7,  col:  9,  eWeight:     13.83,   nPOS:  28160,   sWord:月份@滦
row:  8,  col:  9,  eWeight:      9.76,   nPOS:      0,   sWord:份@滦
row:  9,  col: 10,  eWeight:     14.46,   nPOS:  27136,   sWord:滦@南
row: 10,  col: 11,  eWeight:      5.19,   nPOS:      0,   sWord:南@大
row: 10,  col: 12,  eWeight:     10.17,   nPOS:      0,   sWord:南@大会
row: 11,  col: 13,  eWeight:      7.30,   nPOS:      0,   sWord:大@会
row: 11,  col: 14,  eWeight:      7.30,   nPOS:      0,   sWord:大@会上
row: 12,  col: 15,  eWeight:      2.11,   nPOS:  28160,   sWord:大会@上
row: 13,  col: 15,  eWeight:      8.16,   nPOS:      0,   sWord:会@上
row: 14,  col: 16,  eWeight:      3.42,   nPOS:      0,   sWord:会上@说
row: 15,  col: 16,  eWeight:      4.07,   nPOS:      0,   sWord:上@说
row: 16,  col: 17,  eWeight:      4.05,   nPOS:      0,   sWord:说@的
row: 16,  col: 18,  eWeight:      7.11,   nPOS:      0,   sWord:说@的确
row: 17,  col: 19,  eWeight:      4.10,   nPOS:      0,   sWord:的@确
row: 17,  col: 20,  eWeight:      4.10,   nPOS:      0,   sWord:的@确实
row: 18,  col: 21,  eWeight:     11.49,   nPOS:  25600,   sWord:的确@实
row: 19,  col: 21,  eWeight:     11.63,   nPOS:      0,   sWord:确@实
row: 18,  col: 22,  eWeight:     11.49,   nPOS:  25600,   sWord:的确@实在
row: 19,  col: 22,  eWeight:     11.63,   nPOS:      0,   sWord:确@实在
row: 20,  col: 23,  eWeight:      3.92,   nPOS:      0,   sWord:确实@在
row: 21,  col: 23,  eWeight:     10.98,   nPOS:      0,   sWord:实@在
row: 20,  col: 24,  eWeight:     10.97,   nPOS:      0,   sWord:确实@在理
row: 21,  col: 24,  eWeight:     10.98,   nPOS:      0,   sWord:实@在理
row: 22,  col: 25,  eWeight:     11.17,   nPOS:      0,   sWord:实在@理
row: 23,  col: 25,  eWeight:      5.62,   nPOS:      0,   sWord:在@理
row: 24,  col: 26,  eWeight:     14.30,   nPOS:  24832,   sWord:在理@末##末
row: 25,  col: 26,  eWeight:     11.95,   nPOS:      0,   sWord:理@末##末


//==== NShortPath 初步切分的到的 N 个结果：

始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末, 
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末, 
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末, 
始##始, 王, 晓, 平, 在, 1, 月, 份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 


//==== 经过数字、日期合并等策略处理后的 N 个结果：

始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末, 
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末, 
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末, 
始##始, 王, 晓, 平, 在, 1月, 份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 


//==== 加入对姓名、翻译人名以及地名的识别：

row:  0,  col:  1,  eWeight: 329805.00,   nPOS:      1,   sWord:始##始
row:  1,  col:  2,  eWeight:    218.00,   nPOS:      0,   sWord:王
row:  1,  col:  4,  eWeight:     10.86,   nPOS: -28274,   sWord:未##人
row:  2,  col:  3,  eWeight:      9.00,   nPOS:      0,   sWord:晓
row:  2,  col:  4,  eWeight:     13.27,   nPOS: -28274,   sWord:未##人
row:  3,  col:  4,  eWeight:    271.00,   nPOS:      0,   sWord:平
row:  4,  col:  5,  eWeight:  78484.00,   nPOS:      0,   sWord:在
row:  5,  col:  7,  eWeight:      0.00,   nPOS: -29696,   sWord:未##时
row:  5,  col:  8,  eWeight:      0.00,   nPOS: -29696,   sWord:未##时
row:  7,  col:  8,  eWeight:   1234.00,   nPOS:      0,   sWord:份
row:  8,  col:  9,  eWeight:      1.00,   nPOS:  27136,   sWord:滦
row:  8,  col: 10,  eWeight:     20.37,   nPOS: -28275,   sWord:未##地
row:  9,  col: 10,  eWeight:    813.00,   nPOS:      0,   sWord:南
row: 10,  col: 11,  eWeight:  14536.00,   nPOS:      0,   sWord:大
row: 10,  col: 12,  eWeight:   1333.00,   nPOS:  28160,   sWord:大会
row: 11,  col: 13,  eWeight:    469.00,   nPOS:      0,   sWord:会上
row: 12,  col: 13,  eWeight:  23706.00,   nPOS: -27904,   sWord:未##数
row: 13,  col: 14,  eWeight:  17649.00,   nPOS:      0,   sWord:说
row: 14,  col: 15,  eWeight: 358156.00,   nPOS:      0,   sWord:的
row: 15,  col: 17,  eWeight:    361.00,   nPOS:      0,   sWord:确实
row: 17,  col: 18,  eWeight:  78484.00,   nPOS:      0,   sWord:在
row: 17,  col: 19,  eWeight:      3.00,   nPOS:  24832,   sWord:在理
row: 18,  col: 19,  eWeight:    129.00,   nPOS:      0,   sWord:理
row: 19,  col: 20,  eWeight:2079997.00,   nPOS:      4,   sWord:末##末


//==== 生成 biSegGraph：

row:  0,  col:  1,  eWeight:      4.18,   nPOS:      1,   sWord:始##始@王
row:  0,  col:  2,  eWeight:      2.88,   nPOS:      1,   sWord:始##始@未##人
row:  1,  col:  3,  eWeight:     11.46,   nPOS:      0,   sWord:王@晓
row:  1,  col:  4,  eWeight:      3.88,   nPOS:      0,   sWord:王@未##人
row:  3,  col:  5,  eWeight:     13.93,   nPOS:      0,   sWord:晓@平
row:  2,  col:  6,  eWeight: -28270.43,   nPOS: -28274,   sWord:未##人@在
row:  4,  col:  6,  eWeight: -28270.43,   nPOS: -28274,   sWord:未##人@在
row:  5,  col:  6,  eWeight:     11.25,   nPOS:      0,   sWord:平@在
row:  6,  col:  7,  eWeight:      4.01,   nPOS:      0,   sWord:在@未##时
row:  6,  col:  8,  eWeight:      4.01,   nPOS:      0,   sWord:在@未##时
row:  7,  col:  9,  eWeight: -29690.16,   nPOS: -29696,   sWord:未##时@份
row:  8,  col: 10,  eWeight: -29690.16,   nPOS: -29696,   sWord:未##时@滦
row:  9,  col: 10,  eWeight:      9.76,   nPOS:      0,   sWord:份@滦
row:  8,  col: 11,  eWeight: -29690.17,   nPOS: -29696,   sWord:未##时@未##地
row:  9,  col: 11,  eWeight:      9.76,   nPOS:      0,   sWord:份@未##地
row: 10,  col: 12,  eWeight:     14.46,   nPOS:  27136,   sWord:滦@南
row: 11,  col: 13,  eWeight: -28267.95,   nPOS: -28275,   sWord:未##地@大
row: 12,  col: 13,  eWeight:      5.19,   nPOS:      0,   sWord:南@大
row: 11,  col: 14,  eWeight: -28266.85,   nPOS: -28275,   sWord:未##地@大会
row: 12,  col: 14,  eWeight:     10.17,   nPOS:      0,   sWord:南@大会
row: 13,  col: 15,  eWeight:      7.30,   nPOS:      0,   sWord:大@会上
row: 14,  col: 16,  eWeight:      4.81,   nPOS:  28160,   sWord:大会@未##数
row: 15,  col: 17,  eWeight:      3.42,   nPOS:      0,   sWord:会上@说
row: 16,  col: 17,  eWeight: -27898.75,   nPOS: -27904,   sWord:未##数@说
row: 17,  col: 18,  eWeight:      4.05,   nPOS:      0,   sWord:说@的
row: 18,  col: 19,  eWeight:      4.10,   nPOS:      0,   sWord:的@确实
row: 19,  col: 20,  eWeight:      3.92,   nPOS:      0,   sWord:确实@在
row: 19,  col: 21,  eWeight:     10.97,   nPOS:      0,   sWord:确实@在理
row: 20,  col: 22,  eWeight:      5.62,   nPOS:      0,   sWord:在@理
row: 21,  col: 23,  eWeight:     14.30,   nPOS:  24832,   sWord:在理@末##末
row: 22,  col: 23,  eWeight:     11.95,   nPOS:      0,   sWord:理@末##末


//==== 最终识别结果：

王晓平 /nr 在 /p  1月份 /t  滦南 /ns 大会 /n  上 /v  说 /v  的 /uj 确实 /ad 在 /p  理 /n

非常高兴在这最后一篇文章写完之时得到了张华平老师的授权。我会尽可能快的将SharpICTCLAS源文件放上来供大家测试使用的。

来源：http://www.cnblogs.com/zhenyulu/category/85598.html

1、OptimumSegment的运算过程

经过NShortPath处理后的多个结果首先会经过日期合并策略的处理，这就是前文说的GenerateWord方法完成的功能。在GenerateWord方法中可以看到如下命令：

 m_graphOptimum.SetElement(pCur.row, pCur.col, ......);

它的功能就是将所有得到的多个分词方案合并归入一个 m_graphOptimum 属性，如下面的NShortPath运算结果，经过归并后，在 m_graphOptimum 属性中将包含所有红色词。

Copy Code

经过NShortPath处理后的初步分词结果

//==== 原始句子：

王晓平在1月份滦南大会上说的确实在理

//==== NShortPath 初步切分的到的 N 个结果：

始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末, 
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末, 
始##始, 王, 晓, 平, 在, 1, 月份, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末, 
始##始, 王, 晓, 平, 在, 1, 月, 份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 


//==== 经过数字、日期合并等策略处理后的 N 个结果：

始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大会, 上, 说, 的, 确实, 在, 理, 末##末, 
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在理, 末##末, 
始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大会, 上, 说, 的, 确实, 在理, 末##末, 
始##始, 王, 晓, 平, 在, 1月, 份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 

紧接着对归并后的 m_graphOptimum 进行人名与地名的识别，找出所有可能的人名、地名方案，经过人名、地名识别后的 m_graphOptimum 如下：

Copy Code

加入人名、地名识别

//==== 加入对姓名、翻译人名以及地名的识别：

row:  0,  col:  1,  eWeight: 329805.00,   nPOS:      1,   sWord:始##始
row:  1,  col:  2,  eWeight:    218.00,   nPOS:      0,   sWord:王
row:  1,  col:  4,  eWeight:     10.86,   nPOS: -28274,   sWord:未##人
row:  2,  col:  3,  eWeight:      9.00,   nPOS:      0,   sWord:晓
row:  2,  col:  4,  eWeight:     13.27,   nPOS: -28274,   sWord:未##人
row:  3,  col:  4,  eWeight:    271.00,   nPOS:      0,   sWord:平
row:  4,  col:  5,  eWeight:  78484.00,   nPOS:      0,   sWord:在
row:  5,  col:  7,  eWeight:      0.00,   nPOS: -29696,   sWord:未##时
row:  5,  col:  8,  eWeight:      0.00,   nPOS: -29696,   sWord:未##时
row:  7,  col:  8,  eWeight:   1234.00,   nPOS:      0,   sWord:份
row:  8,  col:  9,  eWeight:      1.00,   nPOS:  27136,   sWord:滦
row:  8,  col: 10,  eWeight:     20.37,   nPOS: -28275,   sWord:未##地
row:  9,  col: 10,  eWeight:    813.00,   nPOS:      0,   sWord:南
row: 10,  col: 11,  eWeight:  14536.00,   nPOS:      0,   sWord:大
row: 10,  col: 12,  eWeight:   1333.00,   nPOS:  28160,   sWord:大会
row: 11,  col: 13,  eWeight:    469.00,   nPOS:      0,   sWord:会上
row: 12,  col: 13,  eWeight:  23706.00,   nPOS: -27904,   sWord:未##数
row: 13,  col: 14,  eWeight:  17649.00,   nPOS:      0,   sWord:说
row: 14,  col: 15,  eWeight: 358156.00,   nPOS:      0,   sWord:的
row: 15,  col: 17,  eWeight:    361.00,   nPOS:      0,   sWord:确实
row: 17,  col: 18,  eWeight:  78484.00,   nPOS:      0,   sWord:在
row: 17,  col: 19,  eWeight:      3.00,   nPOS:  24832,   sWord:在理
row: 18,  col: 19,  eWeight:    129.00,   nPOS:      0,   sWord:理
row: 19,  col: 20,  eWeight:2079997.00,   nPOS:      4,   sWord:末##末

到此为止， m_graphOptimum 包含了所有最终分词结果中可能包含的元素（人名、地名以及NShortPath筛选后所有可能组词方案），Segment类对这个 m_graphOptimum 再次使用NShortPath，并计算出最优结果作为最终的分词方案。

整个过程可从WordSegment类的Segment方法看出，SharpICTCLAS中该方法定义如下（经过简化）：

Copy Code

分词主程序

public List<WordResult[]> Segment(string sentence, int nKind)
{
   m_pNewSentence = Predefine.SENTENCE_BEGIN + sentence + Predefine.SENTENCE_END;
   //---初步分词
   int nResultCount = m_Seg.BiSegment(m_pNewSentence, m_dSmoothingPara, nKind);

   //---人名、地名识别
   for (int i = 0; i < nResultCount; i++)
   {
      m_uPerson.Recognition(m_Seg.m_pWordSeg[i], m_Seg.m_graphOptimum, ......);
      m_uTransPerson.Recognition(m_Seg.m_pWordSeg[i], m_Seg.m_graphOptimum, ......);
      m_uPlace.Recognition(m_Seg.m_pWordSeg[i], m_Seg.m_graphOptimum, ......);
   }

   //---最终优化
   m_Seg.BiOptimumSegment(1, m_dSmoothingPara);

   //---词性标注
   for (int i = 0; i < m_Seg.m_pWordSeg.Count; i++)
      m_POSTagger.POSTagging(m_Seg.m_pWordSeg[i], m_dictCore, m_dictCore);

   return m_Seg.m_pWordSeg;
}

2、人名与地名的识别

ICTCLAS中人名的识别采用的是模板匹配的方法，首先对初步分词得到的多的结果计算词性，然后根据词性串对人名信息进行匹配。整个运算过程如下：

首先定义了人名匹配模板：

Copy Code

人名识别模板

string[] sPatterns = { "BBCD", "BBC", "BBE", "BBZ", "BCD",
"BEE", "BE", "BG", "BXD", "BZ", "CDCD", "CD", "EE", "FB", 
"Y", "XD", "" };
/*------------------------------------
The person recognition patterns set
BBCD:姓+姓+名1+名2;
BBE: 姓+姓+单名;
BBZ: 姓+姓+双名成词;
BCD: 姓+名1+名2;
BE:  姓+单名;
BEE: 姓+单名+单名;韩磊磊
BG:  姓+后缀
BXD: 姓+姓双名首字成词+双名末字
BZ:  姓+双名成词;
B:   姓
CD:  名1+名2;
EE:  单名+单名;
FB:  前缀+姓
XD:  姓双名首字成词+双名末字
Y:   姓单名成词
------------------------------------*/

然后将初步分词得到的结果进行词性标注，清理掉其它不必要的信息后进行模板匹配得到人名：

Copy Code

人名识别过程

//==== 经过初步分词后的一个结果集

始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 

//==== 经过计算得到的m_nBestTag

始##始, 王, 晓, 平, 在, 1月份, 滦, 南, 大, 会上, 说, 的, 确实, 在, 理, 末##末, 
        B   C   D   M   A      A   A   A   A     A   A   A     A   A

//==== 经过模板匹配后识别出来的人名

王晓平

地名的识别与此类似，就不再多说。有关人名、地名识别的进一步内容可以参考：http://qxred.yculblog.com/post.1204714.html；《ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注》作者：风暴红QxRed 。

• 小结

经过NShortPath得到的多个初步分词结果被归并入 m_graphOptimum ，然后经过人名与地名识别过程将所有可能的人名、地名也放入其中，最后通过OptimumSegment方法最终得到分词结果。

来源：http://www.cnblogs.com/zhenyulu/category/85598.html

1）合并不同类中的部分代码

原有ICTCLAS中使用了SegGraph与Segment两个类完成分词过程，SegGraph类负责完成原子分词与segGraph的生成，而Segment类负责BiSegGraph的生成和NShortPath优化，而最终的人名、地名识别以及Optimum优化又分散在了Segment类与WordSegment类中。

SharpICTCLAS将原有SegGraph类与Segment合二为一，因为它们所作的工作仅仅是分词中的几个步骤而已。而WordSegment类中基本保留了原有内容，因为这个类更多的做一些外围工作。

2）改造了程序中用到的部分数据结构

原有ICTCLAS大量使用了数组与二维数组，由于数组的固有缺陷使得我们随处可以看到如此这般的数组定义：

m_pWordSeg = new PWORD_RESULT[MAX_SEGMENT_NUM];

由于不知道最终会分成几个词，所以定义数组时只能用最大的容量 MAX_SEGMENT_NUM 进行预设，所以一旦存在某些异常数据就会造成“溢出”错误。

而SharpICTCLAS中大量使用了 List<int[]> 的方式记录结果 ，范型的List首先可以确保结果集的数量可以动态调整而不用事先定义，另外每个结果的数组长度也可各不相同。

再有的改造就是在Segment类中使用了链表结构处理结果，这大大简化了原有ICTCLAS中的数组结构带来的种种问题。

3）大量使用了静态方法

由于某些过程的调用根本不需要建立对象，这些过程仅仅完成例行计算而已，因此将这些方法声明为静态方法更合适，何况静态方法的调用效率比实例方法高。因此本人在将ICTCLAS移植到C#平台上时，将尽可能的方法定义成静态方法。

下面我就说说SharpICTCLAS中Segment类的一些主要内容：

1、主体部分

比较典型的一个运算过程可以参考BiSegment方法，代码（经过简化）如下：

Copy Code

Segment类的BiSegment方法

public int BiSegment(string sSentence, double smoothPara, int nKind)
{
   WordResult[] tmpResult;
   WordLinkedArray linkedArray;
   m_pWordSeg = new List<WordResult[]>();
   m_graphOptimum = new RowFirstDynamicArray<ChainContent>();

   //---原子分词
   atomSegment = AtomSegment(sSentence);

   //---检索词库，加入所有可能分词方案并存入链表结构
   segGraph = GenerateWordNet(atomSegment, coreDict);

   //---检索所有可能的两两组合
   biGraphResult = BiGraphGenerate(segGraph, smoothPara, biDict, coreDict);

   //---N 最短路径计算出多个分词方案
   NShortPath.Calculate(biGraphResult, nKind);
   List<int[]> spResult = NShortPath.GetNPaths(Predefine.MAX_SEGMENT_NUM);

   //---对结果进行优化，例如合并日期等工作
   for (int i = 0; i < spResult.Count; i++)
   {
      linkedArray = BiPath2LinkedArray(spResult[i], segGraph, atomSegment);
      tmpResult = GenerateWord(spResult[i], linkedArray, m_graphOptimum);

      if (tmpResult != null)
         m_pWordSeg.Add(tmpResult);
   }

   return m_pWordSeg.Count;
}

从上面代码可以看出，已经将原有ICTCLAS的原子分词功能合并入Segment类了。

就拿“他在1月份大会上说的确实在理”这句话来说，上面几个步骤得到的中间结果如下：

Copy Code

程序

//==== 原始句子：

他在1月份大会上说的确实在理


//==== 原子切分：

始##始, 他, 在, 1, 月, 份, 大, 会, 上, 说, 的, 确, 实, 在, 理, 末##末,


//==== 生成 segGraph：

row:  0,  col:  1,  eWeight: 329805.00,   nPOS:      1,   sWord:始##始
row:  1,  col:  2,  eWeight:  19823.00,   nPOS:      0,   sWord:他
row:  2,  col:  3,  eWeight:  78484.00,   nPOS:      0,   sWord:在
row:  3,  col:  4,  eWeight:      0.00,   nPOS: -27904,   sWord:未##数
row:  4,  col:  5,  eWeight:   1900.00,   nPOS:      0,   sWord:月
row:  4,  col:  6,  eWeight:     11.00,   nPOS:  28160,   sWord:月份
row:  5,  col:  6,  eWeight:   1234.00,   nPOS:      0,   sWord:份
row:  6,  col:  7,  eWeight:  14536.00,   nPOS:      0,   sWord:大
row:  6,  col:  8,  eWeight:   1333.00,   nPOS:  28160,   sWord:大会
row:  7,  col:  8,  eWeight:   6136.00,   nPOS:      0,   sWord:会
row:  7,  col:  9,  eWeight:    469.00,   nPOS:      0,   sWord:会上
row:  8,  col:  9,  eWeight:  23706.00,   nPOS:      0,   sWord:上
row:  9,  col: 10,  eWeight:  17649.00,   nPOS:      0,   sWord:说
row: 10,  col: 11,  eWeight: 358156.00,   nPOS:      0,   sWord:的
row: 10,  col: 12,  eWeight:    210.00,   nPOS:  25600,   sWord:的确
row: 11,  col: 12,  eWeight:    181.00,   nPOS:      0,   sWord:确
row: 11,  col: 13,  eWeight:    361.00,   nPOS:      0,   sWord:确实
row: 12,  col: 13,  eWeight:    357.00,   nPOS:      0,   sWord:实
row: 12,  col: 14,  eWeight:    295.00,   nPOS:      0,   sWord:实在
row: 13,  col: 14,  eWeight:  78484.00,   nPOS:      0,   sWord:在
row: 13,  col: 15,  eWeight:      3.00,   nPOS:  24832,   sWord:在理
row: 14,  col: 15,  eWeight:    129.00,   nPOS:      0,   sWord:理
row: 15,  col: 16,  eWeight:2079997.00,   nPOS:      4,   sWord:末##末


//==== 生成 biSegGraph：

row:  0,  col:  1,  eWeight:      3.37,   nPOS:      1,   sWord:始##始@他
row:  1,  col:  2,  eWeight:      3.37,   nPOS:      0,   sWord:他@在
row:  2,  col:  3,  eWeight:      3.74,   nPOS:      0,   sWord:在@未##数
row:  3,  col:  4,  eWeight: -27898.79,   nPOS: -27904,   sWord:未##数@月
row:  3,  col:  5,  eWeight: -27898.75,   nPOS: -27904,   sWord:未##数@月份
row:  4,  col:  6,  eWeight:      9.33,   nPOS:      0,   sWord:月@份
row:  5,  col:  7,  eWeight:     13.83,   nPOS:  28160,   sWord:月份@大
row:  6,  col:  7,  eWeight:      9.76,   nPOS:      0,   sWord:份@大
row:  5,  col:  8,  eWeight:     13.83,   nPOS:  28160,   sWord:月份@大会
row:  6,  col:  8,  eWeight:      9.76,   nPOS:      0,   sWord:份@大会
row:  7,  col:  9,  eWeight:      7.30,   nPOS:      0,   sWord:大@会
row:  7,  col: 10,  eWeight:      7.30,   nPOS:      0,   sWord:大@会上
row:  8,  col: 11,  eWeight:      2.11,   nPOS:  28160,   sWord:大会@上
row:  9,  col: 11,  eWeight:      8.16,   nPOS:      0,   sWord:会@上
row: 10,  col: 12,  eWeight:      3.42,   nPOS:      0,   sWord:会上@说
row: 11,  col: 12,  eWeight:      4.07,   nPOS:      0,   sWord:上@说
row: 12,  col: 13,  eWeight:      4.05,   nPOS:      0,   sWord:说@的
row: 12,  col: 14,  eWeight:      7.11,   nPOS:      0,   sWord:说@的确
row: 13,  col: 15,  eWeight:      4.10,   nPOS:      0,   sWord:的@确
row: 13,  col: 16,  eWeight:      4.10,   nPOS:      0,   sWord:的@确实
row: 14,  col: 17,  eWeight:     11.49,   nPOS:  25600,   sWord:的确@实
row: 15,  col: 17,  eWeight:     11.63,   nPOS:      0,   sWord:确@实
row: 14,  col: 18,  eWeight:     11.49,   nPOS:  25600,   sWord:的确@实在
row: 15,  col: 18,  eWeight:     11.63,   nPOS:      0,   sWord:确@实在
row: 16,  col: 19,  eWeight:      3.92,   nPOS:      0,   sWord:确实@在
row: 17,  col: 19,  eWeight:     10.98,   nPOS:      0,   sWord:实@在
row: 16,  col: 20,  eWeight:     10.97,   nPOS:      0,   sWord:确实@在理
row: 17,  col: 20,  eWeight:     10.98,   nPOS:      0,   sWord:实@在理
row: 18,  col: 21,  eWeight:     11.17,   nPOS:      0,   sWord:实在@理
row: 19,  col: 21,  eWeight:      5.62,   nPOS:      0,   sWord:在@理
row: 20,  col: 22,  eWeight:     14.30,   nPOS:  24832,   sWord:在理@末##末
row: 21,  col: 22,  eWeight:     11.95,   nPOS:      0,   sWord:理@末##末


//==== NShortPath 初步切分的到的 N 个结果：

始##始, 他, 在, 1, 月份, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1, 月份, 大会, 上, 说, 的, 确实, 在理, 末##末,
始##始, 他, 在, 1, 月份, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1, 月, 份, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1, 月份, 大, 会上, 说, 的, 确实, 在理, 末##末,


//==== 经过数字、日期合并等策略处理后的 N 个结果：

始##始, 他, 在, 1月份, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1月份, 大会, 上, 说, 的, 确实, 在理, 末##末,
始##始, 他, 在, 1月份, 大, 会上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1月, 份, 大会, 上, 说, 的, 确实, 在, 理, 末##末,
始##始, 他, 在, 1月份, 大, 会上, 说, 的, 确实, 在理, 末##末,

这些内容在前面的文章中已经涉及过，我这里主要说说SharpICTCLAS中两处地方的内容，分别是原子分词以及数字日期合并策略。

2、原子分词

原子分词看起来应当是程序中最简单的部分，无非是将汉字逐一分开。但是也是最值得改进的地方。SharpICTCLAS目前仍然沿用了原有ICTCLAS的算法并做了微小调整。但我对于 这种原子分词方法不太满意，如果有机会，可以考虑使用一系列正则表达式将某些“原子”词单独摘出来。比如“甲子”、“乙亥”等年份信息属于原子信息，还有URL、Email等都可以预先进行原子识别，这可以大大简化后续工作。因此日后可以考虑这方面的处理。

3、对结果的处理

ICTCLAS与SharpICTCLAS都通过NShortPath计算最短路径并将结果以数组的方式进行输出，数组仅仅记录了分词的位置，我们还需要通过一些后续处理手段将这些数组转换成“分词”结果。

原有ICTCLAS的实现如下：

Copy Code

ICTCLAS对NShortPath结果的处理

while (i < m_nSegmentCount)
{
  BiPath2UniPath(nSegRoute[i]);  //Path convert to unipath
  GenerateWord(nSegRoute, i);    //Gernerate word according the Segmentation route
  i++;
}

其中这个BiPath2UniPath方法做的工作可以用如下案例说明：

由此可见UniPath记录了针对原子分词的分割位置。而后面的GenerateWord方法又针对这个数组去做合并及优化工作。

本人在SharpICTCLAS的改造过程中发现在这里数组的表述方式给后续工作带来了很大的困难（可以考虑一下，让你合并链表中两个相邻结点简单呢还是数组中两个相邻结点简单？），所以我决定在SharpICTCLAS中将BiPath转换为链表结构供后续使用，实践证明简化了不少工作。

这点在BiSegment方法中有所体现，如下：

linkedArray = BiPath2LinkedArray(spResult[i], segGraph, atomSegment);

这样改造后，还使得原有ICTCLAS中 int *m_npWordPosMapTable; 不再需要，与其相关的代码也可以一并删除了。

4、日期、数字合并策略

数字、日期等合并以及拆分策略的实施是在GenerateWord方法中实现的，原有ICTCLAS中，该方法是一个超级庞大的方法，里面有不下6、7层的if嵌套、while嵌套等，分析其内部功能的工作异常复杂。经过一番研究后，我将其中的主要功能部分提取出来，改用了“管道”方式进行处理，简化了代码复杂度。但对于部分逻辑结构异常复杂的日期时间识别功能，SharpICTCLAS中仍然保留了绝大多数原始内容。

让我们先来看看原始ICTCLAS的GenerateWord方法（超级长的一个方法）：

Copy Code

ICTCLAS中GenerateWord方法

//Generate Word according the segmentation route
bool CSegment::GenerateWord(int **nSegRoute, int nIndex)
{
  unsigned int i = 0, k = 0;
  int j, nStartVertex, nEndVertex, nPOS;
  char sAtom[WORD_MAXLENGTH], sNumCandidate[100], sCurWord[100];
  ELEMENT_TYPE fValue;
  while (nSegRoute[nIndex][i] !=  - 1 && nSegRoute[nIndex][i + 1] !=  - 1 &&
    nSegRoute[nIndex][i] < nSegRoute[nIndex][i + 1])
  {
    nStartVertex = nSegRoute[nIndex][i];
    j = nStartVertex; //Set the start vertex
    nEndVertex = nSegRoute[nIndex][i + 1]; //Set the end vertex
    nPOS = 0;
    m_graphSeg.m_segGraph.GetElement(nStartVertex, nEndVertex, &fValue, &nPOS);
    sAtom[0] = 0;
    while (j < nEndVertex)
    {
      //Generate the word according the segmentation route
      strcat(sAtom, m_graphSeg.m_sAtom[j]);
      j++;
    }
    m_pWordSeg[nIndex][k].sWord[0] = 0; //Init the result ending
    strcpy(sNumCandidate, sAtom);
    while (sAtom[0] != 0 && (IsAllNum((unsigned char*)sNumCandidate) ||
      IsAllChineseNum(sNumCandidate)))
    {
      //Merge all seperate continue num into one number
      //sAtom[0]!=0: add in 2002-5-9
      strcpy(m_pWordSeg[nIndex][k].sWord, sNumCandidate);
      //Save them in the result segmentation
      i++; //Skip to next atom now 
      sAtom[0] = 0;

      while (j < nSegRoute[nIndex][i + 1])
      {
        //Generate the word according the segmentation route
        strcat(sAtom, m_graphSeg.m_sAtom[j]);
        j++;
      }
      strcat(sNumCandidate, sAtom);
    }
    unsigned int nLen = strlen(m_pWordSeg[nIndex][k].sWord);
    if (nLen == 4 && CC_Find("第上成±—＋∶·．／",
      m_pWordSeg[nIndex][k].sWord) || nLen == 1 && strchr("+-./",
      m_pWordSeg[nIndex][k].sWord[0]))
    {
      //Only one word
      strcpy(sCurWord, m_pWordSeg[nIndex][k].sWord); //Record current word
      i--;
    }
    else if (m_pWordSeg[nIndex][k].sWord[0] == 0)
    //Have never entering the while loop
    {
      strcpy(m_pWordSeg[nIndex][k].sWord, sAtom);
      //Save them in the result segmentation
      strcpy(sCurWord, sAtom); //Record current word
    }
    else
    {
      //It is a num
      if (strcmp("－－", m_pWordSeg[nIndex][k].sWord) == 0 || strcmp("—",
        m_pWordSeg[nIndex][k].sWord) == 0 || m_pWordSeg[nIndex][k].sWord[0] ==
        '-' && m_pWordSeg[nIndex][k].sWord[1] == 0)
      //The delimiter "－－"
      {
        nPOS = 30464; //'w'*256;Set the POS with 'w'
        i--; //Not num, back to previous word
      }
      else
      {
        //Adding time suffix

        char sInitChar[3];
        unsigned int nCharIndex = 0; //Get first char
        sInitChar[nCharIndex] = m_pWordSeg[nIndex][k].sWord[nCharIndex];
        if (sInitChar[nCharIndex] < 0)
        {
          nCharIndex += 1;
          sInitChar[nCharIndex] = m_pWordSeg[nIndex][k].sWord[nCharIndex];
        }
        nCharIndex += 1;
        sInitChar[nCharIndex] = '\0';
        if (k > 0 && (abs(m_pWordSeg[nIndex][k - 1].nHandle) == 27904 || abs
          (m_pWordSeg[nIndex][k - 1].nHandle) == 29696) && (strcmp(sInitChar, 
          "—") == 0 || sInitChar[0] == '-') && (strlen
          (m_pWordSeg[nIndex][k].sWord) > nCharIndex))
        {
          //3-4月                                 //27904='m'*256
          //Split the sInitChar from the original word
          strcpy(m_pWordSeg[nIndex][k + 1].sWord, m_pWordSeg[nIndex][k].sWord +
            nCharIndex);
          m_pWordSeg[nIndex][k + 1].dValue = m_pWordSeg[nIndex][k].dValue;
          m_pWordSeg[nIndex][k + 1].nHandle = 27904;
          m_pWordSeg[nIndex][k].sWord[nCharIndex] = 0;
          m_pWordSeg[nIndex][k].dValue = 0;
          m_pWordSeg[nIndex][k].nHandle = 30464; //'w'*256;
          m_graphOptimum.SetElement(nStartVertex, nStartVertex + 1,
            m_pWordSeg[nIndex][k].dValue, m_pWordSeg[nIndex][k].nHandle,
            m_pWordSeg[nIndex][k].sWord);
          nStartVertex += 1;
          k += 1;
        }
        nLen = strlen(m_pWordSeg[nIndex][k].sWord);
        if ((strlen(sAtom) == 2 && CC_Find("月日时分秒", sAtom)) || strcmp
          (sAtom, "月份") == 0)
        {
          //2001年
          strcat(m_pWordSeg[nIndex][k].sWord, sAtom);
          strcpy(sCurWord, "未##时");
          nPOS =  - 29696; //'t'*256;//Set the POS with 'm'
        }
        else if (strcmp(sAtom, "年") == 0)
        {
          if (IsYearTime(m_pWordSeg[nIndex][k].sWord))
          //strncmp(sAtom,"年",2)==0&&
          {
            //1998年，
            strcat(m_pWordSeg[nIndex][k].sWord, sAtom);
            strcpy(sCurWord, "未##时");
            nPOS =  - 29696; //Set the POS with 't'
          }
          else
          {
            strcpy(sCurWord, "未##数");
            nPOS =  - 27904; //Set the POS with 'm'
            i--; //Can not be a time word
          }
        }
        else
        {
          //早晨/t  五点/t 
          if (strcmp(m_pWordSeg[nIndex][k].sWord + strlen
            (m_pWordSeg[nIndex][k].sWord) - 2, "点") == 0)
          {
            strcpy(sCurWord, "未##时");
            nPOS =  - 29696; //Set the POS with 't'
          }
          else
          {
            if (!CC_Find("∶·．／", m_pWordSeg[nIndex][k].sWord + nLen - 2) &&
              m_pWordSeg[nIndex][k].sWord[nLen - 1] != '.' &&
              m_pWordSeg[nIndex][k].sWord[nLen - 1] != '/')
            {
              strcpy(sCurWord, "未##数");
              nPOS =  - 27904; //'m'*256;Set the POS with 'm'
            }
            else if (nLen > strlen(sInitChar))
            {
              //Get rid of . example 1.
              if (m_pWordSeg[nIndex][k].sWord[nLen - 1] == '.' ||
                m_pWordSeg[nIndex][k].sWord[nLen - 1] == '/')
                m_pWordSeg[nIndex][k].sWord[nLen - 1] = 0;
              else
                m_pWordSeg[nIndex][k].sWord[nLen - 2] = 0;
              strcpy(sCurWord, "未##数");
              nPOS =  - 27904; //'m'*256;Set the POS with 'm'
              i--;
            }
          }
          i--; //Not num, back to previous word
        }
      }
      fValue = 0;
      nEndVertex = nSegRoute[nIndex][i + 1]; //Ending POS changed to latter
    }
    m_pWordSeg[nIndex][k].nHandle = nPOS; //Get the POS of current word
    m_pWordSeg[nIndex][k].dValue = fValue; 
      //(int)(MAX_FREQUENCE*exp(-fValue));//Return the frequency of current word
    m_graphOptimum.SetElement(nStartVertex, nEndVertex, fValue, nPOS, sCurWord);
    //Generate optimum segmentation graph according the segmentation result
    i++; //Skip to next atom
    k++; //Accept next word
  }
  m_pWordSeg[nIndex][k].sWord[0] = 0;
  m_pWordSeg[nIndex][k].nHandle =  - 1; //Set ending
  return true;
}

SharpICTCLAS中，对这段超长代码进行了功能剥离，采用一种“流水线”式的处理流程，不同工作部分负责处理不同功能，而将处理结果节节传递（很象设计模式中的职责链模式），这样使得整体结构变的清晰起来。SharpICTCLAS中GenerateWord方法定义如下：

Copy Code

SharpICTCLAS中的GenerateWord方法

private static WordResult[] GenerateWord(int[] uniPath, WordLinkedArray linkedArray, 
   RowFirstDynamicArray<ChainContent> m_graphOptimum)
{
   if (linkedArray.Count == 0)
      return null;

   //--------------------------------------------------------------------
   //Merge all seperate continue num into one number
   MergeContinueNumIntoOne(ref linkedArray);

   //--------------------------------------------------------------------
   //The delimiter "－－"
   ChangeDelimiterPOS(ref linkedArray);

   //--------------------------------------------------------------------
   //如果前一个词是数字，当前词以“－”或“-”开始，并且不止这一个字符，
   //那么将此“－”符号从当前词中分离出来。
   //例如 “3 / -4 / 月”需要拆分成“3 / - / 4 / 月”
   SplitMiddleSlashFromDigitalWords(ref linkedArray);

   //--------------------------------------------------------------------
   //1、如果当前词是数字，下一个词是“月、日、时、分、秒、月份”中的一个，则合并,且当前词词性是时间
   //2、如果当前词是可以作为年份的数字，下一个词是“年”，则合并，词性为时间，否则为数字。
   //3、如果最后一个汉字是"点" ，则认为当前数字是时间
   //4、如果当前串最后一个汉字不是"∶·．／"和半角的'.''/'，那么是数
   //5、当前串最后一个汉字是"∶·．／"和半角的'.''/'，且长度大于1，那么去掉最后一个字符。例如"1."
   CheckDateElements(ref linkedArray);

   //--------------------------------------------------------------------
   //遍历链表输出结果
   WordResult[] result = new WordResult[linkedArray.Count];

   WordNode pCur = linkedArray.first;
   int i = 0;
   while (pCur != null)
   {
      WordResult item = new WordResult();
      item.sWord = pCur.theWord.sWord;
      item.nPOS = pCur.theWord.nPOS;
      item.dValue = pCur.theWord.dValue;
      result[i] = item;

      m_graphOptimum.SetElement(pCur.row, pCur.col, new ChainContent(item.dValue, item.nPOS, pCur.sWordInSegGraph));

      pCur = pCur.next;
      i++;
   }

   return result;
}

从中可以看到linkedArray作为“绣球”在多个处理流程中被传递和加工，最终输出相应的结果。只是CheckDateElement方法内容涉及到的东西太多，因此目前看来其实现仍有些臃肿，日后可以进一步进行功能的剥离。

• 小结

1）Segment类是SharpICTCLAS中最大的一个类，实现了分词过程中一些关键的步骤。

2）Segment类对原有ICTCLAS中的代码做了大量修改，力争通过新的数据结构简化原有操作。

3）Segment中定义了部分静态方法以提高调用效率。

来源：http://www.cnblogs.com/zhenyulu/category/85598.html

N-最短路径的计算方式与1-最短路径基本相同，只是在记录所有可达路径时，要保留最短的前N个结果。让我们仍然以上篇文章的案例来看看如何实现N-最短路径的运算。

1、数据表示

这里我们仍然沿用前文例子，对下图求N-最短路径，每条边的权重已经在图中标注出来了。

（图一）

2、运算过程

仍然象1-最短路径一样，计算出每个结点上可达N-最短路的PreNode。我们这里以2-最短路径为例：

1）首先计算出每个结点上所有可达路径的可能路径长度并按从小到大排序。

2）根据排序结果取前2种路径长度并分别记录进各结点的PreNode队列。如下图：

（图二）

在该图中，到达1号、2号、3号结点的路径虽然有多条，但长度只有一种长度，但到达4号“D”结点的路径长度有两种，即长度可能是3也可能是4，此时在“最短路”处（index＝0）记录长度为3时的PreNode，在“次短路”处（index＝1）处记录长度为4时的PreNode，依此类推。

值得注意的是，此时用来记录PreNode的坐标已经由前文求“1-最短路径”时的一个数（ParentNode值)变为2个数（ParentNode值以及index值）。

如图二所示，到达6号“末”结点的次短路径由两个ParentNode，一个是index=0中的4号结点，一个是index=1的5号结点，它们都使得总路径长度为6。

3、具体实现

在具体实现上述算法时，首先要求得所有可能路径的长度，这在SharpICTCLAS中是通过一个EnQueueCurNodeEdges方法实现的，上篇文章给出了它的简化版本的代码，这里将完整的求N-最短路径的EnQueueCurNodeEdges方法代码放上来：

Copy Code

程序

//====================================================================
// 将所有到当前结点（nCurNode）可能的边根据eWeight排序并压入队列
//====================================================================
private static void EnQueueCurNodeEdges(ref CQueue queWork, int nCurNode)
{
   int nPreNode;
   double eWeight;
   ChainItem<ChainContent> pEdgeList;

   queWork.Clear();
   pEdgeList = m_apCost.GetFirstElementOfCol(nCurNode);

   // Get all the edges
   while (pEdgeList != null && pEdgeList.col == nCurNode)
   {
      nPreNode = pEdgeList.row;  // 很特别的命令，利用了row与col的关系
      eWeight = pEdgeList.Content.eWeight; //Get the eWeight of edges

      for (int i = 0; i < m_nValueKind; i++)
      {
         // 第一个结点，没有PreNode，直接加入队列
         if (nPreNode == 0)
         {
            queWork.EnQueue(new QueueElement(nPreNode, i, eWeight));
            break;
         }

         // 如果PreNode的Weight == Predefine.INFINITE_VALUE，则没有必要继续下去了
         if (m_pWeight[nPreNode - 1][i] == Predefine.INFINITE_VALUE)
            break;

         queWork.EnQueue(new QueueElement(nPreNode, i, eWeight + m_pWeight[nPreNode - 1][i]));
      }
      pEdgeList = pEdgeList.next;
   }
}

这里的m_nValueKind就是你希望N-最短路径保留几种路径的结果。

当m_nValueKind＝2时，我们求得了2-最短路径，路径长度有两种，分别长度为5和6，而路径总共有6条，如下：

最短路径：

• 0, 1, 3, 6,
• 0, 1, 2, 3, 6,
• 0, 1, 2, 4, 5, 6,

========================

次短路径

• 0, 1, 2, 4, 6,
• 0, 1, 3, 4, 5, 6,
• 0, 1, 2, 3, 4, 5, 6,

4、求解N-最短路径

N-最短路径的最终输出与上篇文章完全一致，仍然是借助堆栈完成的。只不过根据index的取值的不同，分多次完成压栈与出栈的操作而已。此处就不再重复，感兴趣的可以再看看上一篇文章。

• 小结

1）N-最短路径中用来记录PreNode的坐标由前文求“1-最短路径”时的一个数（ParentNode值)变为2个数（ParentNode值以及index值）。

2）N-最短路径并不意味着求得得路径只有N条。

3）文中只演示了2-最短路径，但可以推广到N-最短路径。程序求得的3-最短路径中，最长的路径为：（0, 1, 3, 4, 6）与（0, 1, 2, 3, 4, 6），它们的长度都是7。

来源：http://www.cnblogs.com/zhenyulu/category/85598.html

1、数据表示

这里我们求最短路的例子使用如下的有向图，每条边的权重已经在图中标注出来了。

（图一）

根据上篇文章内容，该图该可以等价于如下的二维表格表示：

（图二）

而对应于该表格的是一个ColumnFirstDynamicArray，共有10个结点，每个结点的取值如下表所示：

Copy Code

该示例对应的ColumnFirstDynamicArray

row:0,  col:1,  eWeight:1,  nPOS:0,  sWord: 始@A
row:1,  col:2,  eWeight:1,  nPOS:0,  sWord: A@B
row:1,  col:3,  eWeight:2,  nPOS:0,  sWord: A@C
row:2,  col:3,  eWeight:1,  nPOS:0,  sWord: B@C
row:2,  col:4,  eWeight:1,  nPOS:0,  sWord: B@D
row:3,  col:4,  eWeight:1,  nPOS:0,  sWord: C@D
row:4,  col:5,  eWeight:1,  nPOS:0,  sWord: D@E
row:3,  col:6,  eWeight:2,  nPOS:0,  sWord: C@末
row:4,  col:6,  eWeight:3,  nPOS:0,  sWord: D@末
row:5,  col:6,  eWeight:1,  nPOS:0,  sWord: E@末

2、计算出每个结点上可达最短路的PreNode

在求解N-最短路径之前，先看看如何求最短PreNode。如下图所示：

（图三）

首先计算出到达每个结点的最短路径，并将该结点的父结点压入该结点所对应的队列。例如3号“C”结点，到达该结点的最短路径长度为3，它的Parent结点可以是1号“A”结点，也可以是2号“B”结点，因此在队列中存储了两个PreNode结点。

而在实际计算时，如何知道到达3号“C”结点的路径有几条呢？其实我们首先计算所有到达3号“C”结点的路径长度，并按照路径长度从小到大的顺序排列（所有这些都是靠CQueue这个类完成的），然后从队列中依次向后取值，取出所有最短路径对应的PreNode。

计算到当前结点（nCurNode）可能的边，并根据总路径长度由小到大压入队列的代码如下（经过简化）：

Copy Code

EnQueueCurNodeEdges方法

//====================================================================
// 将所有到当前结点（nCurNode）可能的边根据eWeight排序并压入队列
//====================================================================
private void EnQueueCurNodeEdges(ref CQueue queWork, int nCurNode)
{
   int nPreNode;
   double eWeight;
   ChainItem<ChainContent> pEdgeList;

   queWork.Clear();
   pEdgeList = m_apCost.GetFirstElementOfCol(nCurNode);

   // 获取所有到当前结点的边
   while (pEdgeList != null && pEdgeList.col == nCurNode)
   {
      nPreNode = pEdgeList.row;  // 很特别的命令，利用了row与col的关系
      eWeight = pEdgeList.Content.eWeight;

      // 第一个结点，没有PreNode，直接加入队列
      if (nPreNode == 0)
      {
         queWork.EnQueue(new QueueElement(nPreNode, eWeight));
         break;
      }

      queWork.EnQueue(new QueueElement(nPreNode, eWeight + m_pWeight[nPreNode - 1]));
      pEdgeList = pEdgeList.next;
   }
}

这段代码中有一行很特别的命令，就是用红颜色注释的那句“nPreNode = pEdgeList.row;”，让我琢磨了半天终于弄明白原有ICTCLAS用意的一句话。这需要参考本文图二，为了方便起见，我将它挪到了这里：

注意 3 号“C”结点在该表中处于第 3 列，所有可以到达该结点的边就是该列中的元素（目前有两个元素“A@C”与“B@C”）。而与 3 号“C”结点构成这两条边的PreNode结点恰恰是这两个元素的“行号”，分别是 1 号“A”结点与 2 号“B”结点。正是因为这种特殊的对应关系，为我们检索所有可达边提供了便捷的方法。阅读上面那段代码务必把握好这种关系。

3、求解最短路径

求出每个结点上最短路径的PreNode后就需要据此推导出完整的最短路径。原ICTCLAS代码中是靠GetPaths方法实现的，只是到现在我也没有读懂这个方法的代码究竟想干什么 ，只知道它用了若干个while，若干个if，若干个嵌套...（将ICTCLAS中的GetPaths放上来，如果谁读懂了，回头给我讲讲 ，感觉应该和我的算法差不多）。

Copy Code

NShortPath.cpp程序中的GetPaths方法

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

我重写了求解最短路径的方法，其算法表述如下：

（图四）

1）首先将最后一个元素压入堆栈（本例中是6号结点），什么时候这个元素弹出堆栈，什么时候整个任务结束。

2）对于每个结点的PreNode队列，维护了一个当前指针，初始状态都指向PreNode队列中第一个元素。

3）从右向左依次取出PreNode队列中的当前元素并压入堆栈，并将队列指针重新指向队列中第一个元素。如图四：6号元素PreNode是3，3号元素PreNode是1，1号元素PreNode是0。

4）当第一个元素压入堆栈后，输出堆栈内容即为一条队列。本例中0, 1, 3, 6便是一条最短路径。

5）将堆栈中的内容依次弹出，每弹出一个元素，就将当时压栈时对应的PreNode队列指针下移一格。如果到了末尾无法下移，则继续执行第5步，如果仍然可以移动，则执行第3步。

对于本例，先将“0”弹出堆栈，该元素对应的是1号“A”结点的PreNode队列，该队列的当前指针已经无法下移，因此继续弹出堆栈中的“1” ；该元素对应3号“C”结点，因此将3号“C”结点对应的PreNode队列指针下移。由于可以移动，因此将队列中的2压入队列，2号“B”结点的PreNode是1，因此再压入1，依次类推，直到0被压入，此时又得到了一条最短路径，那就是0，1，2，3，6。如下图：

（图五）

再往下，0、1、2都被弹出堆栈，3被弹出堆栈后，由于它对应的6号元素PreNode队列记录指针仍然可以下移，因此将5压入堆栈并依次将其PreNode入栈，直到0被入栈。此时输出第3条最短路径：0, 1, 2, 4, 5, 6。入下图：

（图六）

输出完成后，紧接着又是出栈，此时已经没有任何堆栈元素对应的PreNode队列指针可以下移，于是堆栈中的最后一个元素6也被弹出堆栈，此时输出工作完全结束。我们得到了3条最短路径，分别是：

• 0, 1, 3, 6,
• 0, 1, 2, 3, 6,
• 0, 1, 2, 4, 5, 6,

让我们看看在SharpICTCLAS中，该算法是如何实现的：

Copy Code

SharpICTCLAS中的GetPaths方法

//====================================================================
// 注：index ＝ 0 : 最短的路径； index = 1 ： 次短的路径
//     依此类推。index <= this.m_nValueKind
//====================================================================
public List<int[]> GetPaths(int index)
{
   Stack<PathNode> stack = new Stack<PathNode>();
   int curNode = m_nNode - 1, curIndex = index;
   QueueElement element;
   PathNode node;
   int[] aPath;
   List<int[]> result = new List<int[]>();

   element = m_pParent[curNode - 1][curIndex].GetFirst();
   while (element != null)
   {
      // ---------- 通过压栈得到路径 -----------
      stack.Push(new PathNode(curNode, curIndex));
      stack.Push(new PathNode(element.nParent, element.nIndex));
      curNode = element.nParent;

      while (curNode != 0)
      {
         element = m_pParent[element.nParent - 1][element.nIndex].GetFirst();
         stack.Push(new PathNode(element.nParent, element.nIndex));
         curNode = element.nParent;
      }

      // -------------- 输出路径 --------------
      PathNode[] nArray = stack.ToArray();            
      aPath = new int[nArray.Length];
      
      for(int i=0; i<aPath.Length; i++)
         aPath[i] = nArray[i].nParent;

      result.Add(aPath);

      // -------------- 出栈以检查是否还有其它路径 --------------
      do
      {
         node = stack.Pop();
         curNode = node.nParent;
         curIndex = node.nIndex;

      } while (curNode < 1 || (stack.Count != 0 && !m_pParent[curNode - 1][curIndex].CanGetNext));

      element = m_pParent[curNode - 1][curIndex].GetNext();
   }

   return result;
}

注意，上面的代码是N-最短路径的，比起1-最短路径来说增加了点复杂度，但总体架构不变。这段代码将原有ICTCLAS的70多行求解路径代码缩短到了40多行。

• 小结

1）N-最短路径的求解比较复杂，本文先从求解1-最短路径着手，说明SharpICTCLAS是如何计算的，在下篇文章中将推广到N-最短路径。

2）1-最短路径并不意味着只有一条最短路径，而是路径最短的若干条路径。就如本文案例所示，1-最短路径算法最终求得了3条路径，它们的长度都是5，因此都是最短路径。

来源：http://www.cnblogs.com/zhenyulu/category/85598.html