数据结构实验三-哈夫曼编解码器.doc

北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验三——树
学生姓名：大学霸
班 级： xxxxxxxxxx
班内序号： xx
学 号： xxxxxxxxxx
日 期： 2012年12月1日
1．实验要求
a. 实验目的
通过选择两个题目之一进行实现，掌握如下内容：
Ø 掌握二叉树基本操作的实现方法
Ø 了解赫夫曼树的思想和相关概念
Ø 学习使用二叉树解决实际问题的能力
b. 实验内容
利用二叉树结构实现赫夫曼编/解码器。
基本要求：
1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树
2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。
3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。
5、 打印(Print)：以直观的方式打印赫夫曼树（选作）
6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

测试数据：
I love data Structure, I love Computer。I will try my best to study data Structure.
提示：
1、用户界面可以设计为“菜单”方式：能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的
字符一律不用编码。
2. 程序分析
2.1 存储结构
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。只有度为0和2的结点的二叉树成为正则二叉树。哈夫曼树就是这样。根据二叉树的性质，一颗有n个叶子的哈夫曼树共有2n-1个叶子结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个节点。由于每个结点同时还包括其双亲信息和孩子信息，所以用一个静态三叉链表来存储哈夫曼树。
weight
lchild
rchild
parent
2
-1
-1
4
3
-1
-1
4
6
-1
-1
5
9
-1
-1
6
5
0
1
5
11
4
2
6
20
3
5
-1

0
1
2
3
4
5
6
20
11
5
A
B
Z
C
1
0
0
1
1
0
20
11
5
A
B
Z
C

0
0
1
C++描述如下
struct HNode //静态三叉链表元素
{
int weight; //结点权值
int parent; //双亲指针
int lchild; //左孩子指针
1
1
0
int rchild; //右孩子指针
int mark; //标记是否已经访问过
};

如图所示的哈夫曼树，其对应的编码表可以是如图所示的结构，实际上字符的编码应该用bit表示，即对于1个字符‘Z’使用三个比特001表示
哈夫曼编码表的C++描述：
struct HCode //哈夫曼编码表
{
char ch[2]; //字符
int freq; //频度
char code[100]; //字符编码
};

2.2 关键算法分析
核心算法思想：
1. 哈夫曼编码(Huffman Coding)是不等长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。
2. 哈夫曼编码可以实现无损数据压缩。单个字符用一个特定长度的位序列替代：在字符串中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
关键算法思想描述和实现：
关键算法1：初始化函数
用字符串记录用户输入的原始数据，统计一共出现了多少种字符，各出现了多少次即为字符的权值。对未出现的字符不予统计编码。将统计的叶子节点编制成数组。为创建哈夫曼树作准备。
[1] 用字符串str接收用户输入的数据
[2] 用数组frequency存储字符出现的个数
[3] 如果字符出现过，叶子节点数加1
[4] 创建哈夫曼树Htree，哈夫曼编码表HcodeTable
[5] 初始化哈夫曼编码表
[5.1] 判断字符是否出现过
[5.1.1] 记录权值和字符
[5.1.2] 编码形式置空
[6] 初始化哈夫曼树
[6.1] 标记叶子节点，无左子树右子树及父节点

