分词程序.cpp

实现中文分词

/*中文分词使用整数进行判断*/
/*在目录下的word.txt是中文词的文件*/
/*程序对同一目录下的article.txt进行分割*/
/*程序实现:第一个中文字用数组进行查找，之后进行森林的搜索*/
#include <stdio.h>
#include <malloc.h>
//#include <ctype.h>
#include <windows.h>
typedef struct Forest/*森林的结构*/
{ 
	long int value; 
	struct Forest *child,*sibling;
	int eof;/*中文词的标记*/
}Forest;
Forest *HashTable[65536]={NULL};/*第一个字的根结点用数组存储*/
Forest *search(Forest *root,int value)/*在此层进行文字的查找*/
{ 
	if(root==NULL) 
		return root;
	else 
	{ 
		root=root->child; 
		while(root&&(root->value!=value)) 
			root=root->sibling;
		return root;
	}
}
Forest *insert(Forest *root,int value)
{ 
	Forest *tmpcell,*tmp;
	if(root->child==NULL) 
	{ 
		tmpcell=(Forest*)malloc(sizeof(Forest));
		tmpcell->value=value; 
		tmpcell->child=NULL; 
		tmpcell->sibling=NULL; 
		tmpcell->eof=0; 
		root->child=tmpcell; 
		return tmpcell;
	}
	else 
	{ 
		tmp=root->child;
		while(tmp&&(tmp->value!=value)) 
		{ 
			root=tmp; 
			tmp=tmp->sibling; 
		} 
		if(tmp)return tmp;
		else 
		{ 
			tmpcell=(Forest*)malloc(sizeof(Forest));		
			tmpcell->value=value;
			tmpcell->child=NULL; 
			tmpcell->sibling=NULL;
			tmpcell->eof=0; 
			root->sibling=tmpcell;
			return tmpcell; 
		}
	}
}

void create()/*建立索引*//*结构很简单，但很难描述*/
/*中文字第一层用hash查找并找到根，后面用森林进行查找*/
{ 
	FILE *fp;
	int i;
	char filename[10]={0};/////////////////
	char sequence[4]={0};//////////////////
	unsigned char buffer[20]={0};
	long int value; 
	Forest *root,*tmpcell; 
	 
      fp=fopen("word.txt","r");
	  if(fp==NULL)
	  {
		  printf("词库文件找不到\n");
		  return ;	
	  }
	  while(!feof(fp)) 
	  { 
		  fscanf(fp,"%s\n",buffer); 
		  value=buffer[0];
		  value*=256; 
		  value+=buffer[1];
		  if(HashTable[value]==NULL) 
		  { 
			  tmpcell=(Forest*)malloc(sizeof(Forest));
			  tmpcell->value=value;
			  tmpcell->child=NULL; 
			  tmpcell->sibling=NULL;
			  tmpcell->eof=1; 
			  HashTable[value]=tmpcell; 
		  } 
		  root=HashTable[value];
		  for(i=2;i<=16;i+=2) 
		  { 
			  value=buffer[i]; 
			  value*=256; 
			  value+=buffer[i+1];
			  root=insert(root,value);
		  
		  root->eof=1;}
	  } 
	  fclose(fp);
  
}
void freeForest(Forest *root)/*递归释放森令各节点*/
{ 
	Forest *tmp;
	if(root==NULL) return ; 
	else 
	{
		tmp=root->sibling;
		freeForest(root->child);
		free(root); 
		freeForest(tmp);
	}
}
void freehash()/*释放hash和后面的根*/
{ 
	int i=0; 
	Forest *root; 
	  
	root=HashTable[i]; 
	freeForest(root); 
	
}
void fsplit(char *filename)
{ 
	int lasteof=0/*记录最后一个匹配的词*/,str_pos=0/*str的位置*/,value;
	unsigned char str[20]={0},ch[2]={0};
	Forest *root; 
	FILE *fp=fopen(filename,"r"); 
	printf("filename :%s\n",filename);
	if(fp==NULL)
	{ 
		printf("No file\n");
		return ; 
	}
	while(!feof(fp)) 
	{ 
		ch[0]=fgetc(fp); 
		if(ch[0]<128)/*非中文字符直接输出*/ /*并将前面匹配的中文词输出*/ 
		{ 
			str[str_pos]=0; 
			printf("%s",str);
			str_pos=0;
			putchar(ch[0]);
		} 
		else 
		{
			ch[1]=fgetc(fp);/*若非种文字符需要读两个字节*/
			value=ch[0];
			value*=256;
			value+=ch[1];
			if(str_pos==0) 
			{ 
				root=HashTable[value];
				str[str_pos++]=ch[0]; 
				str[str_pos++]=ch[1];
				lasteof=2; 
			}
			else 
			{ 
				root=search(root,value);
				if(root==NULL)/*没有匹配*/
				{ 
					str[lasteof]=0; 
					printf("[%s]",str);
					if(str_pos!=2)/*这部分很重要*/ /*根据str_pos和lasteof作适当的回退*/
					{ 
						if(str_pos==lasteof) 
							fseek(fp,-2,SEEK_CUR);
						else fseek(fp,-(str_pos-lasteof),SEEK_CUR); 
					}
					else
						fseek(fp,-2,SEEK_CUR);
					str_pos=0; 
				}
				else/*若匹配直接存储*/
				{
					str[str_pos++]=ch[0];
					str[str_pos++]=ch[1];
					if(root->eof==1)/*若是一个中文词，记录下最后的位置*/ 
						lasteof=str_pos;
				} 
			}
		} 
	} 
fclose(fp); 
return ;
}


int main()
{ 
	char *filename="article.txt";  
	create(); 
	fsplit(filename); 
	freehash(); 
	getchar(); 
	return 0;
}