百度之星 2005年 初赛题目四

第四题（共四题 100 分）：低频词过滤（ 40 分）

题目描述：请编写程序，从包含大量单词的文本中删除出现次数最少的单词。如果有多
个单词都出现最少的次数，则将这些单词都删除。

输入数据：程序读入已被命名为 corpus.txt 的一个大数据量的文本文件，该文件包含英
文单词和中文单词，词与词之间以一个或多个 whitespace 分隔。（为便于调试，您可下载
测试 corpus.txt 文件，实际运行时我们会使用不同内容的输入文件。）

输出数据：在标准输出上打印删除了 corpus.txt 中出现次数最少的单词之后的文本（
词与词保持原来的顺序，仍以空格分隔）。

评分标准：程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。

 

思路：因为词汇的频率是一个未知数，在统计的过程中无法探知到哪些多哪些少，必须把所有的词汇进行统计才能统计出哪些词汇词频最低。故1、构造Hash表，对出现的词汇进行统计，统计词频。2、然后获取到词频最低的列表。3、对原文进行处理，剔除低频词汇。

 

 

GHash.h

#ifndef __GHASH_H_
#define __GHASH_H_
#include "GList.h"
#define HASHSIZE 512
typedef struct _Item
{
   char * key;
   char * value;
   unsigned int count;
   struct Item * next;
} Item;

void GHashInit();
Item *  HashInSert(char * key,char * value);
Item *  HashSearch(char * key);
int  HashIncrease(char * key);
int  HashRemove(char * key);
void GetMinList(List* glist);
void FreeGHash();
void PrintGHash();

#endif

 

GHash.c

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "GHash.h"
#include "4lib.h"
//#include "GList.h"
static struct Item *hashtab[HASHSIZE];

static void freeItem(Item * item);
static unsigned int _Hash(char *key);
static unsigned int _ELFHash(char *str);

void GHashInit()
{
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	  	hashtab[i]=NULL;
     }
}

Item *  HashInSert(char * key,char * value)
{
 	 Item * np;
 	 unsigned int hashval;
 	 if((np=HashSearch(key))==NULL)
 	 {
         np=(Item *)malloc(sizeof(Item));
         if(NULL==np || NULL==(np->key = (char*)strdup(key))
		       || NULL ==(np->value = (char*)strdup(value)) )
         {
             return NULL;
         }
         hashval = _Hash(key);
         np->next = (struct Item *)hashtab[hashval];
         hashtab[hashval] = (struct Item *)np;
     }
     else
     {
	  	 free(np->value);
	  	 if((np->value=(char *)strdup(value))== NULL)
	  	 {
		    return NULL;
         }
 	 }
 	 return np;
}

Item *  HashSearch(char * key)
{
    Item  *np;

    for(np = (Item *)hashtab[_Hash(key)];
        np != NULL;
        np = np->next)
      if(strcmp(key,np->key) == 0)
           return np;
    return NULL;
}


int  HashIncrease(char * key)
{
 	 Item * np;
 	 unsigned int hashval;
 	 if((np=HashSearch(key))==NULL)
 	 {
         np=(Item *)malloc(sizeof(Item));
         if(NULL==np || NULL ==(np->key = (char *)strdup(key))
		    )
         {
             return -1;
         }
         hashval = _Hash(key);
         np->value=NULL;
         np->count=1;
         np->next = (struct Item *)hashtab[hashval];
         hashtab[hashval] = (struct Item *)np;
         return 1;
     }
     else
     {
	  	 np->count=np->count+1;
	  	 //free(np->value);
	  	 //if((np->value=strdup(value))== NULL)
	  	 //{
		 //   return NULL;
         //}
         return np->count;
 	 }
 	 return np->count;
}

int  HashRemove(char * key)
{
}



void GetMinList(List* glist)
{
 	 GListInit(glist);
 	 GListEmptyList(glist);
 	 int curmin=100;
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	     if(hashtab[i]!=NULL)
	     {
		    Item * tmp=hashtab[i];
		    while(tmp!=NULL)
		    {
			 	if(tmp->count==curmin)
			 	{
				 	GListAddNode(tmp->key,glist);		  
		        }
		        else if(tmp->count<curmin)
		        {
				 	 GListEmptyList(glist);
				 	 GListAddNode(tmp->key,glist);	
				 	 curmin=tmp->count;
	            }
	            tmp=tmp->next;
	        }
		 }
     }
}

