哈夫曼压缩解压数据结构设计报告样本.doc

《数据构造》课程设计

数学与应用数学一班 胡耕岩 214147
一、 问题分析和任务定义
1.1设计任务
采用哈夫曼编码思想实现文献压缩和恢复功能，并提供压缩先后占用空间之比。规定
（1）运营时压缩原文献规模应不不大于5K。
（2）提供恢复文献与原文献相似性对比功能。
1.2问题分析
本课题是运用哈夫曼编码思想，设计对一种文本文献（.txt）中字符进行哈夫曼编码，生成编码压缩文献，并且还可将一种压缩后文献进行解码还原为原始文本文献（.txt）。
在理解哈夫曼压缩解压缩原理之前，一方面让咱们来结识哈夫曼树。哈夫曼树又称最优二叉树，是带权途径长度最小二叉树。
在文本文献中多采用二进制编码。为了使文献尽量缩短，可以对文献中每个字符浮现次数进行记录。设法让浮现次数多字符二进制码短些，而让那些很少浮现字符二进制码长某些。若对字符集进行不等长编码，则规定字符集中任一字符编码都不是其他字符编码前缀。为了保证哈夫曼编码唯一性，咱们可以对它左右子树大小予以比较限定，如：左子树权值不大于右子树权值。哈夫曼树中左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历途径分支‘0’和‘1’构成字符串，为该节点相应字符哈夫曼编码。
记录字符中每个字符在文献中浮现平均概率（概率越大，规定编码越短）。运用哈夫曼树特点：权越大叶子离根越近，将每个字符概率值作为权值，构造哈夫曼树。则概率越大节点，途径越短。哈夫曼译码是从二进制序列头部开始，顺序匹配成共某些替代成相应字符，直至二进制转换为字符序列。
哈夫曼用于文献解压缩基本是在压缩二进制代码同步还必要存储相应编码，这样就可以依照存储哈夫曼编码对压缩代码进行压缩。总之，该课题任务应当是一方面要打开要压缩文本文献并读出其字符浮现频率，以其为权值构建哈夫曼树。另一方面要找到构建压缩功能办法，在构建哈夫曼树基本上进行编码，变化字符原先存储构造，以达到压缩文献目，以外尚有存储相应哈夫曼编码，为解压缩做准备。

1.3测试用数据
本实验数据是通过读入一种名为huffman.txt文本文档，文档中内容为字符型数据。

二、 概要设计和数据构造选取
如下是在任务分析对题意理解做出概要设计和对数据构造选取：
1、 数据构造定义
//huffman树结点构造体
typedef struct HTnode
{
long weight; //记录结点权值
int parent; //记录结点双亲结点位置
int lchild; /结点左孩子
int rchild; //结点右孩子
int *code; //记录该结点huffman编码
int codelen; //记录该结点huffman编码长度
//初始化结点，令其权值为无穷大，无双亲及左右孩子
HTnode()
{
weight = MAX;
parent = -1;
lchild = -1;
rchild = -1;
codelen = 0;
}
}HTnode;

2、 定义huffman数类及其函数
class huffmanTree
{
public:
huffmanTree();
virtual ~huffmanTree();
bool count(char *input)； //压缩时记录各字符浮现次数，将其写入相应结点权值
void create(); //压缩时依照各结点权值构造huffman树
void code(); //压缩时运用huffman树计算每个字符huffman编码
void printcode(); //列出每个字符huffman编码
void addbit(int bit)；//压缩时对一种未满8个bitbyte中加入一种bit
void resetbyte(); //将byte清空
bool compress(char *input，char *output);//压缩函数,成功返回 true 失败 false
bool decompress(char *input，char *output)；//恢复函数,成功返回 true 失败false
void compare(char *input，char *output); //将原文献与压缩后文献比较
void compare2(char *input，char *output)；//将原文献与恢复后文献比较
private:
int root; //记录根结点位置
int leafnum; //记录不同字符个数
HTnode HT[leaf*2-1]; //HTnode构造数组，用来表达huffman树，树最大结点个数不会超过leaf*2-1
char byte; //压缩文献时用来缓冲bit变量
int bitsnum; //byte中bit个数
int lacknum; //压缩到最后byte中bit不满8个时填充0个数
};
3、 主程序流程及模块间关系
主函数实例化huffmanTree类，并实现菜单工具栏，通过顾客选取输入，用switch语句进行分支执行huffmanTree类中功能函数：
1:压缩函数 bool compress(char *input，char *output)
2:恢复函数 bool decompress(char *input，char *output)
3:恢复文献与原文献对比函数 void compare2(char *input，char *output)
并可在完毕相应功能后安全退出，压缩或恢复文献在同文献夹下生成。

