设为首页收藏本站

Scripts 学盟

 找回密码
 加入学盟

QQ登录

只需一步,快速开始

查看: 2588|回复: 5

ICTCLAS 分词系统研究2 - 词典结构 [复制链接]

管理员

超级大菜鸟

Rank: 9Rank: 9Rank: 9

混混@普宁.中国 实名认证  发表于 2011-9-14 23:15:11 |显示全部楼层
ICTCLAS的词典结构是理解分词的重要依据,通过这么一个数据结构设计合理访问速度高效的词典才能达到快速准备的分词的目的。

通过阅读和分析源代码,我们可以知道,是程序运行初,先把词典加载到内存中,以提高访问的速度。源代码在Result.cpp的构造函数CResult() 内实现了词典和分词规则库的加载。如下代码所示:
  1. CResult::CResult()
  2. {
  3.         ……
  4.         m_dictCore.Load("data//coreDict.dct");
  5.         m_POSTagger.LoadContext("data//lexical.ctx");
  6.         ……
  7. }
复制代码
我们再跳进Load方法具体分析它是怎样读取数据词典的,看Load的源代码:
  1. bool CDictionary::Load(char *sFilename,bool bReset)
  2. {
  3.         FILE *fp;
  4.         int i,j,nBuffer[3];

  5.         //首先判断词典文件能否以二进制读取的方式打开
  6.         if((fp=fopen(sFilename,"rb"))==NULL)
  7.                 return false;//fail while opening the file
  8.    
  9.         //为新文件释放内存空间
  10.         for( i=0;i<CC_NUM;i++)
  11.         {        //delete the memory of word item array in the dictionary
  12.                 for( j=0;j<m_IndexTable[i].nCount;j++)
  13.                         delete m_IndexTable[i].pWordItemHead[j].sWord;
  14.                 delete [] m_IndexTable[i].pWordItemHead;
  15.         }
  16.         DelModified();//删除掉修改过的,可以先不管它

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

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

  30.                 //根据前面读到的词块数目,循环读取一个个词块
  31.                 while(j<m_IndexTable[i].nCount)
  32.                 {

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

  36.                         //读取词内容
  37.                         if(nBuffer[1])//String length is more than 0
  38.                         {
  39.                                 fread(m_IndexTable[i].pWordItemHead[j].sWord,sizeof(char),nBuffer[1],fp);
  40.                         }
  41.                         m_IndexTable[i].pWordItemHead[j].sWord[nBuffer[1]]=0;
  42.                         if(bReset)//Reset the frequency
  43.                                 m_IndexTable[i].pWordItemHead[j].nFrequency=0;
  44.                         else
  45.                                 m_IndexTable[i].pWordItemHead[j].nFrequency=nBuffer[0];
  46.                         m_IndexTable[i].pWordItemHead[j].nWordLen=nBuffer[1];
  47.                         m_IndexTable[i].pWordItemHead[j].nHandle=nBuffer[2];
  48.                         j+=1;//Get next item in the original table.
  49.                 }
  50.         }
  51.         fclose(fp);
  52.         return true;
  53. }
复制代码
看完上面的源代码,词典的结构也应该基本清楚了,如下图一所示:

1.png


修改表的数据结构和上图差不多,但是在词块数目后面多了一个nDelete数目,即删除的数目,数据结构如下图二所示:

2.png


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:(鼬)獾

-----------------------

