《案例二十基于词表的词频统计.ppt》由会员分享，可在线阅读，更多相关《案例二十基于词表的词频统计.ppt（38页珍藏版）》请在三一办公上搜索。
1、1页 共36页,案例二十 基于词表的词频统计,本案例知识要点链表的使用文件操作哈希表的使用快速排序法类的设计和使用,2页 共36页,一、案例需求,案例描述词频统计就是统计一个句子或一篇文章中各种词出现的频率，它是中文信息处理的一项基本技术，在很多领域中都有重要的应用。例如在中文搜索引擎（如Google、百度）中，除特别常用的词以外，一篇文章中出现频率较高的词通常能反映这篇文章的主题，因此可以使用词频来对中文文章进行归类。本案例实现按词表对文章中的词语进行分析，并按字典序给出词表中各词语在文章中出现的次数。案例效果图本案例需要一个待统计文本文件，如图所示。,3页 共36页,待统计文本文件,4页
2、共36页,本案例需一个词表文件，如图所示。,词表文件内容,5页 共36页,本案例最终统计出每个词在文本中出现的次数。运行效果如图所示。,运行效果,6页 共36页,本案例最终统计出的结果保存在文件out.txt中。效果如图所示。,out.txt文件,7页 共36页,功能说明（1）本案例需要一个文本和一个词表，统计出每个词在文本中出现的次数。统计的原则包括以下两种：交集型。例如“内存在涨价”，需要统计“内存”和“存在”两个词各一次（假设这两个词都在词表中）。组合型。例如“中美关系在发展”，需要统计“中美”、“关系”和“中美关系”（假设这3个词都在词表中）。,8页 共36页,文本和词表的格式如下：文
3、本是一个长句，句中只包含汉字，不包含数字、标点、空格、回车以及其他任何特殊符号。文本规模小于或等于50 000汉字。词表的规模小于或等于100 000个词，所有词不重复，词在27个汉字之间，每个词占一行。实现基于词表的词频统计，从磁盘中读取词表和文本，将词频统计结果输出到磁盘中，输出结果要求按字典序排序，并计算出程序运行时间。,9页 共36页,二、案例分析,根据需要构造一个哈希表类，在类中实现如下操作：（1）建立哈希表，将词表在内存中存储起来，这个存储的过程就是类的构造函数。案例中的词表是数量较大的词组，词与词之间用空格隔开。因此可用文件流函数getline来实现。每次调用getline函数便
4、得到一个存有词的字符串，然后将字符串按照某种散列函数插入到哈希表中，一直到词表全部存储为止。（2）统计词频。从词表中读取文本文件，存储在一个字符串中，因为每个汉字存储在两字节中，所以词在414字节之间，用char word15即可表示一个词。考虑到词频统计的交集性和组合性原则，可将在文本字符串中的每个汉字与其后的汉字分别组成27个汉字的词，在词表中进行搜索，每被搜到一次，将统计次数加1。循环直到文本末尾。,10页 共36页,（3）哈希函数（散列函数）的实现。用char word15存储的词得到一个关键字，然后除以某个素数，得到的余数为散列地址。由于数据较多，要高速完成搜索，散列到每个相同地址的
5、元素要尽量少，因此素数要很大，关键字的范围也要很大而且不重叠。（4）按字符的字典序排序输出。哈希表是乱序存储的，因此可先遍历哈希表，将所有词频大于0的词存入数组中，用快速排序法对这个数组中的元素进行排序。,11页 共36页,三、案例设计,1类的设计根据案例分析，需要设计出两个结构体NODE和TABLE，同时还需要设计一个类SYMBOLTABLE。其中，结构体NODE是哈希桶（哈希桶即哈希表中各个同地址值的元素构成的链表）中节点的数据结构，TABLE是哈希表的结构，SYMBOLTABLE类提供了诸如哈希函数、查找词汇、遍历哈希表、将词汇插入哈希表中、快速排序等功能。,12页 共36页,13页 共
6、36页,14页 共36页,15页 共36页,16页 共36页,17页 共36页,2主程序设计 在主函数中声明了一个SYMBOLTABLE类的对象，依次调用哈希表类的构造函数、统计函数、输出函数即可。另外，为了记录程序的运行时间，包含了time头文件，调用clock函数，能精确到毫秒。主程序有详细的注释，清晰易懂，流程图略。,18页 共36页,19页 共36页,20页 共36页,21页 共36页,22页 共36页,23页 共36页,24页 共36页,25页 共36页,26页 共36页,27页 共36页,28页 共36页,29页 共36页,30页 共36页,31页 共36页,32页 共36页,33
7、页 共36页,34页 共36页,35页 共36页,36页 共36页,37页 共36页,五、案例总结与提高,案例总结本案例类的设计并不复杂，但是要求读者除了具备C+基本知识和简单的数据结构知识以外，还要求读者掌握文件流、哈希表、快速排序、算法设计、主函数接口等诸多知识点，否则案例理解起来比较困难。本案例用到的许多知识点在数据结构教材中都有很详细的讲述，读者可以查找相关书籍熟悉这些知识，对照程序来理解掌握这些知识，逐步提升程序设计水平。,38页 共36页,案例提高可以考虑采用更高效、冲突更少的哈希函数（HashFun(const string&s)）来完成本案例。可以试着改用平衡树（AVL）作为数据结构。关于平衡树的相关知识可查阅数据结构教材。,