三、 详细设计和编码
核心算法----huffman算法：
（1） 依照给定n个权值｛w1,w2,……,wn｝构成n棵二叉树集合F=｛T1,T2,……,Tn｝,其中每棵二叉树T1中只有一种带权 w1依照点，其左右子树均空。
（2） 在F中选用两棵根结点权值最小树作为左右子树构造一棵新二叉树，且置新二叉树根结点权值为其左右树上根结点权值之和。
（3） 在F中删除这两棵树，同步将所得到二叉树加入F中。
（4） 重复（2）(3),直到F中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短编码方案。
为了详细阐明这个问题，特如下面例子来阐明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2，可以构成许各种不同带权二叉树，但各个带权二叉树WPL（树带权途径长度）不同，要想由n个带权叶子结点所构成二叉树中，满二叉树或完全二叉树不一定是最优树。权值越大结点离根越近二叉树才是最优二叉树（huffman树）。按照上面算法，则可按照下面图构造过程生成huffman树。
主程序模块:

主函数
菜 单
huffmanTree类
压缩函数
compress
恢复函数
decompress
对比函数
compare2

Huffman编码流程
NO
YES
哈夫曼编码位操作压缩存储
压缩文献成功!
计算压缩率%
打开文本文献记录文献长度
初始化节点
构建哈夫曼树
计算左右分支权值大小,进行无重复前缀编码
压缩文献失败

Huffman解码流程
NO
YES
解压压缩文献成功!
解压缩文献失败!
打开压缩文献读取原文献长度进行文献定位
依照哈夫曼编码长短,对节点进行排序
通过哈夫曼编码长短,依次解码,从本来位存储还原到字节存储
在单字节内对相应位置补0

四、 上机调试
如下是我在上机过程中遇到某些问题及解决方案
开始考虑问题是，要对文献进行压缩，如何才干达到比较好效果，那就
huffman编码是采用等长编码还是采用不等长问题，采用不登长编码要避免译码二义性或多义性。假设用0表达字符D,用01表达字符C则当接受到编码串“…01…”，并译到字符0时，是及时译出相应字符D，还是接着与下一种字符1一起译为相应字符C，这就产生了二义性。因而，若对某一种字符集进行不等长编码，则规定字符集合中任何一种字符编码都不能是其她字符编码前缀。符合此规定编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所相应编码二叉树也可以直接看出，任何一种叶子结点都不也许是其他叶子结点双亲，也就是说，只有当一种结点是另一种结点双亲时，该结点字符编码才会是另一种结点字符编码前缀。
为了使不等长编码为前缀编码，可用该字符集中每个字符作为叶子结点生成一棵编码二叉树，为了获得文献最短长度，特将每个字符浮现频率作为字符结点权值赋予该结点上，求出此树最小带权途径长度就等于文献最短长度。因而，对文献进行压缩，就可以转化字符集中所有字符作为叶子结点，字符浮现频率作为权值所产生 huffman树问题。
基本思路大体有了后，接下来是对程序编写工作，程序初步形成后，对其测试，发现了某些语法错误,修正后编译通过。

运营程序如下图所示

图5 程序主菜单
压缩：
在命令行下输入1对文献进行压缩，依照提示输入刚刚建文本文献（huffman.txt），和要生成压缩文献名称，按回车确认进行压缩。

图6 压缩文本

成功执行完毕后如下图所示。

图7 压缩完毕

恢复：
在命令行下输入2对本程序压缩文献进行恢复，依照提示输入待恢复文献名称和恢复后文献名称，按回车拟定，成功执行后如下图所示。

图7 文献恢复完毕

对比：
在命令行下输入3对恢复后文献和原文献对比，依照提示输入要对比文献，按回车确认，成功执行后如下图所示。

图8 文献恢复完毕

五、 测试成果
程序功能满足设计规定，测试未发现明显bug，详细可参见 五使用阐明。

程序如下:
// stdafx.h

