bd留置针
● 链表的使用
● 文件操作
● 哈希表的使用
● 快速排序法
● 类的设计和使用
一、案例需求
1．案例描述
词频统计就是统计一个句子或一篇文章中各种词出现的频率，它是中文信息处理的一项基本技术，在很多领域都有重要的应用。比如在中文搜索引擎（如：google，baidu）中，除去特别常用的词，一篇文章中出现频率较高的词通常能反映这篇文章的主题，因此可以使用词频来对中文文章进行文本聚类。本案例实现按词表对文章中的词语进行分析，并按字典序给出词表中各词语在文章中出现的频数。 2．案例效果图
（1）案例需要一个待统计文本文件，效果图如图20-3、20-4所示。
密令截击图20-1待统计文本文件内容
（2）本案例需一个词表文件，效果图如图20-2所示。
图20-2词表文件内容
（3）本案例最终统计出每个词在文本中出现的次数。运行结果如图20-3所示。
图20-3运行结果
（3）本案例最终统计出的结果保存在中。效果图如图20-4所示。
图20-4运行结果文件内容
3．功能说明
（1）本案例需要一个文本和一个词表，统计出每个词在文本中出现的次数。统计的原则包括以下两种：
● 交集型：如“内存在涨价”，需要统计“内存”和“存在”（假设这两个词都在词表中）。
● 组合型：如“中美关系在发展”，需要统计“中美”、“关系”和“中美关系”（假设这三个词都在词表中）。
（2）文本和词表的格式是：
输入文本是一个长句，句中只包含汉字，不包含数字、标点、空格、回车以及其它任何特殊符号。文本规模小于等于50，000汉字。
输入词表的规模小于等于100，000个词，所有词不重复，词在2~7个汉字之间，每个词占一行。
（3）实现基于词表的词频统计，从磁盘中读取词表和文本，将词频统计结果输出到磁盘中，输出结果要求按字典序排序，并计算出程序运行时间。
二、案例分析
首先分析选取哪种数据结构，以达到高速搜索的目的。具备搜索功能的数据结构很多，如线性表、平衡树、哈希表等，当数据量庞大时，使用哈希表最合适。哈希表的概念在案例“哈希表的演示”已经做了介绍。
根据需要构造一个哈希表类，在类中实现如下操作：
● 建立哈希表将词表在内存中存储起来，这个存储的过程就是类的构造函数。案例中的词表是数量较大的词组，词与词之间用空格隔开。因此可用文件流函数getline来实现。每次调用getline函数便得到一个存有词的字符串，然后将字符串按照某种散列函数插入到哈希表中，一直到词表全部存储为止。 ● 统计词频：从词表中读取文本文件，存储在一个字符串里，因为每个汉字存储在两个字节里，所以词在4~14个字节之间，用char word[15]即可表示一个词。考虑到词频统计的交集性和组合性原则，可对在文本字符串中的每个汉字与其后的汉字分别组成藏药膝盖疼的药丶2~7个汉字的词，在词表中进行搜索，每被搜到一次，次数加1。循环直到文本末尾。
● 哈希函数（散列函数）的实现：用char word[15]存储的词得到一个关键字，然后除以某个素数，得到的余数为散列地址。由于数据较多，要高速完成搜索，散列到每个相同地址的元素要尽量少，因此素数要很大，关键字的范围也很大且不重叠。
● 按字符的字典序排序输出：而哈希表是乱序存储的，故可先遍历哈希表，将所有词频大于0的词存入数组中，用快速排序法将这个数组中的元素排序。
三、案例设计
1．类的设计
根据案例分析，需要设计出两个结构体NODE和TABLE，同时还需设计一个类SYMBOLTABLE。其中：结构体NODE是哈希桶（哈希桶--哈希表中各个同地址值的元素
构成的链表）中节点的数据结构， TABLE是哈希表的结构，SYMBOLTABLE类提供了诸如：哈希函数、查词汇、遍历哈希表、将词汇插入哈希表中、快速排序等功能。
（1） 结构体 NODE
struct NODE
{
char word[15];//关键字
int number; //关键字被访问的次数
PNODE next;//指向下一结点的指针
};
（2） 结构体 TABLE
struct TABLE
{
int prime;//哈希桶数
PNODE * buckets;//指向结点指针的指针，可构成动态的指针数组
};
（3） SYMBOLTABLE类
图20-5 SYMBOLTABLE类图
● 数据成员
PSYMBOLTABLE p;
哈希符号表指针。
int num;
被遍历的词数。
● 函数成员
SYMBOLTABLE(char *argv);
构造函数、创建哈希表。
~SYMBOLTABLE()
析构函数。
int Hash(char* word);
静态哈希函数，形参：字符串，桶数。返回桶的下标。
void FindNode(char* s);
形参：结点指针，字符串。在某一链中到某词汇，若到则词频数加1，且返回。 void InsertIntoSymTbl(char name[20]);
将词汇插入哈希表中。
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 word[15]; //关键字
#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 name[20]); //将词表插入哈希表中
#25 void SearchInSymTbl(char* argv); //搜索某一词汇
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议