对修改后如何保存的源代码进行分析:
  1. bool CDictionary::Save(char * sFilename) {
  2.         FILE * fp;
  3.         int i, j, nCount, nBuffer[3];
  4.         PWORD_CHAIN pCur;
  5.         if ((fp = fopen(sFilename, "wb")) == NULL) return false; //fail while opening the file
  6.         //对图一中所示的6768个数据块进行遍历
  7.         for (i = 0; i < CC_NUM; i++) {
  8.                 pCur = NULL;
  9.                 if (m_pModifyTable) {

  10.                         //计算修改后有效词块的数目
  11.                         nCount = m_IndexTable[i].nCount + m_pModifyTable[i].nCount - m_pModifyTable[i].nDelete;
  12.                         fwrite( & nCount, sizeof(int), 1, fp);
  13.                         pCur = m_pModifyTable[i].pWordItemHead;
  14.                         j = 0;

  15.                         //对原表中的词块和修改表中的词块进行遍历,并把修改后的添加到原表中
  16.                         while (pCur != NULL && j < m_IndexTable[i].nCount) {

  17.                                 //如果修改表中的词长度小于原表中对应位置的词的长度或者长度相等但nHandle值比原表中的小,则把修改表中的写入到词典文件当中.
  18.                                 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 modified data to the file
  19.                                         nBuffer[0] = pCur->data.nFrequency;
  20.                                         nBuffer[1] = pCur->data.nWordLen;
  21.                                         nBuffer[2] = pCur->data.nHandle;
  22.                                         fwrite(nBuffer, sizeof(int), 3, fp);
  23.                                         if (nBuffer[1]) //String length is more than 0
  24.                                         fwrite(pCur->data.sWord, sizeof(char), nBuffer[1], fp);
  25.                                         pCur = pCur->next; //Get next item in the modify table.
  26.                                 }

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

  31.                                 //如果修改表中的词长度比原表中的长度大或  长度相等但句柄值要多,就把原表的词写入的词典文件中
  32.                                 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
  33.                                         nBuffer[0] = m_IndexTable[i].pWordItemHead[j].nFrequency;
  34.                                         nBuffer[1] = m_IndexTable[i].pWordItemHead[j].nWordLen;
  35.                                         nBuffer[2] = m_IndexTable[i].pWordItemHead[j].nHandle;
  36.                                         fwrite(nBuffer, sizeof(int), 3, fp);
  37.                                         if (nBuffer[1]) //String length is more than 0
  38.                                         fwrite(m_IndexTable[i].pWordItemHead[j].sWord, sizeof(char), nBuffer[1], fp);
  39.                                         j += 1; //Get next item in the original table.
  40.                                 }
  41.                         }

  42.                         //把原表中剩余的词写入的词典文件当中
  43.                         if (j < m_IndexTable[i].nCount) {
  44.                                 while (j < m_IndexTable[i].nCount) {
  45.                                         if (m_IndexTable[i].pWordItemHead[j].nFrequency != -1) { //Has been deleted
  46.                                                 nBuffer[0] = m_IndexTable[i].pWordItemHead[j].nFrequency;
  47.                                                 nBuffer[1] = m_IndexTable[i].pWordItemHead[j].nWordLen;
  48.                                                 nBuffer[2] = m_IndexTable[i].pWordItemHead[j].nHandle;
  49.                                                 fwrite(nBuffer, sizeof(int), 3, fp);
  50.                                                 if (nBuffer[1]) //String length is more than 0
  51.                                                 fwrite(m_IndexTable[i].pWordItemHead[j].sWord, sizeof(char), nBuffer[1], fp);
  52.                                         }
  53.                                         j += 1; //Get next item in the original table.
  54.                                 }
  55.                         } else ////原表已到尾部但修改表还没有遍历完,把修改表中剩余的词写入到词典文件当中
  56.                         while (pCur != NULL) //Add the rest data to the file.
  57.                         {
  58.                                 nBuffer[0] = pCur->data.nFrequency;
  59.                                 nBuffer[1] = pCur->data.nWordLen;
  60.                                 nBuffer[2] = pCur->data.nHandle;
  61.                                 fwrite(nBuffer, sizeof(int), 3, fp);
  62.                                 if (nBuffer[1]) //String length is more than 0
  63.                                 fwrite(pCur->data.sWord, sizeof(char), nBuffer[1], fp);
  64.                                 pCur = pCur->next; //Get next item in the modify table.
  65.                         }
  66.                 }

  67.                 //不是修改标记,则把原表的数据全部写入到词典文件当中
  68.                 else {
  69.                         fwrite( & m_IndexTable[i].nCount, sizeof(int), 1, fp);
  70.                         //write to the file
  71.                         j = 0;
  72.                         while (j < m_IndexTable[i].nCount) {
  73.                                 nBuffer[0] = m_IndexTable[i].pWordItemHead[j].nFrequency;
  74.                                 nBuffer[1] = m_IndexTable[i].pWordItemHead[j].nWordLen;
  75.                                 nBuffer[2] = m_IndexTable[i].pWordItemHead[j].nHandle;
  76.                                 fwrite(nBuffer, sizeof(int), 3, fp);
  77.                                 if (nBuffer[1]) //String length is more than 0
  78.                                 fwrite(m_IndexTable[i].pWordItemHead[j].sWord, sizeof(char), nBuffer[1], fp);
  79.                                 j += 1; //Get next item in the original table.
  80.                         }
  81.                 }
  82.         }
  83.         fclose(fp);
  84.         return true;
  85. }