#include <iostream> //输入输出头文献
#include <fstream> //文献操作类和办法
#include <queue> //队列容器
using namespace std;

const int leaf = 256; //最多也许浮现不同字符数
const long MAX = 99999999; //表达无穷大

//huffman树结点构造体
typedef struct HTnode

{
long weight; //记录结点权值
int parent; //记录结点双亲结点位置
int lchild; //结点左孩子
int rchild; //结点右孩子
int *code; //记录该结点huffman编码
int codelen; //记录该结点huffman编码长度

//初始化结点，令其权值为无穷大，无双亲及左右孩子
HTnode()
{
weight = MAX;
parent = -1;
lchild = -1;
rchild = -1;
codelen = 0;
}
}HTnode;

//##############################################################

//huffmanTree.h

//huffman树类
class huffmanTree
{
public:
huffmanTree();
virtual ~huffmanTree();
bool count(char *input); //压缩时记录各字符浮现次数，将其写入相应结点权值
void create(); //压缩时依照各结点权值构造huffman树
void code(); //压缩时，运用建好huffman树计算每个字符huffman编码
void printcode(); //列出每个字符huffman编码
void addbit(int bit); //压缩时对一种未满8个bitbyte中加入一种bit
void resetbyte(); //将byte清空
bool compress(char *input，char *output); //压缩函数 成功执行返回 true 失败 false
bool decompress(char *input，char *output); //恢复函数 成功执行返回 true 失败 false
void compare(char *input，char *output); //将原文献与压缩后文献比较
void compare2(char *input，char *output); //将原文献与恢复后文献比较
private:
int root; //记录根结点位置
int leafnum; //记录不同字符个数
HTnode HT[leaf*2-1]; //HTnode构造数组，用来表达huffman树，树最大结点个数不会超过leaf*2-1
char byte; //压缩文献时用来缓冲bit变量
int bitsnum; //byte中bit个数
int lacknum; //压缩到最后byte中bit不满8个时填充0个数
};

//##############################################################

//huffmanTree.cpp

#include "stdafx.h"
#include "huffmanTree.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

huffmanTree::huffmanTree()
{
//初始化成员变量
root = 0;
leafnum = 0;
byte = 0;
bitsnum = 0;
lacknum = 0;
}

huffmanTree::~huffmanTree()
{
for(int i=0；i<leaf；i++)
{
if(HT[i].codelen != 0)
delete []HT[i].code;
}
}

//记录各字符浮现次数
bool huffmanTree::count(char *input)
{
ifstream ifs;
char c;
ifs.open(input,ios::binary);
if(!ifs){
cout << "无法打开文献 " << input << '!' << endl;
return false;
}
while(ifs.get(c)){
if(HT[c+128].weight==MAX){ //若该字符是第一次浮现，先初始化权值
HT[c+128].weight = 0;
leafnum++;
}
HT[c+128].weight++; //权值+1
}
ifs.close();
return true;
}

//选权值最小两棵树构成新数
void huffmanTree::create()
{
for(int i=leaf；i<2*leaf-1；i++)
{
int loc1=-1，loc2=-1;
for(int j=0；j<i；j++){
if(HT[j].parent != -1)
continue;
if(loc1==-1 || HT[j].weight < HT[loc1].weight)
{
loc2 = loc1;
loc1 = j;
}
else if(loc2==-1 || HT[j].weight < HT[loc2].weight)
loc2 = j;
}
if(HT[loc1].weight==MAX || HT[loc2].weight==MAX || loc2==-1) //只剩一棵树，结束
break;
HT[i].weight = HT[loc1].weight + HT[loc2].weight;
//为了减少压缩文献中需要写入huffman树信息，商定小标小结点做为双亲结点左孩子
HT[i].lchild = loc1>loc2 ?loc2 ：loc1;
HT[i].rchild = loc1>loc2 ?loc1 ：loc2;
HT[loc1].parent = i; HT[loc2].parent = i;
root = i;
}
}

//列出每个字符huffman编码
void huffmanTree::printcode()
{
for(int i=0；i<leaf；i++)
{
if(HT[i].codelen!=0){
cout << "值为" << i-128 << "字符huffman编码：";
for(int j=0；j<HT[i].codelen；j++)
{
cout << HT[i].code[j];
}
cout << endl;
}
}
}

