NShortPath.cpp
上传用户:sunyong76
上传日期:2021-10-03
资源大小:2236k
文件大小:8k
源码类别:

多国语言处理

开发平台:

Java

  1. //////////////////////////////////////////////////////////////////////
  2. //ICTCLAS简介:计算所汉语词法分析系统ICTCLAS(Institute of Computing Technology, Chinese Lexical Analysis System),
  3. //             功能有:中文分词;词性标注;未登录词识别。
  4. //             分词正确率高达97.58%(973专家评测结果),
  5. //             未登录词识别召回率均高于90%,其中中国人名的识别召回率接近98%;
  6. //             处理速度为31.5Kbytes/s。
  7. //著作权:  Copyright?2002-2005中科院计算所 职务著作权人:张华平 刘群
  8. //遵循协议:自然语言处理开放资源许可证1.0
  9. //Email: zhanghp@software.ict.ac.cn
  10. //Homepage:www.nlp.org.cn;mtgroup.ict.ac.cn
  11. /****************************************************************************
  12.  *
  13.  * Copyright (c) 2000, 2001 
  14.  *     Software Research Lab.
  15.  *     Institute of Computing Tech.
  16.  *     Chinese Academy of Sciences
  17.  *     All rights reserved.
  18.  *
  19.  * This file is the confidential and proprietary property of 
  20.  * Institute of Computing Tech. and the posession or use of this file requires 
  21.  * a written license from the author.
  22.  *
  23.  * Abstract:
  24.  *      N-Shortest Path Problem for graph in word segement
  25.  *
  26.  * Author: Kevin Chang (zhanghp@software.ict.ac.cn)
  27.  *
  28.  * Notes:
  29.  *
  30.  ****************************************************************************/
  31. // NShortPath.cpp: implementation of the CNShortPath class.
  32. //
  33. //////////////////////////////////////////////////////////////////////
  34. #include "stdafx.h"
  35. #include "NShortPath.h"
  36. #include "Segment.h"
  37. #include <memory.h>
  38. #include <string.h>
  39. //#include <stdlib.h>
  40. //////////////////////////////////////////////////////////////////////
  41. // Construction/Destruction
  42. //////////////////////////////////////////////////////////////////////
  43. CNShortPath::CNShortPath(CDynamicArray *apCost,unsigned int nValueKind)
  44. {
  45.        m_apCost=apCost;//Set the cost
  46.    m_nValueKind=nValueKind;//Set the value kind
  47.    m_nVertex=apCost->m_nCol+1;
  48.        if(m_nVertex<apCost->m_nRow+1)
  49.    m_nVertex=apCost->m_nRow+1;//Get the vertex numbers
  50.    m_pParent=new CQueue*[m_nVertex-1];//not including the first node
  51.    m_pWeight=new ELEMENT_TYPE *[m_nVertex-1];
  52. //    m_pParent=(CQueue **)malloc((m_nVertex-1)*sizeof(CQueue *));//not including the first node
  53. //    m_pWeight=(ELEMENT_TYPE **)malloc(sizeof(ELEMENT_TYPE *)*(m_nVertex-1));
  54. for(unsigned int i=0;i<m_nVertex-1;i++)//The queue array for every node
  55. {
  56. m_pParent[i]=new CQueue[nValueKind];
  57. m_pWeight[i]=new ELEMENT_TYPE[nValueKind];
  58. // m_pParent[i]=(CQueue *)malloc(sizeof(CQueue)*nValueKind);
  59. // m_pWeight[i]=(ELEMENT_TYPE *)malloc(sizeof(ELEMENT_TYPE)*nValueKind);
  60. }
  61. }
  62. CNShortPath::~CNShortPath()
  63. {
  64.  for(unsigned int i=0;i<m_nVertex-1;i++)//The queue array for every node
  65.  {
  66.  delete [] m_pWeight[i];
  67. //  free(m_pWeight[i]);
  68. /*  for(unsigned int j=0;j<m_nValueKind;j++)
  69.  {
  70.  m_pParent[i][j].~CQueue();//;delete 
  71.  }*/
  72. //  free(m_pParent[i]);
  73.          delete [] m_pParent[i];
  74.  }
  75.  delete [] m_pWeight;
  76.  delete [] m_pParent;//not including the first node
  77. //  free(m_pWeight);
  78. //  free(m_pParent);
  79. }
  80. //bBest=true: only get one best result and ignore others
  81. //Added in 2002-1-24
  82. void CNShortPath::GetPaths(unsigned int nNode,unsigned int nIndex,int **nResult,bool bBest)
  83. {
  84.     CQueue queResult;
  85. unsigned int nCurNode,nCurIndex,nParentNode,nParentIndex,nResultIndex=0;
  86.     
  87. if(m_nResultCount>=MAX_SEGMENT_NUM)//Only need 10 result
  88. return ;
  89. nResult[m_nResultCount][nResultIndex]=-1;//Init the result 
  90. queResult.Push(nNode,nIndex);
  91.     nCurNode=nNode;
  92. nCurIndex=nIndex;
  93.     bool bFirstGet;
  94.     while(!queResult.IsEmpty())
  95. {
  96. while(nCurNode>0)//
  97. {//Get its parent and store them in nParentNode,nParentIndex
  98. if(m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,0,false,true)!=-1)
  99. {
  100. if(nParentNode==nCurNode&&nParentIndex==nCurIndex)
  101. break;
  102.    nCurNode=nParentNode;
  103.    nCurIndex=nParentIndex;
  104.    
  105. }
  106. if(nCurNode>0)
  107.                 queResult.Push(nCurNode,nCurIndex);
  108. }
  109. if(nCurNode==0)
  110. { //Get a path and output
  111.       nResult[m_nResultCount][nResultIndex++]=nCurNode;//Get the first node
  112.    bFirstGet=true;
  113.    nParentNode=nCurNode;
  114.    while(queResult.Pop(&nCurNode,&nCurIndex,0,false,bFirstGet)!=-1)
  115.    {
  116.    nResult[m_nResultCount][nResultIndex++]=nCurNode;
  117.             bFirstGet=false;
  118.    nParentNode=nCurNode;
  119.    }
  120.    nResult[m_nResultCount][nResultIndex]=-1;//Set the end
  121.    m_nResultCount+=1;//The number of result add by 1
  122.    if(m_nResultCount>=MAX_SEGMENT_NUM)//Only need 10 result
  123. return ;
  124.    nResultIndex=0;
  125.    nResult[m_nResultCount][nResultIndex]=-1;//Init the result 
  126.    if(bBest)//Return the best result, ignore others
  127.    return ;
  128. }
  129. queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top node
  130.         while(queResult.IsEmpty()==false&&(m_pParent[nCurNode-1][nCurIndex].IsSingle()||m_pParent[nCurNode-1][nCurIndex].IsEmpty(true)))
  131. {
  132.        queResult.Pop(&nCurNode,&nCurIndex,0);//Get rid of it
  133.    queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top node
  134. }
  135.         if(queResult.IsEmpty()==false&&m_pParent[nCurNode-1][nCurIndex].IsEmpty(true)==false)
  136. {
  137.    m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,0,false,false);
  138.    nCurNode=nParentNode;
  139.    nCurIndex=nParentIndex;
  140.    if(nCurNode>0)
  141.        queResult.Push(nCurNode,nCurIndex);
  142. }
  143. }
  144. }
  145. int CNShortPath::Output(int **nResult,bool bBest,int *npCount)
  146. {//sResult is a string array
  147.   unsigned int i;
  148.   
  149.   m_nResultCount=0;//The 
  150.   if(m_nVertex<2)
  151.   {
  152.   nResult[0][0]=0;
  153.   nResult[0][1]=1;
  154.   *npCount=1;
  155.   return 1;
  156.   }
  157.   for(i=0;i<m_nValueKind&&m_pWeight[m_nVertex-2][i]<INFINITE_VALUE;i++)
  158.   {
  159.  
  160.   GetPaths(m_nVertex-1,i,nResult,bBest);
  161.  
  162.   *npCount=m_nResultCount;
  163.   if(nResult[i][0]!=-1&&bBest)//Get the best answer
  164.   return 1;
  165.       if(m_nResultCount>=MAX_SEGMENT_NUM)//Only need 10 result
  166.     return 1;
  167.   }
  168.   return 1;
  169. }
  170. int CNShortPath::ShortPath()
  171. {
  172. unsigned int nCurNode=1,nPreNode,i,nIndex;
  173. ELEMENT_TYPE eWeight;
  174. PARRAY_CHAIN pEdgeList;
  175. for(;nCurNode<m_nVertex;nCurNode++)
  176. {
  177. CQueue queWork;
  178. eWeight=m_apCost->GetElement(-1,nCurNode,0,&pEdgeList);//Get all the edges
  179. while(pEdgeList!=0 && pEdgeList->col==nCurNode)
  180. {
  181. nPreNode=pEdgeList->row;
  182. eWeight=pEdgeList->value;//Get the value of edges
  183. for(i=0;i<m_nValueKind;i++)
  184. {
  185. if(nPreNode>0)//Push the weight and the pre node infomation
  186. {
  187. if(m_pWeight[nPreNode-1][i]==INFINITE_VALUE)
  188. break;
  189. if(nPreNode!=nCurNode)
  190. queWork.Push(nPreNode,i,eWeight+m_pWeight[nPreNode-1][i]);
  191. }
  192. else
  193. {
  194. if(nPreNode!=nCurNode)
  195. queWork.Push(nPreNode,i,eWeight);
  196. break;
  197. }
  198. }//end for
  199. pEdgeList=pEdgeList->next;
  200. }//end while
  201. //Now get the result queue which sort as weight.
  202. //Set the current node information
  203. for(i=0;i<m_nValueKind;i++)
  204. {
  205. m_pWeight[nCurNode-1][i]=INFINITE_VALUE;
  206. }
  207. //memset((void *),(int),sizeof(ELEMENT_TYPE)*);
  208. //init the weight
  209. i=0;
  210. while(i<m_nValueKind&&queWork.Pop(&nPreNode,&nIndex,&eWeight)!=-1)
  211. {//Set the current node weight and parent
  212. if(m_pWeight[nCurNode-1][i]==INFINITE_VALUE)
  213. m_pWeight[nCurNode-1][i]=eWeight;
  214. else if(m_pWeight[nCurNode-1][i]<eWeight)//Next queue
  215. {
  216. i++;//Go next queue and record next weight
  217. if(i==m_nValueKind)//Get the last position
  218. break;
  219. m_pWeight[nCurNode-1][i]=eWeight;
  220. }
  221. m_pParent[nCurNode-1][i].Push(nPreNode,nIndex);
  222. }
  223. }//end for
  224. return 1;
  225. }