基于哈希表的词频统计.doc

本例可执行文件下载:下载本案例知识要点l链表的使用l文件操作l哈希表的使用l快速排序法l类的设计和使用一、案例需求1案例描述词频统计就是统计一个句子或一篇文章中各种词出现的频率，它是中文信息处理的一项基本技术，在很多领域都有重要的应用。比如在中文搜索引擎（如：google，baidu）中，除去特别常用的词，一篇文章中出现频率较高的词通常能反映这篇文章的主题，因此可以使用词频来对中文文章进行文本聚类。本案例实现按词表对文章中的词语进行分析，并按字典序给出词表中各词语在文章中出现的频数。2案例效果图（1）案例需要一个待统计文本文件，效果图如图20-3、20-4所示。图20-1待统计文本文件内容（2）本案例需一个词表文件，效果图如图20-2所示。图20-2词表文件内容（3）本案例最终统计出每个词在文本中出现的次数。运行结果如图20-3所示。图20-3运行结果（3）本案例最终统计出的结果保存在out.txt中。效果图如图20-4所示。图20-4运行结果文件内容3功能说明（1）本案例需要一个文本和一个词表，统计出每个词在文本中出现的次数。统计的原则包括以下两种：l交集型：如“内存在涨价”，需要统计“内存”和“存在”（假设这两个词都在词表中）。l组合型：如“中美关系在发展”，需要统计“中美”、“关系”和“中美关系”（假设这三个词都在词表中）。（2）文本和词表的格式是：输入文本是一个长句，句中只包含汉字，不包含数字、标点、空格、回车以及其它任何特殊符号。文本规模小于等于50，000汉字。输入词表的规模小于等于100，000个词，所有词不重复，词在27个汉字之间，每个词占一行。（3）实现基于词表的词频统计，从磁盘中读取词表和文本，将词频统计结果输出到磁盘中，输出结果要求按字典序排序，并计算出程序运行时间。二、案例分析首先分析选取哪种数据结构，以达到高速搜索的目的。具备搜索功能的数据结构很多，如线性表、平衡树、哈希表等，当数据量庞大时，使用哈希表最合适。哈希表的概念在案例“哈希表的演示”已经做了介绍。根据需要构造一个哈希表类，在类中实现如下操作：l建立哈希表将词表在内存中存储起来，这个存储的过程就是类的构造函数。案例中的词表是数量较大的词组，词与词之间用空格隔开。因此可用文件流函数getline来实现。每次调用getline函数便得到一个存有词的字符串，然后将字符串按照某种散列函数插入到哈希表中，一直到词表全部存储为止。l统计词频：从词表中读取文本文件，存储在一个字符串里，因为每个汉字存储在两个字节里，所以词在414个字节之间，用char word15即可表示一个词。考虑到词频统计的交集性和组合性原则，可对在文本字符串中的每个汉字与其后的汉字分别组成27个汉字的词，在词表中进行搜索，每被搜到一次，次数加1。循环直到文本末尾。l哈希函数（散列函数）的实现：用char word15存储的词得到一个关键字，然后除以某个素数，得到的余数为散列地址。由于数据较多，要高速完成搜索，散列到每个相同地址的元素要尽量少，因此素数要很大，关键字的范围也很大且不重叠。l按字符的字典序排序输出：而哈希表是乱序存储的，故可先遍历哈希表，将所有词频大于0的词存入数组中，用快速排序法将这个数组中的元素排序。三、案例设计1类的设计根据案例分析，需要设计出两个结构体NODE和TABLE，同时还需设计一个类SYMBOLTABLE。其中：结构体NODE是哈希桶（哈希桶-哈希表中各个同地址值的元素构成的链表）中节点的数据结构，TABLE是哈希表的结构，SYMBOLTABLE类提供了诸如：哈希函数、查找词汇、遍历哈希表、将词汇插入哈希表中、快速排序等功能。（1）结构体NODEstruct NODE char word15;/关键字 int number; /关键字被访问的次数 PNODE next;/指向下一结点的指针;（2）结构体TABLEstruct TABLE int prime;/哈希桶数 PNODE * buckets;/指向结点指针的指针，可构成动态的指针数组;（3）SYMBOLTABLE类图20-5SYMBOLTABLE类图l数据成员PSYMBOLTABLE p;哈希符号表指针。int num;被遍历的词数。l函数成员SYMBOLTABLE(char *argv);构造函数、创建哈希表。SYMBOLTABLE()析构函数。int Hash(char* word);静态哈希函数，形参：字符串，桶数。返回桶的下标。void FindNode(char* s);形参：结点指针，字符串。在某一链中找到某词汇，若找到则词频数加1，且返回。 void InsertIntoSymTbl(char name20);将词汇插入哈希表中。void SearchInSymTbl(char* argv);搜索某一词汇。void TraverseSymTbl(char* argv);遍历哈希表。void Qsort(PNODE* p,int s,int t);使用快速排序法。2主程序设计在主函数中声明了一个SYMBOLTABLE类的对象，依次调用哈希表类的构造函数、统计函数、输出函数即可。另外，为了记录程序的运行时间，包含了time头文件，调用clock函数，能精确到毫秒。主程序有详细的注释，清晰易懂，流程图略。四、案例实现/ */ * source.h类声明头文件 / *#1#ifndef _SUPERMARKET_ /防止头文件被多次包含#2#include#3#include#4typedef struct TABLE* PSYMBOLTABLE;/符号表构造函数，哈希符号表指针#5typedef struct NODE* PNODE; /结点指针#6struct NODE#7#8 char word15; /关键字#9int number; /此词被访问的次数#10 PNODE next; /指向下一结点的指针#11;#12struct TABLE#13#14 int prime; /哈希桶数#15 PNODE * buckets; /指向结点指针的指针，可构成动态的指针数组#16;#17class SYMBOLTABLE#18#19public:#20SYMBOLTABLE(char *argv); /创建哈希表#21SYMBOLTABLE()#22int Hash(char* word); /静态哈希函数，形参：字符串，桶数/返回桶的下标#23 void FindNode(char* s); /形参：结点指针，字符串 /功能:在某一链中找到某词汇，若找到则词频数加1，且返回；#24 void InsertIntoSymTbl(char name20); /将词表插入哈希表中#25 void SearchInSymTbl(char* argv); /搜索某一词汇#26 void TraverseSymTbl(char* argv); /遍历哈希表#27 void Qsort(PNODE* p,int s,int t); /使用快速排序法#28private:#29PSYMBOLTABLE p; /哈希符号表指针#30int num; /被遍历的词数#31;#32SYMBOLTABLE:SYMBOLTABLE(char* argv) /创建哈希表#33#34 ifstream in(argv);#35 int i,n;#36 char s15;#37 p=new struct TABLE; /建立哈希表#38 p-prime=100000; /桶数#39 num=0;#40 p-buckets=new PNODEp-prime; /建立每个散列链#41#42 for(i=0;iprime;i+) /动态分布内存#43 p-bucketsi=NULL;#44 for(i=0;inumber=0;#66 strcpy(t-word,word); /复制word的内容#67 t-next=p-bucketsn; /形成链表#68 p-bucketsn=t;#69#70void SYMBOLTABLE:SearchInSymTbl(char* argv) /在文本中搜索词汇#71#72 ifstream text(argv);#73 char story100002;#74text.getline(story,100002,n); /从文件中读出长句子#75 int m;#76 m=strlen(story); /求得句子的长度#77 storym=0;#78 int i,j;#79 char s15;#80 for(i=0;im;i+=2)#81 #82 s0=storyi;#83 s1=storyi+1; /第一个字#84 for(j=2;j=12&i+jm;j+=2) /每增加一个字则在词表中搜一次#85 /最多增加到七个字的词#86 sj=storyi+j;#87 sj+1=storyi+j+1;#88 sj+2=0; /以0为结尾符#89 FindNode(s);#90 #91 #92#93void SYMBOLTABLE:TraverseSymTbl(char* argv) /遍历哈希表#94#95 ofstream out(argv);#96 outnum; /输出总的词数#97 if(num=0) /若为0，直接结束#98 return;#99 int i;#100 PNODE verb100001; /最多10万词，还有一个岗哨#101 for(i=0;inum+1;i+)#102 verbi=new struct NODE; /有num个词，再加上一个哨岗#103 int j=0;#104 PNODE u;#105 for(i=0;iprime);i+)#106 #107 u=p-bucketsi;#108 while(u!=NULL)#109 #110 if(u-number0) /遍历哈希表，从中找出词频大于0的词，并装入数组中#111 #112 verbj=u;#113 j+;#114 #115 u=u-next;#116 #117 #118 strcpy(verbj-word,abc);/当作快速排序中的边缘，所有汉字组成的词都大于英文#119 Qsort(verb,0,j-1);#120 for(i=num-1;i=0;i-) /倒着从小到大遍历#121 outendlword number;#122#123int SYMBOLTABLE:Hash(char* word) /哈希函数，求散列地址#124#125 unsigned long s=1,t=1,r=1,m=1;#126 int i;#127 for(i=0;i4;i+)#128 s*=wordi;#129 while(wordi!=0&i8)#130 #131 t*=wordi;#132 i+;#133 #134 while(wordi!=0&iprime);#145#146void SYMBOLTABLE:FindNode(char* s) /在某一散列链中搜索结点位置#147#148 int n;#149 PNODE current;#150 n=Hash(s); /调用Hash函数，求得散列地址#151 current=p-bucketsn;#152 while(current!=NULL) /循环查找该结点#153 #154 if(strcmp(current-word,s)=0)/如果找到词，且为第一次找到，num加一#155 #156 if(current-number)=0)#157 num+;#158 current-number+;#159 return;#160 #161 current=current-next;#162 #163#164#165void SYMBOLTABLE:Qsort(PNODE* p,int s,int t)/快速排序法,从大到小排列#166#167 int i=s,j=t+1;#168 PNODE x=ps;#169 do#170 do i+;while(strcmp(pi-word,x-word)0); /从大到小排#171 do j-;while(strcmp(pj-word,x-word)0); /从大到小排#172 if(ij)#173 #174 PNODE temp=pi;#175 pi=pj;#176 pj=temp;#177 #178 while(ij);#179 ps=pj;#180 pj=x;#181 if(sj-1)#182 Qsort(p,s,j-1);#183 if(j+1t)#184 Qsort(p,j+1,t);#185/ */ * tongji.cpp系统主文件 / *#1#include#2#includesource.h /用包含命令将类定义头文件包含进来#3#includetime.h#4void main()#5#6 clock_t start,end;#7 start=clock();#8 SYMBOLTABLE st(dict.txt); /创建哈希表，读入词表#9 st.SearchInSymTbl(example.txt)； /读入目标文本，在哈希表中搜索#10 st.TraverseSymTbl(out.txt); /输出字典序的词表及频率#11 end=clock();#12 cout程序运行运行完毕!结果在out.txt中,用时en