//压缩时，运用建好huffman树计算每个字符huffman编码
void huffmanTree::code()
{
for(int i=0；i<leaf；i++)
{
int len=0;
int loc=i;
while(HT[loc].parent!=-1)
{ //计算huffman编码长度
len++;
loc = HT[loc].parent;
}
HT[i].codelen = len;
HT[i].code = new int[len];
loc = i;
for(int j=len-1；j>=0；j--)
{ //从后往前找，记录结点huffman编码
if(loc==HT[HT[loc].parent].lchild)
HT[i].code[j] = 0;
else
HT[i].code[j] = 1;
loc = HT[loc].parent;
}
}
}

//压缩时对一种未满8个bitbyte中加入一种bit
void huffmanTree::addbit(int bit)
{
if(bit == 0)
byte = byte << 1; //若新增bit为0，则直接将byte按位左移
else
byte = ((byte << 1) | 1); //若新增bit为1，先将byte按位左移，再与1按位或运算
bitsnum++;
}

//将byte清空
void huffmanTree::resetbyte()
{
byte = 0;
bitsnum = 0;
}

//压缩函数 成功执行返回 true 失败 false
bool huffmanTree::compress(char *input，char *output)
{
if( !count(input) )
return false;

create();
code();
ifstream ifs;
ofstream ofs;
ifs.open(input,ios::binary);
ofs.open(output,ios::binary);
char c;
if(!ifs)
{
cout << "无法打开文献 " << input << '!' << endl;
return false;
}
if(!ofs)
{
cout << "无法打开文献 " << output << '!' << endl;
return false;
}

ofs.put(0); //预留一种字符，等压缩完后在该位置写入局限性一种bytebit个数
ofs.put(root-384); //将根节点位置-384写入（为使该值不超过char最大表达范畴）
for(int i=0；i<leaf*2-1；i++)
{ //写入每个结点双亲结点位置
if(HT[i].parent==-1) //若该节点没有双亲结点，则写入127(一种字节所能表达最大值)
ofs.put(127);
else //否则将双亲结点位置-384再写入（为使该值不超过char最大表达范畴）
ofs.put(HT[i].parent-384);
}

while(ifs.get(c))
{ //将字符huffman编码并加入byte中
int tmp = c+128;
for(int i=0；i<HT[tmp].codelen；i++)
{
addbit(HT[tmp].code[i]);
if(bitsnum==8)
{ //若byte已满8位，则输出该byte并将byte清空
ofs.put(byte);
resetbyte();
}
}
}
if(bitsnum!=0){ //解决最后未满8个字符byte，用0填充并记录填充个数
for(int i=bitsnum；i<8；i++)
{
addbit(0);
lacknum++;
}
ofs.put(byte);
resetbyte();
}
ofs.seekp(0,ios::beg); //将写指针移动到文献开头
ofs.put(lacknum); //写入最后一种字节缺失bit个数
ifs.close();
ofs.close();
return true;
}

//恢复函数 成功执行返回 true 失败 false
bool huffmanTree::decompress(char *input，char *output)
{
queue<char> q;
char c;
ifstream ifs;
ofstream ofs;
ifs.open(input,ios::binary);
ofs.open(output,ios::binary);
if(!ifs)
{
cout << "无法打开文献 " << input << '!' << endl;
return true;
}
if(!ofs)
{
cout << "无法打开文献 " << output << '!' << endl;
return false;
}

ifs.get(c);
lacknum = c; //读出最后一种字节缺失bit个数
ifs.get(c);
root = c+384; //读出根结点位置
for(int i=0；i<leaf*2-1；i++)
{ //建立各结点之间双亲孩子关系
ifs.get(c);
if(c==127)
continue;
else
{
HT[i].parent = c+384;
if(HT[c+384].lchild==-1)
HT[c+384].lchild = i;
else
HT[c+384].rchild = i;
}
}

int point = root;
//为了以便解决最后一种也许有缺失bit字节，先将读出数据放入队列
while(ifs.get(c))
q.push(c);

//还原文献过程
while(q.size()>1)
{ //尚未到最后一种字节
c = q.front();
for(int i=0；i<8；i++)
{
if(int(c&128)==0)
{
point = HT[point].lchild;
if(HT[point].lchild==-1 && HT[point].rchild==-1)
{
ofs.put(char(point-128));
point = root;
}
c = c << 1;
}
else
{
point = HT[point].rchild;
if(HT[point].lchild==-1 && HT[point].rchild==-1)
{
ofs.put(char(point-128));
point = root;
}
c = c << 1;
}
}
q.pop();
}
c = q.front(); //最后一种字节
for(i=0；i<8-lacknum；i++)
{
if(int(c&128)==0)
{
point = HT[point].lchild;
if(HT[point].lchild==-1 && HT[point].rchild==-1)
{
ofs.put(char(point-128));
point = root;
}
c = c << 1;
}
else{
point = HT[point].rchild;
if(HT[point].lchild==-1 && HT[point].rchild==-1)
{
ofs.put(char(point-128));
point = root;
}
c = c << 1;
}
}
q.pop();
ifs.close();
ofs.close();
return true;
}