复制代码
增加一个词条目:
  1. bool CDictionary::AddItem(char * sWord, int nHandle, int nFrequency) {

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

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

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

  22.         //如果修改表为空,为它初始化空间
  23.         if (!m_pModifyTable) //Not prepare the buffer
  24.         {
  25.                 m_pModifyTable = new MODIFY_TABLE[CC_NUM];
  26.                 memset(m_pModifyTable, 0, CC_NUM * sizeof(MODIFY_TABLE));
  27.         }

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

  35.         //如果没有在修改表中找到,则添加进去
  36.         pTemp = new WORD_CHAIN; //Allocate the word chain node
  37.         if (pTemp == NULL) //Allocate memory failure
  38.         return false;
  39.         memset(pTemp, 0, sizeof(WORD_CHAIN)); //init it with 0
  40.         pTemp->data.nHandle = nHandle; //store the handle
  41.         pTemp->data.nWordLen = strlen(sWordAdd);
  42.         pTemp->data.sWord = new char[1 + pTemp->data.nWordLen];
  43.         strcpy(pTemp->data.sWord, sWordAdd);
  44.         pTemp->data.nFrequency = nFrequency;
  45.         pTemp->next = NULL;

  46.         //插入到修改表中
  47.         if (pRet != NULL) {
  48.                 pNext = pRet->next; //Get the next item before the current item
  49.                 pRet->next = pTemp; //link the node to the chain
  50.         } else {
  51.                 pNext = m_pModifyTable[nPos].pWordItemHead;
  52.                 m_pModifyTable[nPos].pWordItemHead = pTemp; //Set the pAdd as the head node
  53.         }
  54.         pTemp->next = pNext; //Very important!!!! or else it will lose some node
  55.         //把词块数目加一
  56.         m_pModifyTable[nPos].nCount++; //the number increase by one
  57.         return true;
  58. }