void FreeGHash()
{
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	     if(hashtab[i]!=NULL)
	     {
		    Item * tmp;
		    Item * deln;
		    for(tmp=hashtab[i]; tmp!=NULL; tmp=hashtab[i])
		    {
			     hashtab[i]=(struct Item *)(tmp->next);
			     freeItem(tmp);
			}
		 }
     }
}
void PrintGHash()
{
 	 printf("Print Hash:\n");
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	     if(hashtab[i] !=NULL )
	     {
		    printf("%d---",i);
		    Item * tmp;
		    for(tmp=hashtab[i]; tmp!=NULL; tmp=tmp->next)
		    {
			     printf("%s:%s:%d;",tmp->key,tmp->value,tmp->count);
			}
			printf("\n");
		 }
     }
}

static unsigned int _Hash(char *key)
{
    return _ELFHash(key)%HASHSIZE;
}

// ELF Hash Function
static unsigned int _ELFHash(char *str)
{
       unsigned int hash = 0;
       unsigned int x = 0;

       while (*str)
      {
           hash = (hash << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash
           if ((x = hash & 0xF0000000L) != 0)
           {//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。

           //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位
           hash ^= (x >> 24);
           //清空28-31位。
           hash &= ~x;
           }
       }

      //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)
     return (hash & 0x7FFFFFFF);

}

static void freeItem(Item * item)
{
   free(item->key);
   free(item->value);
   free(item);
   item=NULL;
}

 

 

 GLish.h

 

#ifndef __GLIST_H_
#define __GLIST_H_
typedef struct _Node 
{
    char* data;
    struct _Node * next; 
} Node;
typedef struct _List
{
   int count; 
   Node * header;
} List;

void GListInit(List* glist);
void GListAddNode(char* data,List* glist);
void GListEmptyList(List * glist);
int GListGetCount(List* glist);
void GListPrint(List * glist);
#endif

 

 

   GLish.c

  

#include <stdio.h>
#include <stdlib.h>
#include "GList.h"
#include "4lib.h"
//static List glist ;
void GListInit(List* glist)
{
 	 glist->count=0;
 	 glist->header=NULL;
}
void GListAddNode(char* data,List* glist)
{
 	Node * node = (Node *)malloc(sizeof(Node));
 	//node->data=data;
 	node->data=(char *)strdup(data);
 	node->next=glist->header;
 	glist->header=node;
 	glist->count=glist->count+1;
}
int GetCount(List* glist)
{
 	return glist->count;
}
void FreeNode(Node * node)
{
 	 free(node->data);
 	 free(node);
 	 node=NULL;
}
void GListEmptyList(List * glist)
{
 	 Node* tmp;
 	 while(glist->header!=NULL)
 	 {
        tmp=glist->header;
        glist->header=tmp->next;
        //free(tmp);
        FreeNode(tmp);
     }
     glist->count=0;
     glist->header=NULL;
}

void GListPrint(List * glist)
{
 	 printf("GList:\n");
 	 Node* tmp=glist->header;
 	 while(tmp!=NULL)
 	 {
        printf("%s ",tmp->data);
        tmp=tmp->next;
     }
     printf("\n");
}

int GListSearch(char * data,List* glist)
{
 	Node* tmp=glist->header;
 	 while(tmp!=NULL)
 	 {
	    if(strcmp(data,tmp->data)==0)
     	    return TRUE;
	    else
            tmp=tmp->next;
     }
     return FALSE;
}

 

  4lib.h

 

#ifndef __4LIB_H_
#define __4LIB_H
#define TRUE 1
#define FALSE 0
char *strdup(const char *str);

#endif

4lib.c

char *strdup(const char *str)
{
    int n = strlen(str) + 1;
    char *dup = malloc(n);
    if(dup)
    {
        strcpy(dup, str);
    }
    return dup;
}

 

 

   main.c

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "GList.h"
#include "GHash.h"
#include "4lib.h"
#define INPUT "4.input.txt"
#define READBUFSIZE 513
#define FREADSIZE ((READBUFSIZE-1))
#define KEEPBUFSIZE (READBUFSIZE*2)
char keepbuf[KEEPBUFSIZE];
extern int  HashIncrease(char * key);
void HandlerItem(const char *item)
{
 	//printf(" %s\n",item);
 	HashIncrease(item);
}

void HanlderBuf(const char * buf)
{
 	 if (buf==NULL)
 	     return;
 	 strncat(keepbuf,buf,strlen(buf));
 	 char *split=" \t\n";
 	 char *tmp,*next;
 	 char *first=strtok(keepbuf,split);
 	 //HandlerItem(first,out);
 	 tmp=first;
 	 while(tmp)
 	 {
          next=strtok(NULL,split);
          if(next==NULL)//end of string
          {
	          strncpy(keepbuf,tmp,strlen(tmp));
	          keepbuf[strlen(tmp)]='\0';
	          break;
	      }
	      else
	      {
		   	  HandlerItem(tmp);
	   	  }
          tmp=next;
          
     }
}

void HandlerItemout(char *item,List * glist)
{
    if(GListSearch(item,glist)==FALSE)
		  printf(" %s ",item);
 	//HashIncrease(item);
}

void HanlderBufout(char * buf,List * glist)
{
 	 if (buf==NULL)
 	     return;
 	 strncat(keepbuf,buf,strlen(buf));
 	 char *split=" \t\n";
 	 char *tmp,*next;
 	 char *first=strtok(keepbuf,split);
 	 //HandlerItem(first,out);
 	 tmp=first;
 	 while(tmp)
 	 {
          next=strtok(NULL,split);
          if(next==NULL)//end of string
          {
	          strncpy(keepbuf,tmp,strlen(tmp));
	          keepbuf[strlen(tmp)]='\0';
	          break;
	      }
	      else
	      {
		   	  HandlerItemout(tmp,glist);
	   	  }
          tmp=next;
          
     }
}


int main(int argc, char *argv[])
{
  FILE * f=fopen(INPUT,"r+");
  if(NULL==f)
  {
	 perror("Open file:");
  }
  
  GHashInit();
  
  char readbuf[READBUFSIZE];
  memset(keepbuf,'\0',KEEPBUFSIZE);
  memset(readbuf,'\0',READBUFSIZE);
  int readnum;
  while((readnum=fread(readbuf,sizeof(char),FREADSIZE,f))>0)
  {
      readbuf[readnum]='\0';
      //printf("%d\n",readnum);
      if(readnum<FREADSIZE)
      {
	      if(feof(f)!=0)//end file
	      {
	         HanlderBuf(readbuf);
	         break;
	      }
          else
          {
		   	  perror("Error!");
	   	  }
	  }
	  else if(readnum==FREADSIZE)
	  {
	   	   HanlderBuf(readbuf);
      }
  }
  
  if(strlen(keepbuf)>0)
    HandlerItem(keepbuf);
  fclose(f);
  PrintGHash();

  List glist;
  GetMinList(&glist);
  printf("list count:%d\n",GetCount(&glist));
  GListPrint(&glist);
  
  FreeGHash();
  
  //hanlde the input
  f=fopen(INPUT,"r+");
  if(NULL==f)
  {
	 perror("Open file:");
  }
  memset(keepbuf,'\0',KEEPBUFSIZE);
  memset(readbuf,'\0',READBUFSIZE);
  readnum;
  while((readnum=fread(readbuf,sizeof(char),FREADSIZE,f))>0)
  {
      readbuf[readnum]='\0';
      //printf("%d\n",readnum);
      if(readnum<FREADSIZE)
      {
	      if(feof(f)!=0)//end file
	      {
	         HanlderBufout(readbuf,&glist);
	         break;
	      }
          else
          {
		   	  perror("Error!");
	   	  }
	  }
	  else if(readnum==FREADSIZE)
	  {
	   	   HanlderBufout(readbuf,&glist);
      }
  }
  
  if(strlen(keepbuf)>0)
    HandlerItemout(keepbuf,&glist);
  fclose(f);
  
  GListEmptyList(&glist);
  system("PAUSE");	
  return 0;
}

 

 

   该解决方案不包含的内容：

   1、 在对词汇进行统计的时，未记录词汇的位置，造成在提出低频词汇时需要再次比对，可以提升

   2、 仅适用于最低频的，无法针对词频范围。如果需要则可以修改为HashTable的冲突列表为顺序列表

   3、 无法获得每个低频词汇的出现的顺序

   4、 替换低频词汇效率不高