开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 多国语言处理 > 查看源码
Segment.cpp
资源名称：Codes and Application.rar　[点击查看]
上传用户：yxl0916
上传日期：2007-05-25
资源大小：2245k
文件大小：16k
源码类别：

多国语言处理

开发平台：

Visual C++

Segment.cpp：源码内容
  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.  *     Machine Group
  15.  *     Software Research Lab.
  16.  *     Institute of Computing Tech.
  17.  *     Chinese Academy of Sciences
  18.  *     All rights reserved.
  19.  *
  20.  * This file is the confidential and proprietary property of 
  21.  * Institute of Computing Tech. and the posession or use of this file requires 
  22.  * a written license from the author.
  23.  * Filename: Segment.cpp
  24.  * Abstract:
  25.  *           implementation of the CSegment class.
  26.  * Author:   Kevin Zhang 
  27.  *          (zhanghp@software.ict.ac.cn)
  28.  * Date:     2002-4-23
  29.  *
  30.  * Notes:  N-Shortest paths Word segmentation
  31.  *                
  32.  ****************************************************************************/
  34. #include "stdafx.h"
  35. #include "Segment.h"
  36. #include "..\Utility\Dictionary.h"
  37. #include "..\Utility\Utility.h"
  38. #include "NShortPath.h"
  39. #include <string.h>
  40. #include <math.h>
  41. //////////////////////////////////////////////////////////////////////
  42. // Construction/Destruction
  43. //////////////////////////////////////////////////////////////////////
  45. CSegment::CSegment()
  46. {
  47. //malloc buffer
  48. m_pWordSeg=new PWORD_RESULT[MAX_SEGMENT_NUM];
  49. for(int i=0;i<MAX_SEGMENT_NUM;i++)
  50. {
  51. m_pWordSeg[i]=new WORD_RESULT[MAX_WORDS];
  52. }
  53. m_npWordPosMapTable=0;//Record the start position of possible words
  54. m_nWordCount=0;//Record the End position of possible words
  55. m_graphOptimum.SetRowFirst();//Set row first
  56. }
  58. CSegment::~CSegment()
  59. {
  60. //free buffer
  61. for(int i=0;i<MAX_SEGMENT_NUM;i++)
  62. {
  63. delete m_pWordSeg[i];
  64. }
  65. delete m_pWordSeg;
  66. }
  68. bool CSegment::Segment(char *sSentence,CDictionary &dictCore,int nResultCount)
  69. {
  70. int **nSegRoute;//The segmentation route
  71. nSegRoute=new int*[MAX_SEGMENT_NUM];
  72. for(int i=0;i<MAX_SEGMENT_NUM;i++)
  73. {
  74. nSegRoute[i]=new int[MAX_SENTENCE_LEN/2];
  75. memset(nSegRoute[i],0,MAX_SENTENCE_LEN/2*sizeof(int));
  76. }
  77. m_graphSeg.m_segGraph.SetRowFirst(false);
  78. m_graphOptimum.SetRowFirst(false);
  79.   m_graphSeg.GenerateWordNet(sSentence,dictCore);
  80. CNShortPath sp(&m_graphSeg.m_segGraph,nResultCount);
  81. sp.ShortPath();
  82. sp.Output((int **)nSegRoute,false,&m_nSegmentCount);
  83. m_graphOptimum.SetEmpty();//Set graph optimum empty
  84. i=0;
  85. while(i<m_nSegmentCount)
  86. {
  87. GenerateWord(nSegRoute,i);
  88. //Gernerate word according the Segmentation route
  89. i++;
  90. }
  92. //free the memory
  93. for(i=0;i<MAX_SEGMENT_NUM;i++)
  94. {
  95. delete [] nSegRoute[i];//free the pointer memory
  96. }
  97. delete [] nSegRoute;//free the pointer array
  99. return true;
  100. }
  101. //Generate Word according the segmentation route
  102. bool CSegment::GenerateWord(int **nSegRoute, int nIndex)
  103. {
  104. unsigned int i=0,k=0;
  105. int j,nStartVertex,nEndVertex,nPOS;
  106. char sAtom[WORD_MAXLENGTH],sNumCandidate[100],sCurWord[100];
  107. ELEMENT_TYPE fValue;
  108. while(nSegRoute[nIndex][i]!=-1&&nSegRoute[nIndex][i+1]!=-1&&nSegRoute[nIndex][i]<nSegRoute[nIndex][i+1])
  109. {
  110. nStartVertex=nSegRoute[nIndex][i];
  111. j=nStartVertex;//Set the start vertex
  112. nEndVertex=nSegRoute[nIndex][i+1];//Set the end vertex
  113. nPOS=0;
  114. m_graphSeg.m_segGraph.GetElement(nStartVertex,nEndVertex,&fValue,&nPOS);
  115. sAtom[0]=0;
  116. while(j<nEndVertex)
  117. {//Generate the word according the segmentation route
  118. strcat(sAtom,m_graphSeg.m_sAtom[j]);
  119. j++;
  120. }
  121. m_pWordSeg[nIndex][k].sWord[0]=0;//Init the result ending
  122. strcpy(sNumCandidate,sAtom);
  123. while(sAtom[0]!=0&&(IsAllNum((unsigned char *)sNumCandidate)||IsAllChineseNum(sNumCandidate)))
  124. {//Merge all seperate continue num into one number
  125.  //sAtom[0]!=0: add in 2002-5-9
  126. strcpy(m_pWordSeg[nIndex][k].sWord,sNumCandidate);
  127. //Save them in the result segmentation
  128. i++;//Skip to next atom now 
  129. sAtom[0]=0;
  131. while(j<nSegRoute[nIndex][i+1])
  132. {//Generate the word according the segmentation route
  133. strcat(sAtom,m_graphSeg.m_sAtom[j]);
  134. j++;
  135. }
  136. strcat(sNumCandidate,sAtom);
  137. }
  138. unsigned int nLen=strlen(m_pWordSeg[nIndex][k].sWord);
  139. if(nLen==4&&CC_Find("第上成±—＋∶·．／",m_pWordSeg[nIndex][k].sWord)||nLen==1&&strchr("+-./",m_pWordSeg[nIndex][k].sWord[0]))
  140. {//Only one word
  141. strcpy(sCurWord,m_pWordSeg[nIndex][k].sWord);//Record current word
  142. i--;
  143. }
  144. else if(m_pWordSeg[nIndex][k].sWord[0]==0)//Have never entering the while loop
  145. {
  146. strcpy(m_pWordSeg[nIndex][k].sWord,sAtom);
  147. //Save them in the result segmentation
  148. strcpy(sCurWord,sAtom);//Record current word
  149. }
  150. else
  151. {//It is a num
  152. 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 "－－"
  153. {
  154. nPOS=30464;//'w'*256;Set the POS with 'w'
  155. i--;//Not num, back to previous word
  156. }
  157. else
  158. {//Adding time suffix
  160. char sInitChar[3];
  161. unsigned int nCharIndex=0;//Get first char
  162. sInitChar[nCharIndex]=m_pWordSeg[nIndex][k].sWord[nCharIndex];
  163. if(sInitChar[nCharIndex]<0)
  164. {
  165. nCharIndex+=1;
  166. sInitChar[nCharIndex]=m_pWordSeg[nIndex][k].sWord[nCharIndex];
  167. }
  168. nCharIndex+=1;
  169. sInitChar[nCharIndex]='';
  170. 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))
  171. {//3-4月                                 //27904='m'*256
  172.    //Split the sInitChar from the original word
  173. strcpy(m_pWordSeg[nIndex][k+1].sWord,m_pWordSeg[nIndex][k].sWord+nCharIndex);
  174. m_pWordSeg[nIndex][k+1].dValue=m_pWordSeg[nIndex][k].dValue;
  175. m_pWordSeg[nIndex][k+1].nHandle=27904;
  176. m_pWordSeg[nIndex][k].sWord[nCharIndex]=0;
  177. m_pWordSeg[nIndex][k].dValue=0;
  178. m_pWordSeg[nIndex][k].nHandle=30464;//'w'*256;
  179. m_graphOptimum.SetElement(nStartVertex,nStartVertex+1,m_pWordSeg[nIndex][k].dValue,m_pWordSeg[nIndex][k].nHandle,m_pWordSeg[nIndex][k].sWord);
  180. nStartVertex+=1;
  181. k+=1;
  182. }
  183. nLen=strlen(m_pWordSeg[nIndex][k].sWord);
  184. if((strlen(sAtom)==2&&CC_Find("月日时分秒",sAtom))||strcmp(sAtom,"月份")==0)
  185. {//2001年
  186. strcat(m_pWordSeg[nIndex][k].sWord,sAtom);
  187. strcpy(sCurWord,"未##时");
  188. nPOS=-29696;//'t'*256;//Set the POS with 'm'
  189. }
  190. else if(strcmp(sAtom,"年")==0)
  191. {
  192.  if(IsYearTime(m_pWordSeg[nIndex][k].sWord))//strncmp(sAtom,"年",2)==0&&
  193.  {//1998年，
  194. strcat(m_pWordSeg[nIndex][k].sWord,sAtom);
  195. strcpy(sCurWord,"未##时");
  196. nPOS=-29696;//Set the POS with 't'
  197.  }
  198.  else
  199.  {
  200. strcpy(sCurWord,"未##数");
  201. nPOS=-27904;//Set the POS with 'm'
  202. i--;//Can not be a time word
  203.  }
  204. }
  205.       else
  206. {
  207. //早晨/t  五点/t 
  208. if(strcmp(m_pWordSeg[nIndex][k].sWord+strlen(m_pWordSeg[nIndex][k].sWord)-2,"点")==0)
  209. {
  210. strcpy(sCurWord,"未##时");
  211. nPOS=-29696;//Set the POS with 't'
  212. }
  213. else 
  214. {
  215. if(!CC_Find("∶·．／",m_pWordSeg[nIndex][k].sWord+nLen-2)&&m_pWordSeg[nIndex][k].sWord[nLen-1]!='.'&&m_pWordSeg[nIndex][k].sWord[nLen-1]!='/')
  216. {
  217. strcpy(sCurWord,"未##数");
  218. nPOS=-27904;//'m'*256;Set the POS with 'm'
  219. }
  220. else if(nLen>strlen(sInitChar))
  221. {//Get rid of . example 1.
  222. if(m_pWordSeg[nIndex][k].sWord[nLen-1]=='.'||m_pWordSeg[nIndex][k].sWord[nLen-1]=='/')
  223. m_pWordSeg[nIndex][k].sWord[nLen-1]=0;
  224. else
  225. m_pWordSeg[nIndex][k].sWord[nLen-2]=0;
  226. strcpy(sCurWord,"未##数");
  227. nPOS=-27904;//'m'*256;Set the POS with 'm'
  228. i--;
  229. }
  230. }
  231. i--;//Not num, back to previous word
  232. }
  233. }
  234. fValue=0;
  235. nEndVertex=nSegRoute[nIndex][i+1];//Ending POS changed to latter
  236. }
  237. m_pWordSeg[nIndex][k].nHandle=nPOS;//Get the POS of current word
  238. m_pWordSeg[nIndex][k].dValue=fValue;//(int)(MAX_FREQUENCE*exp(-fValue));//Return the frequency of current word
  239. m_graphOptimum.SetElement(nStartVertex,nEndVertex,fValue,nPOS,sCurWord);
  240. //Generate optimum segmentation graph according the segmentation result
  241. i++;//Skip to next atom
  242. k++;//Accept next word
  243. }
  244. m_pWordSeg[nIndex][k].sWord[0]=0;
  245. m_pWordSeg[nIndex][k].nHandle=-1;//Set ending
  246. return true;
  247. }
  249. //DEL bool CSegment::GetSegmentResult(int nIndex,char *sResult)
  250. //DEL {
  251. //DEL  int i=0;
  252. //DEL  char sTempBuffer[WORD_MAXLENGTH];
  253. //DEL  sResult[0]=0;
  254. //DEL  if(nIndex<0||nIndex>=m_nSegmentCount)
  255. //DEL  return false;
  256. //DEL  while(m_WordSeg[nIndex][i].sWord[0]!=0)
  257. //DEL  {
  258. //DEL  sprintf(sTempBuffer,"%s/%c%c",m_WordSeg[nIndex][i].sWord,m_WordSeg[nIndex][i].nHandle/256,m_WordSeg[nIndex][i].nHandle%256);
  259. //DEL  strcat(sResult,sTempBuffer);
  260. //DEL  strcat(sResult,"  ");
  261. //DEL  i++;
  262. //DEL  }
  263. //DEL  return true;
  264. //DEL }
  265. //Word Segmentation based on optimum segmentation graph
  267. //After unknown word recognition
  268. bool CSegment::OptimumSegmet(int nResultCount)
  269. {
  270. int **nSegRoute;//The segmentation route
  271. nSegRoute=new int*[MAX_SEGMENT_NUM];
  272. for(int i=0;i<MAX_SEGMENT_NUM;i++)
  273. {
  274. nSegRoute[i]=new int[MAX_SENTENCE_LEN/2];
  275. }
  276. CNShortPath sp(&m_graphOptimum,nResultCount);
  277. sp.ShortPath();
  278. sp.Output((int **)nSegRoute,false,&m_nSegmentCount);
  279. i=0;
  280. m_graphSeg.m_segGraph=m_graphOptimum;
  281. m_graphOptimum.SetEmpty();//Set graph optimum empty
  282. while(i<m_nSegmentCount)
  283. {
  284. GenerateWord(nSegRoute,i);
  285. //Gernerate word according the Segmentation route
  286. i++;
  287. }
  289. //free the memory
  290. for(i=0;i<MAX_SEGMENT_NUM;i++)
  291. {
  292. delete [] nSegRoute[i];//free the pointer memory
  293. }
  294. delete [] nSegRoute;//free the pointer array
  295. return true;
  296. }
  298. int CSegment::GetResultCount(PWORD_RESULT pItem)
  299. {
  300. int nCount=0;
  301. while(pItem[nCount].sWord[0]!=0)
  302. {
  303. nCount+=1;
  304. }
  305. return nCount;
  306. }
  308. bool CSegment::GetLastWord(PWORD_RESULT pItem, char *sWordRet)
  309. {
  310. int nCount=0;
  311. sWordRet[0]=0;
  312. while(pItem[nCount].sWord[0]!=0)
  313. {
  314. strcpy(sWordRet,pItem[nCount].sWord);
  315. nCount+=1;
  316. }
  317. return !sWordRet[0];
  318. }
  320. bool CSegment::IsYearTime(char *sNum)
  321. {//Judge whether the sNum is a num genearating year
  322. unsigned int nLen=strlen(sNum);
  323. char sTemp[3];
  324. strncpy(sTemp,sNum,2);
  325. sTemp[2]=0;
  326. if(IsAllSingleByte((unsigned char *)sNum)&&(nLen==4||nLen==2&&sNum[0]>'4'))//1992年, 90年
  327. return true;
  328. if(IsAllNum((unsigned char *)sNum)&&(nLen>=6||nLen==4&&CC_Find("５６７８９",sTemp)))
  329. return true;
  330. if(GetCharCount("零○一二三四五六七八九壹贰叁肆伍陆柒捌玖",sNum)==(int)nLen/2&&nLen>=3)
  331. return true;
  332. if(nLen==8&&GetCharCount("千仟零○",sNum)==2)//二仟零二年
  333. return true;
  334. if(nLen==2&&GetCharCount("千仟",sNum)==1)
  335. return true;
  336. if(nLen==4&&GetCharCount("甲乙丙丁戊己庚辛壬癸",sNum)==1&&GetCharCount("子丑寅卯辰巳午未申酉戌亥",sNum+2)==1)
  337. return true;
  338. return false;
  339. }
  341. //CDynamicArray &aWord: the words array
  342. //CDynamicArray &aWordBinaryNet:the net between words
  343. //double dSmoothingPara: the parameter of data smoothing
  344. //CDictionary &DictBinary: the binary dictionary
  345. //CDictionary &DictCore: the Core dictionary
  346. bool CSegment::BiGraphGenerate(CDynamicArray &aWord, CDynamicArray &aBinaryWordNet,double dSmoothingPara,CDictionary &DictBinary,CDictionary &DictCore)
  347. {
  348. PARRAY_CHAIN pTail,pCur,pNextWords;//Temp buffer
  349. unsigned int nWordIndex=0,nTwoWordsFreq=0,nCurWordIndex,nNextWordIndex;
  350. //nWordIndex: the index number of current word
  351. double dCurFreqency,dValue,dTemp;
  352. char sTwoWords[WORD_MAXLENGTH];
  353. m_nWordCount=aWord.GetTail(&pTail);//Get tail element and return the words count
  354. if(m_npWordPosMapTable)
  355. {//free buffer
  356. delete [] m_npWordPosMapTable;
  357. m_npWordPosMapTable=0;
  358. }
  359. if(m_nWordCount>0)//Word count is greater than 0
  360. m_npWordPosMapTable=new int[m_nWordCount];//Record the  position of possible words
  361. pCur=aWord.GetHead();
  362. while(pCur!=NULL)//Set the position map of words
  363. {
  364. m_npWordPosMapTable[nWordIndex++]=pCur->row*MAX_SENTENCE_LEN+pCur->col;
  365. pCur=pCur->next;
  366. }
  368. pCur=aWord.GetHead();
  369. while(pCur!=NULL)//
  370. {
  371. if(pCur->nPOS>=0)//It's not an unknown words
  372. dCurFreqency=pCur->value;
  373. else//Unknown words
  374. dCurFreqency=DictCore.GetFrequency(pCur->sWord,2);
  375. aWord.GetElement(pCur->col,-1,pCur,&pNextWords);//Get next words which begin with pCur->col
  376. while(pNextWords&&pNextWords->row==pCur->col)//Next words
  377. {
  378. //Current words frequency
  379. strcpy(sTwoWords,pCur->sWord);
  380. strcat(sTwoWords,WORD_SEGMENTER);
  381. strcat(sTwoWords,pNextWords->sWord);
  382. nTwoWordsFreq=DictBinary.GetFrequency(sTwoWords,3);
  383. //Two linked Words frequency
  384. dTemp=(double)1/MAX_FREQUENCE;
  385. //Smoothing
  386. dValue=-log(dSmoothingPara*(1+dCurFreqency)/(MAX_FREQUENCE+80000)+(1-dSmoothingPara)*((1-dTemp)*nTwoWordsFreq/(1+dCurFreqency)+dTemp));
  387. //-log{a*P(Ci-1)+(1-a)P(Ci|Ci-1)} Note 0<a<1
  388. if(pCur->nPOS<0)//Unknown words: P(Wi|Ci);while known words:1
  389.     dValue+=pCur->value;
  391. //Get the position index of current word in the position map table
  392. nCurWordIndex=BinarySearch(pCur->row*MAX_SENTENCE_LEN+pCur->col,m_npWordPosMapTable,m_nWordCount);
  393. nNextWordIndex=BinarySearch(pNextWords->row*MAX_SENTENCE_LEN+pNextWords->col,m_npWordPosMapTable,m_nWordCount);
  394. aBinaryWordNet.SetElement(nCurWordIndex,nNextWordIndex,dValue,pCur->nPOS);
  395. pNextWords=pNextWords->next;//Get next word
  396. }
  397. pCur=pCur->next;
  398. }
  399. return true;
  400. }
  402. bool CSegment::BiSegment(char *sSentence, double dSmoothingPara, CDictionary &dictCore, CDictionary &dictBinary, unsigned int nResultCount)
  403. {
  404. int **nSegRoute;//The segmentation route
  405. nSegRoute=new int*[MAX_SEGMENT_NUM];
  406. unsigned int nLen=strlen(sSentence)+10;
  407. for(int i=0;i<MAX_SEGMENT_NUM;i++)
  408. {
  409. nSegRoute[i]=new int[nLen/2];
  410. memset(nSegRoute[i],-1,nLen/2*sizeof(int));
  411. }
  412.   m_graphSeg.GenerateWordNet(sSentence,dictCore,true);//Generate words array
  413.     CDynamicArray aBiwordsNet;
  414. BiGraphGenerate(m_graphSeg.m_segGraph,aBiwordsNet,dSmoothingPara,dictBinary,dictCore);
  415.     //Generate the biword link net
  416.     
  417. CNShortPath sp(&aBiwordsNet,nResultCount);
  418. sp.ShortPath();
  419. sp.Output(nSegRoute,false,&m_nSegmentCount);
  422. m_graphOptimum.SetEmpty();//Set graph optimum empty
  423. i=0;
  424. while(i<m_nSegmentCount)
  425. {
  426. BiPath2UniPath(nSegRoute[i]);
  427. //Path convert to unipath
  428. GenerateWord(nSegRoute,i);
  429. //Gernerate word according the Segmentation route
  430. i++;
  431. }
  433. //free the memory
  434. for(i=0;i<MAX_SEGMENT_NUM;i++)
  435. {
  436. delete [] nSegRoute[i];//free the pointer memory
  437. }
  438. delete [] nSegRoute;//free the pointer array
  440. return true;
  441. }
  443. bool CSegment::BiPath2UniPath(int *npPath)
  444. {//BiPath convert to unipath
  445. int i=0,nTemp=-1;
  446. if(!m_npWordPosMapTable)
  447. return false;
  448. while(npPath[i]!=-1&&npPath[i]<m_nWordCount)
  449. {
  450. nTemp=m_npWordPosMapTable[npPath[i]];
  451. npPath[i]=nTemp/MAX_SENTENCE_LEN;
  452. i++;
  453. }
  454. if(nTemp>0)
  455. npPath[i++]=nTemp%MAX_SENTENCE_LEN;
  456. npPath[i]=-1;
  457. return true;
  458. }
  460. bool CSegment::BiOptimumSegment(unsigned int nResultCount,double dSmoothingPara, CDictionary &dictBinary, CDictionary &dictCore)
  461. {
  462. int **nSegRoute;//The segmentation route
  463. nSegRoute=new int*[MAX_SEGMENT_NUM];
  464. for(int i=0;i<MAX_SEGMENT_NUM;i++)
  465. {
  466. nSegRoute[i]=new int[MAX_SENTENCE_LEN/2];
  467. memset(nSegRoute[i],-1,MAX_SENTENCE_LEN/2*sizeof(int));
  468. }
  469.     CDynamicArray aBiwordsNet;
  470. BiGraphGenerate(m_graphOptimum,aBiwordsNet,dSmoothingPara,dictBinary,dictCore);
  471.     //Generate the biword link net
  472.     
  473. CNShortPath sp(&aBiwordsNet,nResultCount);
  474. sp.ShortPath();
  475. sp.Output((int **)nSegRoute,false,&m_nSegmentCount);
  476. i=0;
  477. m_graphSeg.m_segGraph=m_graphOptimum;
  478. m_graphOptimum.SetEmpty();//Set graph optimum empty
  480. while(i<m_nSegmentCount)
  481. {
  482. BiPath2UniPath(nSegRoute[i]);
  483. //Path convert to unipath
  484. GenerateWord(nSegRoute,i);
  485. //Gernerate word according the Segmentation route
  486. i++;
  487. }
  489. //free the memory
  490. for(i=0;i<MAX_SEGMENT_NUM;i++)
  491. {
  492. delete [] nSegRoute[i];//free the pointer memory
  493. }
  494. delete [] nSegRoute;//free the pointer array
  495. return true;
  496. }