//将原文献与压缩后文献比较
void huffmanTree::compare(char *input，char *output)
{
ifstream origin，compress;
origin.open(input,ios::binary);
compress.open(output,ios::binary);

if(!origin)
{
cout << "无法打开文献 " << input << '!' << endl;
return;
}
if(!compress)
{
cout << "无法打开文献 " << output << '!' << endl;
return;
}
double total1=0，total2=0;
char c;
while(origin.get(c))
total1++;
while(compress.get(c))
total2++;
cout << "原文献大小：" << total1 << " Byte" << endl;
cout << "压缩后大小：" << total2 << " Byte" << endl；
cout << "压缩率：" << total2/total1*100 << '%' << endl;
origin.close();
compress.close();
}

//将原文献与恢复后文献比较
void huffmanTree::compare2(char *input，char *output)
{
ifstream origin，decompress;
origin.open(input,ios::binary);
decompress.open(output,ios::binary);
double total1=0，total2=0;
char c1，c2;
bool dif = false;
while(origin.get(c1) && decompress.get(c2))
{
if(c1!=c2) //依次比较每个字节，不同则将dif标志设为true
dif = true;
total1++;
total2++;
}
while(origin.get(c1))
{ //若原文献尚有剩余数据，将dif设为true
dif = true;
total1++;
}
while(decompress.get(c2))
{ //若恢复文献尚有剩余数据，将dif设为true
dif = true;
total2++;
}
cout << "原文献大小：" << total1 << " Byte" << endl;
cout << "恢复文献大小：" << total2 << " Byte" << endl；
if(dif==true)
cout << "原文献与恢复文献不同!" << endl；
else
cout << "原文献与恢复文献相似!" << endl；
origin.close();
decompress.close();
}
//##############################################################

//huffman.cpp

#include "stdafx.h"
#include "huffmanTree.h"

void main()
{
int choice = 1;
char input[255]，output[255];
huffmanTree h;
while(choice)
{
cout<<" ***************************************************"<<endl;
cout<<" * 哈夫曼编码压缩恢复算法 *"<<endl;
cout<<" * *"<<endl;
cout<<" * 1)压缩 *"<<endl;
cout<<" * *"<<endl;
cout<<" * 2) 恢复 *"<<endl;
cout<<" * *"<<endl;
cout<<" * 3) 恢复文献与原文献对比 *"<<endl;
cout<<" * *"<<endl;
cout<<" * 4) 清屏 *"<<endl;
cout<<" * *"<<endl;
cout<<" * 5) 退出 *"<<endl;
cout<<" * *"<<endl;
cout<<" * 阐明：请您输入相应操作序号进行操作 *"<<endl;
cout<<" ****************************************************"<<endl;
cout<<">";
cin >> choice;
switch(choice)
{
case 1:
{
cout << "请输入待压缩文献名：";
cin >> input;
cout << "请输入压缩后文献名：";
cin >> output;
if( press(input,output))
{
h.printcode();
pare(input,output);
cout<<endl<<"文献压缩成功!"<<endl;
}else
{
cout<<endl<<"文献压缩失败!"<<endl;
}
}
break;
case 2:
{
cout << "请输入待恢复文献名：";
cin >> input;
cout << "请输入恢复后文献名：";
cin >> output;
if (h.decompress(input,output))
cout<<endl<<"文献恢复成功!"<<endl;
else
cout<<endl<<"文献恢复失败!"<<endl;
}
break;
case 3:
{
cout << "请输入原文献文献名：";
cin >> input;
cout << "请输入恢复文献文献名：";
cin >> output;
pare2(input,output);
}
break;
ca