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

基于哈希表的词频统计本例可执行文件下载: 下载 本案例知识要点 l 链表的使用 l 文件操作 l 哈希表的使用 l 快速排序法 l 类的设计和使用 一、案例需求 1案例描述 词频统计就是统计一个句子或一篇文章中各种词出现的频率，它是中文信息处理的一项基本技术，在很多领域都有重要的应用。比如在中文搜索引擎中，除去特别常用的词，一篇文章中出现频率较高的词通常能反映这篇文章的主题，因此可以使用词频来对中文文章进行文本聚类。本案例实现按词表对文章中的词语进行分析，并按字典序给出词表中各词语在文章中出现的频数。 2案例效果图 案例需要一个待统计文本文件，效果图如图20-3、20-4所示。 图20-1待统计文本文件内容 本案例需一个词表文件，效果图如图20-2所示。 图20-2词表文件内容 本案例最终统计出每个词在文本中出现的次数。运行结果如图20-3所示。 图20-3运行结果 本案例最终统计出的结果保存在out.txt中。效果图如图20-4所示。 图20-4运行结果文件内容 3功能说明 本案例需要一个文本和一个词表，统计出每个词在文本中出现的次数。统计的原则包括以下两种： l 交集型：如“内存在涨价”，需要统计“内存”和“存在”。 l 组合型：如“中美关系在发展”，需要统计“中美”、“关系”和“中美关系”。 文本和词表的格式是： 输入文本是一个长句，句中只包含汉字，不包含数字、标点、空格、回车以及其它任何特殊符号。文本规模小于等于50，000汉字。 输入词表的规模小于等于100，000个词，所有词不重复，词在27个汉字之间，每个词占一行。 实现基于词表的词频统计，从磁盘中读取词表和文本，将词频统计结果输出到磁盘中，输出结果要求按字典序排序，并计算出程序运行时间。 二、案例分析 首先分析选取哪种数据结构，以达到高速搜索的目的。具备搜索功能的数据结构很多，如线性表、平衡树、哈希表等，当数据量庞大时，使用哈希表最合适。哈希表的概念在案例“哈希表的演示”已经做了介绍。 根据需要构造一个哈希表类，在类中实现如下操作： l 建立哈希表将词表在内存中存储起来，这个存储的过程就是类的构造函数。案例中的词表是数量较大的词组，词与词之间用空格隔开。因此可用文件流函数getline来实现。每次调用getline函数便得到一个存有词的字符串，然后将字符串按照某种散列函数插入到哈希表中，一直到词表全部存储为止。 l 统计词频：从词表中读取文本文件，存储在一个字符串里，因为每个汉字存储在两个字节里，所以词在414个字节之间，用char word15即可表示一个词。考虑到词频统计的交集性和组合性原则，可对在文本字符串中的每个汉字与其后的汉字分别组成27个汉字的词，在词表中进行搜索，每被搜到一次，次数加1。循环直到文本末尾。 l 哈希函数的实现：用char word15存储的词得到一个关键字，然后除以某个素数，得到的余数为散列地址。由于数据较多，要高速完成搜索，散列到每个相同地址的元素要尽量少，因此素数要很大，关键字的范围也很大且不重叠。 l 按字符的字典序排序输出：而哈希表是乱序存储的，故可先遍历哈希表，将所有词频大于0的词存入数组中，用快速排序法将这个数组中的元素排序。 三、案例设计 1类的设计 根据案例分析，需要设计出两个结构体NODE和TABLE，同时还需设计一个类SYMBOLTABLE。其中：结构体NODE是哈希桶中节点的数据结构， TABLE是哈希表的结构，SYMBOLTABLE类提供了诸如：哈希函数、查找词汇、遍历哈希表、将词汇插入哈希表中、快速排序等功能。 结构体 NODE struct NODE char word15;/关键字 int number; /关键字被访问的次数 PNODE next;/指向下一结点的指针 ; 结构体 TABLE struct TABLE int prime;/哈希桶数 PNODE * buckets;/指向结点指针的指针，可构成动态的指针数组 ; SYMBOLTABLE类 图20-5 SYMBOLTABLE类图 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<string > #3 #include<fstream> #4 typedef struct TABLE* PSYMBOLTABLE;/符号表构造函数，哈希符号表指针 #5 typedef struct NODE* PNODE; /结点指针 #6 struct NODE #7 #8 char word15; /关键字 #9 int number; /此词被访问的次数 #10 PNODE next; /指向下一结点的指针 #11 ; #12 struct TABLE #13 #14 int prime; /哈希桶数 #15 PNODE * buckets; /指向结点指针的指针，可构成动态的指针数组 #16 ; #17 class SYMBOLTABLE #18 #19 public: #20 SYMBOLTABLE(char *argv); /创建哈希表 #21 SYMBOLTABLE #22 int 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); /使用快速排序法 #28 private: #29 PSYMBOLTABLE p; /哈希符号表指针 #30 int num; /被遍历的词数 #31 ; #32 SYMBOLTABLE: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;i<p->prime;i+) /动态分布内存 #43 p->bucketsi=NULL; #44 for(i=0;i<100000;i+) #45 #46 if(in.good) #47 #48 in.getline(s,16,'n'); /读入每个词 #49 sstrlen(s)='0' #50 if(!strcmp(s,"0") #51 break; #52 n=Hash(s); #53 InsertIntoSymTbl(s); /将词表插入到哈希表中 #54 #55 else #56 break; #57 #58 #59 void SYMBOLTABLE:InsertIntoSymTbl(char *word) /插入函数 #60 #61 int n; #62 PNODE t; #63 n=Hash(word); #64 t=new struct NODE; #65 t->number=0; #66 strcpy(t->word,word); /复制word的内容 #67 t->next=p->bucketsn; /形成链表 #68 p->bucketsn=t; #69 #70 void SYMBOLTABLE:SearchInSymTbl(char* argv) /在文本中搜索词汇 #71 #72 ifstream text(argv); #73 char story100002; #74 text.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;i<m;i+=2) #81 #82 s0=storyi; #83 s1=storyi+1; /第一个字 #84 for(j=2;j<=12&&i+j<m;j+=2) /每增加一个字则在词表中搜一次 #85 /最多增加到七个字的词 #86 sj=storyi+j; #87 sj+1=storyi+j+1; #88 sj+2='0' /以'0'为结尾符 #89 FindNode(s); #90 #91 #92 #93 void SYMBOLTABLE:TraverseSymTbl(char* argv) /遍历哈希表 #94 #95 ofstream out(argv); #96 out<<num; /输出总的词数 #97 if(num=0) /若为0，直接结束 #98 return; #99 int i; #100 PNODE verb100001; /最多10万词，还有一个岗哨 #101 for(i=0;i<num+1;i+) #102 verbi=new struct NODE; /有num个词，再加上一个哨岗 #103 int j=0; #104 PNODE u; #105 for(i=0;i<(p->prime);i+) #106 #107 u=p->bucketsi; #108 while(u!=NULL) #109 #110 if(u->number>0) /遍历哈希表，从中找出词频大于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 out<<endl<<verbi->word<<" "<<verbi->number; #122 #123 int SYMBOLTABLE:Hash(char* word) /哈希函数，求散列地址 #124 #125 unsigned long s=1,t=1,r=1,m=1; #126 int i; #127 for(i=0;i<4;i+) #128 s*=wordi; #129 while(wordi!='0'&&i<8) #130 #131 t*=wordi; #132 i+; #133 #134 while(wordi!='0'&&i<12) #135 #136 r*=wordi; #137 i+; #138 #139 while(wordi!='0') #140 #141 m*=wordi; #142 i+; #143 #144 return (s+t+r+m)%(p->prime); #145 #146 void 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 #165 void 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(i<j) #173 #174 PNODE temp=pi; #175 pi=pj; #176 pj=temp; #177 #178 while(i<j); #179 ps=pj; #180 pj=x; #181 if(s<j-1) #182 Qsort(p,s,j-1); #183 if(j+1<t) #184 Qsort(p,j+1,t); #185 / * / * tongji.cpp 系统主文件 / * #1 #include<iostream.h> #2 #include"source.h" /用包含命令将类定义头文件包含进来 #3 #include"time.h" #4 void 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中,用时"<<end-start<<"毫秒."<<endl; #13 五、案例总结与提高 1案例总结 本案例类的设计并不复杂，但是要求读者除了具备C+基本知识和简单的数据结构知识外，还要求读者掌握文件流、哈希表、快速排序、算法设计、主函数接口等诸多知识点，否则案例理解起来比较困难。本案例用到的许多知识点在数据结构教材中都有很详细的讲述，读者需要查找相关书籍熟悉这些知识，对照程序来理解掌握这些知识，逐步提升程序设计水平。 2案例提高 可以考虑采用更高效、冲突更少的哈希函数来完成本案例。 可以试着改用平衡树做为数据结构。关于平衡树的相关知识可查阅数据结构教材。