C++实现如下
void Huffman::Initial()
{
[1] cin.getline(str,MAXSIZE); //从键盘接收字符串
short frequency[128]={0};
leaf=0;
[2] for(int i=0;str[i]!='\0';i++) //统计字符频度
frequency[(short)str[i]]++;
[3] for(int j=0;j<128;j++) //统计字符种类个数
if(frequency[j]!=0) leaf++;
[4] HTree = new HNode[leaf*2-1]; //创建哈夫曼树
HCodeTable = new HCode[leaf]; //创建哈夫曼编码表
[5] for(int k=0,m=0;k<128;k++) //初始化哈夫曼编码表
{
[5.1] if(frequency[k]!=0) //字符串是否出现k对应的字符
{
[5.1.1] HCodeTable[m].freq=HTree[m].weight=frequency[k]; //字符的频度即为权值
HCodeTable[m].ch[0]=(char)k; //字符数据
HCodeTable[m].ch[1]='\0';
[5.1.2] HCodeTable[m].code[0]='\0'; //字符编码先设为空
HTree[m].mark =0;
m++;
}
}
[6] for(int k=0;k<leaf;k++) //初始化哈夫曼树
HTree[k].lchild=HTree[k].rchild=HTree[k].parent=-1;//标记叶子节点，无左右孩子及父节点
cout<<"编码初始化完成！\n";

时间复杂度：因为操作每次都需要把str遍历一遍，如果str长度为n，则时间复杂度为o（n）
关键算法2：建立哈夫曼树
建立哈弗曼树——即最优二叉树。这里实现时：每建立一个父节点就需要扫描权值序列得到两个最小的权值。由于节点个数逐渐增多，因而扫描次数动态变化，程序里设置计数变量来控制扫描次数的变化。另外设置标记来标识节点是否已经被取出。由于前面得出了总的叶子节点个数，根据哈弗曼树建立的规律可以知道总的节点数和建立哈弗曼树过程中的父子节点间的对应关系，因而可以通过下标准确定位节点，动态建立哈弗曼树。
[1]初始化最小权值min，最小权值点num，扫描次数front，查找最小值的次数count，左、右子树权值lcvaule、rcvaule
[2] 在前front个节点中找到最小权值点，记录结点和权值
[3] 最小节点已被访问，
[4] 找到第一个最小权值点即为新节点的左孩子
[4.1] 记录权值，建立此节点和新节点的关系
[5] 找到第二个最小权值点即为新节点的右孩子
[5.1] 记录权值，建立此节点和新节点的关系
[5.2] 新节点的权值等于孩子结点权值之和
[5.3] 新节点下移，查找次数count清零
……
[6] 根节点的父节点为空

C++实现：
void Huffman::CreateTree()
{
[1] int min=MAXSIZE;
int num(0),front(leaf),count(0),lcvalue(0),rcvalue(0);
for(int s=0;s<(2*leaf-2);s++)
{
[2] for(int i=0;i<front;i++) //遍历编码表中所有元素寻找最小值
{
if(HTree[i].mark!=1 && HTree[i].weight<=min) //找到权值最小的结点
{ min=HTree[i].weight; num=i; } //记录最小权值，结点下标
}
[3] HTree[num].mark=1; //标记已读
count++;
[4] if(count==1) //第一个最小节点即左孩子
{
[4.1] lcvalue=min; //lcvaule保存左孩子的权值
HTree[num].parent=front; //修改左孩子的父节点
HTree[front].lchild=num; //记录新节点的左孩子
}
[5] if(count==2) //第二个最小节点即右孩子
{
[5.1] rcvalue=min; //rcvalue保存右孩子的权值
HTree[num].parent=front; //修改第二个节点的父节点
HTree[front].rchild=num; //记录新节点的右孩子
[5.2] HTree[front].weight=lcvalue+rcvalue; //新节点的权值等于lcvalue+rcvalue
[5.3] front++; //新节点下移
count=0; //计数器清零
}
min=MAXSIZE;
}
[6] HTree[2*leaf-2].parent=-1; //根节点
}

时间复杂度：假设有n个叶子节点，在原有叶子节点的基础上还要新创建n-1个结点才能构成哈夫曼树，每次创建新节点时还要在前n个节点中找到最小的两个结点做为左子树和右子树，则时间复杂度为o(n^2)

关键算法3：建立哈夫曼编码表
建立字符编码表。这里采用从叶子节点到根节点的顺序逆序编码，然后字符串转置得到最终编码。如果有n个叶子节点需要n次循环编码
[1] 从叶子节点开始循环，直到根节点
[1.1] 若该节点师父节点的左分支,则编码0
[1.2] 若该节点师父节点的右分支,则编码1
[1.3] 将该节点的父节点当做叶子节点进行下一次分析
[2] 将编码字符逆置

C++实现：
void Huffman::CreateTable()
{
for(int j=0,parent=0,child=0;j<leaf;j++) //对所有叶子节点自下而上进行编码
{
parent=HTree[j].parent;
child=j;
[1] while(parent!=-1) //一直循环到根节点
{
[1.1] if(HTree[parent].lchild==child)
strcat(HCodeTable[j].code,"0");//左孩子标‘0’
[1.2] else
strcat(HCodeTable[j].code,"1");//右孩子标‘1’
[1.3] child=parent; //将父节点当成叶子节点
parent=HTree[child].parent; //父节点的父节点

}
[2] strrev(HCodeTable[j].code); //字符串反转后即为叶子节点的编码
}
}

时间复杂度:假设有n个叶子节点，则哈夫曼树深度至少为o(log2n),每次编码都要向上循环到根节点，则编码总的时间复杂度为o(n*log2n)
关键算法4：编码
扫描原字符串，在字符编码表中查找相应字符的编码，串接写入编码串。
[1] 创建pcode记录编码后的数据，并置空
[2] 连续编码直到str结束
[2.1] 在编码表中进行匹配
[2.2] 串接字符

C++实现：
void Huffman::Encoding()
{
int num;
[1] pcode=new char[MAXSIZE]; //pcode存储压缩后的字符串
pcode[0]='\0'; /pcode初始化
[2] for(int i=0;str[i]!='\0';i++) //连续编码直到str结束
{
num=0;
[2.1] for(int j=0;str[i]!=HCodeTable[j].ch[0];j++) num++;//找到编码表中对应下标
[2.2] strcat(pcode,HCodeTable[num].code); //串接字符
}
}
时间复杂度：假设有原始数据N个字符，出现了n种字符。一个一个的进行匹配，可知此过程的时间复杂度为o(N*n)

关键算法5：解码
这里从根节点出发，顺序查找，根据0和1的决定走左支还是右支。当查找到叶子节点时，将字符串接写入解码字符串，并将查找点置于根节点，开始后续解码，循环直到编码后的字符串遍历完毕。
[1] 创建字符数组pstr记录解码后的数据
[2] 连续解码直到pcode结束
[2.1] 如果是叶子结点
[2.1.1] 串接字符，重新设置根节点
[2.2] 如果是0，走左分支
[2.3] 如果是1，走走分支

C++实现：
void Huffman::Decoding()
{
[1] int parent=leaf*2-2; //根节点在HTree中的下标
pstr=new char[MAXSIZE]; //pstr存储解压后的字符串
pstr[0]='\0';
[2] for(int i=0;pcode[i-1]!='\0';i++) //连续解码直到pcode结束
{
[2.1] if(HTree[parent].lchild==-1) //左孩子为空即为叶子节点
{
[2.1.1] strcat(pstr,HCodeTable[parent].ch); //串接字符
parent=leaf*2-2; //为了进行下一次查找，parent重新移至根节点
}
[2.2] if(pcode[i]=='0') parent=HTree[parent].lchild;//左分支
[2.3] else parent=HTree[parent].rchild;//右分支
}
}

时间复杂度：设编码后的数据pstr长度为n,解码从头进行到尾，此时间复杂度为o(n)
关键算法6：分析
在分析压缩比前首先判断编码前的字符串str和编码后的字符串pstr是否相同，调用strcmp()判断两个字符串，如果相同，编/解码成功
编码前的大小即用户输入的字符串str的大小，编码后数据变成由0 1组成的字符串，在机器中以二进制数的形式存储，所以需要把字符串pcode的大小除8就是编码后的大小

C++实现：
void Huffman::Analyse()
{
cout<<"分析结果如下：\n";
if(strcmp(str,pstr)==0) //进行比较
{
cout<<"解码后字符串与原字符串相同，编码/解码成功。\n";
int before=strlen(str); //原始数据大小
int length=strlen(pcode);
int after=ceil((float)length/8); //压缩后的数据大小
float rate=(float)after/before; //计算压缩比率
cout<<"压缩前的数据大小 ： "<<before<<"Byte"<<endl;
cout<<"压缩后的数据大小 ： "<<after<<"Byte"<<endl;
cout<<"压缩率 ： "<<100*rate<<"%"<<endl;
}
else
cout<<"解码后字符串与原字符串不同，编码/解码失败。\n";
}

时间复杂度：没有循环或递归，所以为o(1)
关键算法7：直观打印哈夫曼树
思想和普通二叉树的中序遍历相同，需要不断的递归。要打印一个节点的权值，首先要打印它的右子树，最后打印它的右子树。同时因为要打出树的形状，函数还需要layer参数存储这是第几层，根据layer的不同决定前面空多少格。
[1] 如果到达叶子节点
[1.1]打印空格
[1.2]打印该节点的权值
[1.3]回溯
[2]否则
[2.1]进入该节点的右子树
[2.2]打印空格
[2.3]打印该节点的权值
[2.4]进入该节点的左子树
C++实现：
void Huffman::PrintTree(int TreeNode,int layer)
{
[1] if(HTree[TreeNode].rchild==-1)
{
[1.1] for(int i=0;i<layer*3;i++) //根据layer的大小确定打印多少个空格
cout<<' ';
[1.2] cout<<HTree[TreeNode].weight<<endl;
[1.3] return;
}
[2] else
{
[2.1] PrintTree(HTree[TreeNode].rchild,layer+1); //先打印右子树，layer记录层次
[2.2] for(int i=0;i<layer*3;i++) //根据layer的大小确定打印多少个空格
cout<<' ';
[2.3] cout<<HTree[TreeNode].weight<<endl; //打印结点权值
[2.4] PrintTree(HTree[TreeNode].lchild,layer+1); //打印左子树
}
}

时间复杂度：与二叉树的中序遍历时间复杂度类似，假设有n个叶子节点，时间复杂度为o(n)
2.3 其他
3. 程序运行结果

测试结论： 本程序对所有ASCII编码均适用，允许的最大长度内都能正确的编码和解码

4. 总结
1. 哈夫曼编码根据自负出现的概率来构造带权平均长度最短的编码。它是一种变长的编码。它的基本原理是频繁使用的数据用较短的数据代替，较少使用的数据用较长的数据代替，每个数据的代码各不相同，但最终编码的平均长度是最小的。通过这次的实验，可以初步掌握和理解这种巧妙的结构

2. 这次实验和前两次比起来明显增加了难度，每一个模块都用到了不同的思想，书上提供的代码将思想简单的转化了一下，在实际应用时，我都要进行不同程度的改写，才能把它们组合起来，所以代码写的也比之前两次都要长，中间遇到的问题也很多，总结了一下比如对用户输入的字符串进行统计，一直不知道进行统计然后上网去查知道了ASCII码字符正好对应128个短整型数，这样就把一个统计字符的工作转化成统计数字的工作，能方便一些。在对字符串的操作上也没有之间使用书上的程序，而是查到了string类的库函数strcat()，strrev()也是简化了代码。

3. 改进方向
(1) 程序只能对ASCII编码，不支持对汉字的编码，后面应该考虑怎么把汉字编码加进去。
(2) 由于时间关系，只做了用户手动输入字符串，可以把文件流也加进去，把要压缩文件通过程序处理后保存起来，下次要用时在使用解压，这样更具有实用性。
(3) 用数组处理字符串造成了一定的空间的浪费，后续应考虑采取其他方式处理字符串。
第15页