# 赫夫曼编译码器开发
## 实验目的及要求
考查二叉树存储表示及其基本操作实现。
赫夫曼树的建立。
赫夫曼树编码和译码算法。
系统功能:从文件或键盘读入一串电文字符,实现赫夫曼编码和译码。
密码文件以文件的形式进行存放。
## 算法原理概述
Huffman树
Huffman树简介
### 基本概念
路径:树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度:路径上的分支数目称作路径长度。
树的路径长度:从树根到每一个结点的路径长度之和。
结点的带权路径长度:在一棵树中,如果其结点上附带有一个权值,通常把该结点的路径长度与该结点上的权值的乘机称为节点的带权路径长度。
树的带权路径长度:树中所有叶子结点的带权路径长度之和,通常记作
WPL=
![](https://www.writebug.com/myres/static/uploads/2022/12/29/8934bf91452b196faacb9248e0cea790.writebug)
Huffman树的概念
假设有n个权值{w1,w2,…,wn},试构造一颗有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树称做最优二叉树或Huffman树。
Huffman树是一类带权路径最短的树,又称最优二叉树。
例如:(a)、(b)、(c)为3棵二叉树,都有4个叶子结点a、b、c、d,分别带权7、5、2、4,他们的带权路径长度分别为:
- WPL=7×2+5×2+2×2+4×2=36
- WPL=7×3+5×3+2×1+4×2=46
- WPL=7×1+5×2+2×3+4×3=35
![](https://www.writebug.com/myres/static/uploads/2022/12/29/e9e5ee4de0f8ff52d2255f3094e761eb.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/12/29/99ca0716077b0aa85a4c6152f07f8eba.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/12/29/bbb01b08d423ee5f70a9191f8a3d945f.writebug)
### Huffman树的构造
根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根节点,其左右子树均空。
在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和。
在F中删除这两棵树,同时将新得到的二叉树加入F中。
重复(2)和(3),直到F只含一棵树为止。这棵树便是Huffman树。
例如:图(a1)、(b1)、(c1)、(d1)展示了Huffman树(c)的构造过程。其中,根节点上标注的数字是所赋的权。
![](https://www.writebug.com/myres/static/uploads/2022/12/29/40e54843e42cd650d397172dff42cdcc.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/12/29/7bfaf58103a537541ac007208f6618b3.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/12/29/35b8c939ec1b9b0f7f464daca2ff07b1.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/12/29/18de043de11cd1b1090197c867deaaf3.writebug)
### Huffman编码
### Huffman编码简介(来源于百度百科)
赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就称Huffman编码。
若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码称做前缀编码。
### Huffman编码的实现
我们这里利用二叉树来设计二进制的前缀编码。假设有一棵下图(2a)所示的二叉树,其4个叶子结点分别表示A、B、C、D这4个字符,且约定左分支表示字符’0’,右分支表示字符’1’,则可以从根节点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。可以证明,如此得到的必为二进制前缀编码。如图(2a)所得A、B、C、D的二进制前缀编码分别为0、10、110和111。
![](https://www.writebug.com/myres/static/uploads/2022/12/29/d56c4781ac19ccce65400cbd3010a8b5.writebug)
假设每种字符在电文中出现的次数为wi,其编码长度为li,电文中只有n种字符,则电文总长为
![](https://www.writebug.com/myres/static/uploads/2022/12/29/ad97d70a2548ae9cdab8ab93d0dea4e6.writebug)
。对应到二叉树上,若置wi为叶子结点的权,li恰为从根到叶子的路径长度。则
![](https://www.writebug.com/myres/static/uploads/2022/12/29/7b4594c589724ff94034891e2748c31a.writebug)
恰为二叉树上带权路径长度。由此可见,设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权,设计一棵Huffman树的问题,由此得到的二进制前缀编码便称为Huffman编码。
由于Huffman树中没有度为1的结点,则一棵有n个叶子结点的Huffman树共有2n-1个结点,可以存储在一个大小为2n-1的一维数组中。由于在构成Huffman树之后,为求编码需从叶子结点出发走一条从叶子到根的路径;而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言,既需知双亲的信息,又需知孩子结点的信息。由此,设定下述存储结构:
```c++
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode,*HuffmanTree; //动态分配数组存储Huffman树
typedef char **HuffmanCode; //动态分配数组存储Huffman编码表
```
## Huffman译码
### Huffman译码简介
哈夫曼树译码是指由给定的代码求出代码所表示的结点值,它是哈夫曼树编码的逆过程。
从文本中,依次读入原先编码的Huffman编码,再利用已经存储的Huffman树结构,根据编码信息往下进行搜索,则可得该Huffman编码所对应的字符。
### Huffman译码的实现
Huffman译码的基本思想是:从根结点出发,逐个读入文件中的二进制代码;若代码为0则走向左孩子,否则走向右孩子;一旦到达叶子结点,便可译出代码所对应的字符。然后又重新从根结点开始继续译码,直到该二进制文件结束。
操作步骤如下:
读入一个字符,判断是’1’还是’0’
从根节点出发,出发走到该字符所对应的分支
若该分支节点没有左孩子和右孩子,则输出该节点所对应的字符;若有,则继续执行步骤(2)直至找到
若已经译出一个字符,则将数组清空,重新开始步骤(1)
```c++
while (!feof(encodefile)) {
c = fgetc(encodefile);
if (word == text_length) break;
if (c == '0') q = HT[q].lchid;
else if (c == '1') q = HT[q].rchild;
if (HT[q].lchid == 0 && HT[q].rchild == 0) {
fputc(HT[q].ASCII_CODE, decodefile);
q = 2 * char_number - 1;
word++;
}
}
```
### huf文件编码算法
对二进制文件的写入
在Windows操作系统中,二进制以8位(1字节)为单位存储,8位二进制无符号数的表示范围为20-1~27-1,即0~255。而0~255能够恰好对应ASCII码对照表中的所有256个字符,因此,在压缩存储Huffman编码时,每一次可以取8位0/1编码,将其对应到一个字节的每一个bit位上,再将这个字节转换成ASCII码值,在文件中写入其对应的字符。
### Huffman编码的实现
在进行Huffman编码压缩时,每一次取8位字符’0’或’1’, 将其对应到一个字节的每一个bit位上,再将这个字节转换成ASCII码值,在文件中写入其对应的字符。
例如:
假设之前已由Huffman编码得到A=0,B=10,C=110,D=111。则字符串“ABCD……”所对应的Huffman编码为010110111……。第一次取前8位01011011,将其对应写入1字节的8个bit位上,即n=(01011011)2=(91)10�
基于C++开发的(控制台)赫夫曼编译码器【100011578】
版权申诉
104 浏览量
2023-04-06
09:45:24
上传
评论
收藏 873KB ZIP 举报
神仙别闹
- 粉丝: 2687
- 资源: 7658
最新资源
- 演讲稿.txt
- 基于Python的爬虫案例-软科中国大学TOP200
- 碳排放权交易明细数据(2024年5月更新).xlsx
- 特殊文件属性命令chattr和lsattr
- HTML、CSS 和 JavaScript动态、交互式的网页 .txt
- b0cd8f9b23d4e5e381b6a8fd8ee0e907.JPG
- ff45d61c5900e45634cf4cac6cff61a1.JPG
- springboot.springboot.springboot.springboot.txt
- linux-进程与服务管理
- 毕业设计基于Django+MySQL+Redis实现简单的天气预报系统python源码.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