untitled1.cpp

中文分词程序

/*中文分词使用整数进行判断*/
/**//*在目录下的word-.txt是中文词的文件*/
/**//*程序对同一目录下的split.txt进行分割*/
/**//*程序实现：
/*第一个中文字用数组进行查找，之后进行森林的搜索*/
#include <stdio.h>
#include <malloc.h>
#include <ctype.h>
#include <string.h>
#include <windows.h>
typedef struct Trie/**//*森林的结构*/
{
    long int value;
    struct Trie *child,*sibling;
    int eof;/**//*中文词的标记*/
}Trie;   
Trie *HashTable[65536]={NULL};/**//*第一个字的根结点用数组存储*/
Trie *search(Trie *root,int value)
/**//*在此层进行文字的查找*/
{
    if(root==NULL)
        return root;
    else
    {
        root=root->child;
        while(root&&(root->value!=value))
          root=root->sibling;
        return root;
    }
}
Trie *insert(Trie *root,int value)
{
    Trie *tmpcell,*tmp;
    if(root->child==NULL)
    {
        tmpcell=(Trie*)malloc(sizeof(Trie));
        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=(Trie*)malloc(sizeof(Trie));
            tmpcell->value=value;
            tmpcell->child=NULL;
            tmpcell->sibling=NULL;
            tmpcell->eof=0;
            root->sibling=tmpcell;
            return tmpcell;
        }
    }
}
void create()/**//*建立索引*/
/**//*结构很简单，但很难描述*/
/**//*中文字第一层用hash查找并找到根，后面用森林进行查找*/
{
    FILE *fp;
    int words=2,maxwords=20,i;
    char *filename="word.txt"; 
    //char filename[10]={0};
    char sequence[4]={0};
    unsigned char buffer[40]={0};
    long int value;
    Trie *root,*tmpcell;
    for(words=2;words<=maxwords;words+=2)
    {
        //strcpy(filename,"word");
        //itoa(words,sequence,10);
        //strcat(filename,sequence);
        //strcat(filename,".txt");/**//*构造词文件名*/
        fp=fopen(filename,"r");
        if(fp==NULL)
            continue;
        while(!feof(fp))
        {
            fscanf(fp,"%s ",buffer);
            value=buffer[0];
            value=value<<8;
            value+=buffer[1];
            if(HashTable[value]==NULL)
            {
                tmpcell=(Trie*)malloc(sizeof(Trie));
                tmpcell->value=value;
                tmpcell->child=NULL;
                tmpcell->sibling=NULL;
                tmpcell->eof=0;
                HashTable[value]=tmpcell;
            }
            root=HashTable[value];
            for(i=2;i<=words-2;i+=2)
            {
                value=buffer[i];
                value=value<<8;
                value+=buffer[i+1];
                root=insert(root,value);
            }
            root->eof=1;
        }
        fclose(fp);
    }
}
void freetrie(Trie *root)
/**//*递归释放森令各节点*/
{
    Trie *tmp;
    if(root==NULL)
        return ;
    else
    {
        tmp=root->sibling;
        freetrie(root->child);
        free(root);
        freetrie(tmp);
    }
}
void freehash()/**//*释放hash和后面的根*/
{
    int i;
    Trie *root;
    for(i=0;i<65536;i++)
    {    
        root=HashTable[i];
        if(root!=NULL)
            freetrie(root);
    }
}
void fsplit(char *filename)
{
    int lasteof=0/**//*记录最后一个匹配的词*/,str_pos=0/**//*str的位置*/,value;
    unsigned char str[20]={0},ch[2]={0};
    Trie *root;
    FILE *fp=fopen(filename,"r");
    
    if(fp==NULL)
    {
        printf("No file ");
        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=value<<8;
            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="split.txt"; 
    DWORD time[2];
    create();
    
    fsplit(filename);
    
    freehash();
    getchar();
    return 0;
}