复制代码
删除修改过的词条
  1. bool CDictionary::DelModified() {
  2.         PWORD_CHAIN pTemp, pCur;
  3.         if (!m_pModifyTable) return true;

  4.         for (int i = 0; i < CC_NUM; i++) {
  5.                 pCur = m_pModifyTable[i].pWordItemHead;

  6.                 //删除链表上的节点
  7.                 while (pCur != NULL) {
  8.                         pTemp = pCur;
  9.                         pCur = pCur->next;
  10.                         delete pTemp->data.sWord;
  11.                         delete pTemp;
  12.                 }
  13.         }
  14.         delete[] m_pModifyTable;
  15.         m_pModifyTable = NULL;
  16.         return true;
  17. }

  18. //采用二分法进行查找
  19. bool CDictionary::FindInOriginalTable(int nInnerCode, char * sWord, int nHandle, int * nPosRet) {
  20.         PWORD_ITEM pItems = m_IndexTable[nInnerCode].pWordItemHead;
  21.         int nStart = 0,
  22.         nEnd = m_IndexTable[nInnerCode].nCount - 1,
  23.         nMid = (nStart + nEnd) / 2,
  24.         nCount = 0,
  25.         nCmpValue;
  26.         while (nStart <= nEnd) //Binary search
  27.         {
  28.                 nCmpValue = strcmp(pItems[nMid].sWord, sWord);

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

  35.                                         //Get the first item which match the current word
  36.                                         while (nMid >= 0 && strcmp(pItems[nMid].sWord, sWord) == 0) nMid--;
  37.                                         if (nMid < 0 || strcmp(pItems[nMid].sWord, sWord) != 0) nMid++;
  38.                                 } * nPosRet = nMid;
  39.                                 return true;
  40.                         }
  41.                         if (nPosRet) * nPosRet = nMid;
  42.                         return true; //find it
  43.                 } else if (nCmpValue < 0 || (nCmpValue == 0 && pItems[nMid].nHandle < nHandle && nHandle != -1)) {
  44.                         nStart = nMid + 1;
  45.                 } else if (nCmpValue > 0 || (nCmpValue == 0 && pItems[nMid].nHandle > nHandle && nHandle != -1)) {
  46.                         nEnd = nMid - 1;
  47.                 }
  48.                 nMid = (nStart + nEnd) / 2;
  49.         }
  50.         if (nPosRet) {
  51.                 //Get the previous position
  52.                 * nPosRet = nMid - 1;
  53.         }
  54.         return false;
  55. }

  56. //在修改表中查询
  57. bool CDictionary::FindInModifyTable(int nInnerCode, char * sWord, int nHandle, PWORD_CHAIN * pFindRet) {
  58.         PWORD_CHAIN pCur, pPre;
  59.         if (m_pModifyTable == NULL) //empty
  60.                 return false;
  61.         pCur = m_pModifyTable[nInnerCode].pWordItemHead;
  62.         pPre = NULL;

  63.         //sWord相等且句柄(nHandle)相等
  64.         while (pCur != NULL && (_stricmp(pCur->data.sWord, sWord) < 0 || (_stricmp(pCur->data.sWord, sWord) == 0 && pCur->data.nHandle < nHandle)))
  65.         //sort the link chain as alphabet
  66.         {
  67.                 pPre = pCur;
  68.                 pCur = pCur->next;
  69.         }
  70.         if (pFindRet) * pFindRet = pPre;
  71.         if (pCur != NULL && _stricmp(pCur->data.sWord, sWord) == 0 && (pCur->data.nHandle == nHandle || nHandle < 0)) { //The node exists, delete the node and return
  72.                 return true;
  73.         }
  74.         return false;
  75. }
复制代码
得到词的类型,共三种汉字、分隔符和其他
  1. int CDictionary::GetWordType(char * sWord) {
  2.         int nType = charType((unsigned char * ) sWord),
  3.         nLen = strlen(sWord);
  4.         if (nLen > 0 && nType == CT_CHINESE && IsAllChinese((unsigned char * ) sWord)) return WT_CHINESE; //Chinese word
  5.         else if (nLen > 0 && nType == CT_DELIMITER) return WT_DELIMITER; //Delimiter
  6.         else return WT_OTHER; //other invalid
  7. }
复制代码

相关帖子

Rank: 7Rank: 7Rank: 7

俊俊 实名认证  发表于 2011-9-16 15:02:09 |显示全部楼层
纯粹看不懂~~~

使用道具 举报

管理员

超级大菜鸟

Rank: 9Rank: 9Rank: 9

混混@普宁.中国 实名认证  发表于 2011-9-16 18:20:12 |显示全部楼层
代码不去看懂, 知道有那么个词库放一堆词哩好,哈哈

使用道具 举报

Rank: 8Rank: 8

那个谁 发表于 2011-9-16 18:31:07 |显示全部楼层
没劲!!!!!!!!!!!!!!!!!!!!!

使用道具 举报

Rank: 8Rank: 8

那个谁 发表于 2012-2-16 09:08:05 |显示全部楼层
混混大牛! C++都会了。。。

使用道具 举报

管理员

超级大菜鸟

Rank: 9Rank: 9Rank: 9

混混@普宁.中国 实名认证  发表于 2012-2-17 15:30:00 |显示全部楼层
看就看看, 写就写不了

使用道具 举报

您需要登录后才可以回帖 登录 | 加入学盟

手机版|Scripts 学盟   |

GMT+8, 2024-7-17 21:27 , Processed in 1.108707 second(s), 17 queries .

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部