作业三 最大匹配分词法.doc

作业三 中文分词法 中文分词法：开始没有思路，后来查了下资料和问了下同学，才搞定的。我的思路： 这里说的是最大匹配分词法：首先准备一个分词词表input.txt作为输入，顺序扫描待分词的句子，将句中候选词按照词长从大到小的顺序依次跟词表cizu.txt文件中的词进行匹配，匹配成功即作为一个词输出。这样就使得每次输出的词是长度最大的（相比已知的确定的词表而言）。如果一个句中的多字候选词跟词表中所有的词都匹配不上，自然就只能把单字词当作分词结果输出了。把事先准备好的欲分词文件在目录d:outputinput.txt，那么我们开始执行程序显示之后再看文件夹d:output里面多了个output.txt的文件，这就是对input.txt做好的分词输出文件。程序的算法思想：首先对一篇文本按照标点符号等自身的分隔符分解成句子，然后对每个句子按照词长MAX_CWORD_LEN=18（9个汉字）的正向最大匹配法进行分词。在划分句子的时候，最关键的操作在确定字串在何处断开成为独立的句子。这里考虑了英文和中文混杂的情况。数据结构：使用二维的指针数组进行词典存储：词典中的每个词利用其第一个字节和最后一个字节进行二维定位来存储，有相同的第一个字节和最后一个字节的多个词串用指针进行相连。这种存储方式极大得提高了查词典的效率，在匹配词串时利用第一字节和最后一个字节直接定位或者通过几级指针快速检索。输入文本文件和输出文本文件都用一维数组进行存储，对空间的要求比较大，避免了多次文件的I/O操作。主要文件有测试文件input.txt，输出文件output.txt，这里还有一个字典，就是每个词后面都有可能出现的词语，比如：人名，人民，人生等ziguang.txt。实现的部分源程序如下：/不进行索引的单词char *arrayEnglishStop = a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, about, above, after, again, all, also, am, an, and, any, are, as, at, back, be, been, before, behind, being, below, but, by, can, click, do, does, done, each, else, etc, ever, every, few, for, from, generally, get, go, gone, has, have, hello, here, how, if, in, into, is, just, keep, later, let, like, lot, lots, made, make, makes, many, may, me, more, most, much, must, my, need, no, not, now, of, often, on, only, or, other, others, our, out, over, please, put, so, some, such, than, that, the, their, them, then, there, these, they, this, try, to, up, us, very, want, was, we, well, what, when, where, which, why, will, with, within, you, your, yourself;/词典索引时,字或词不需要索引char *arrayChineseStop = 的,吗,么,啊,说,对,在,和,是,被,最,所,那,这,有,将,会,与,於,于,他,她,它,您,为,欢迎;/标点符号及汉字的标点符号,注意 + - 这三个符号，因为在搜索的时候需要通过他们进行异或等条件判断char arrayAsciiSymbol =!,*,(,),-,_,+,=,:,;,.,?,/,|,#,$,%,&;/汉字词典typedef struct _WORD_NODEcharstrWordMAX_CWORD_LEN+1;/ todo ,可以增加 两个字，三个字，四个字，五个字的数组，这样查起来更快struct _WORD_NODE*nextWord;WORD_NODE; /定义结构体类型struct _CH_DICT WORD_NODE*lstWord;CH_DICTMAX_CDIMMAX_CDIM; /定义结构体二维数组变量：词典char SEG_LISTMAX_WORD; /定义数组存放分词后的句串int WNUM_IN = 0;int WNUM_OUT = 0;char *strTrim(char str) int firstchar=0; int endpos=0; int i; int firstpos=0; for(i=0;stri!=0;i+) if(stri= | stri = r | str i = n | str i=t) if(firstchar=0) firstpos+; else endpos=i; firstchar=1; for(i=firstpos;i=endpos;i+) stri-firstpos=stri; /去除待处理字符串中的空格、换行等 stri-firstpos=0; return str;int addDictWord(char *strWord , int len)unsigned char firstChar,lastChar;WORD_NODE* curLst;WORD_NODE* newWord ,*curTmp ;firstChar = strWord0 ;lastChar = strWordlen-1;if (firstChar 161 | lastChar strWord,strWord);newWord-nextWord = NULL;firstChar -= 161 ;lastChar -= 161 ; /按词串第一个字节和最后一个字节顺序来存词curLst = CH_DICTfirstCharlastChar.lstWord;if( curLst = NULL)/reinit list;CH_DICTfirstCharlastChar.lstWord = newWord ;return 0;curTmp = curLst ; /curLst对应位置上已经存词则顺着指针向后找while(curTmp - nextWord != NULL )curTmp = curTmp-nextWord;curTmp - nextWord = newWord ;return 0;void addSegWord(unsigned char *strWord , int len)const char *cstrWord = ( const char * ) ( char * ) strWord;strcat(SEG_LIST , cstrWord);strcat(SEG_LIST , |);WNUM_OUT = WNUM_OUT + len + 1;void freeDict()int i ,j ;WORD_NODE *curLst,*curTmp ,*tmp;for ( i = 0 ; i MAX_CDIM ; i + ) for ( j = 0 ; j nextWord ;free(tmp);tmp = ( WORD_NODE *)NULL;CH_DICTij.lstWord = (WORD_NODE *)NULL; int freeSeg()FILE *fpOut = NULL;fpOut = fopen(d:outputoutput.txt,w);if( fpOut=( FILE *)NULL)printf(output.txt cannot be createdn);return -1;fwrite ( SEG_LIST , WNUM_OUT , 1 , fpOut );memset ( SEG_LIST , 0x00 , sizeof ( SEG_LIST ) );fclose ( fpOut );return 0;BOOL searchWord( unsigned char *strWord,int len )WORD_NODE *curLst,*curTmp;unsigned char firstChar,lastChar;firstChar = strWord0 ;lastChar = strWordlen-1;firstChar -= 161 ;lastChar -= 161 ;curLst = CH_DICTfirstCharlastChar.lstWord;curTmp = curLst;while ( curTmp != NULL ) if ( strcmp(char *)strWord,curTmp-strWord) = 0)return TRUE;curTmp = curTmp - nextWord ;return FALSE;int segWord ( unsigned char *strText , int iWordLen , BOOL bChinese )int i = 0 ,j = 0 , k = 0 , l = 0 , temp=0;unsigned char strCharMAX_CWORD_LEN+1,strChar15,strChar25,strChar37;BOOLbFound = FALSE;i = iWordLen ; if ( FALSE = bChinese ) /英文/检查 是否在stop数组里addSegWord(strText,iWordLen);return 0;while ( i 1 ) /i表示取出的句子中还未匹配出来的字数for ( j = MAX_CWORD_LEN ; j = 2 ; j -=2 ) /最大词长个汉字if ( i j ) /句子的长度小于最大词长时，进入下次循环减小jcontinue; l = 0 ;for ( k=temp , l=0 ; k 0 return 0;void initSegList()int i ; for ( i = 0 ; i MAX_WORD ; i + ) SEG_LISTi=0;int loadDict(char *strFilename)int len = 0 , i ,j ;FILE *fpDict = NULL;unsigned char firstChar,lastChar;charsLine128; for ( i = 0 ; i MAX_CDIM ; i + ) for ( j = 0 ; j MAX_CDIM ; j + ) CH_DICTij.lstWord = (WORD_NODE *)NULL; fpDict = fopen(strFilename,r);if ( fpDict = ( FILE *)NULL ) printf(open dict file %s error !n,strFilename); return -1;while ( !feof(fpDict) fgets(sLine,128,fpDict);strTrim(sLine);len = strlen(sLine);if ( len MAX_CWORD_LEN )printf(%s error!n,sLine);addDictWord(sLine,len); fclose(fpDict); return 0;BOOL isEnglishStop(unsigned char *strWord)/arrayEnglishStopreturn FALSE ;inline BOOL isAsciiSymbol (char cChar)int i = 0 ;for ( i = 0 ; i sizeof(arrayAsciiSymbol) ; i + ) if ( cChar = arrayAsciiSymboli) return TRUE;return FALSE;int segSentence (char *strText ,BOOL bSpace ) int iTextLen = strlen(strText) ;int iWordLen= 0 ;inti= 0 ;intiNexti= 0 ;BOOLbSep = FALSE ;/是否是分隔符或者是一个词结束BOOLbChinese= FALSE ;/上一个有效字符类型，/false:英文 true: ChineseBOOLbFound= FALSE ;BOOL bSymbol= FALSE ;/是否是标点unsigned char strWordMAX_SWORD_LEN + 1; /当前词unsigned charstrChar3;/unsigned charcChar;/memset(strWord,0,sizeof(strWord);strChar0 = 0;for ( i = 0 ; i cChar) /英文字符/*连续空格不算分隔 */if ( = cChar | t = cChar | r = cChar | n = cChar )if ( TRUE = bChinese ) /如果前面一个有效字符是Chineseif ( TRUE = bSpace & ( = cChar | t = cChar) bSep = TRUE ;e