前言:
最基本的压缩编码方法——赫夫曼(huffman)编码。
在了解赫夫曼编码之前,我们必须了解一下赫夫曼树,赫夫曼编码就是基于赫夫曼树实现的。
相关视频——【C语言描述】《数据结构和算法》_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
相关书籍——《大话数据结构》
我的小站——半生瓜のblog,同步更新哦。
@TOC
1.赫夫曼树的定义与原理
-
结点的路径长度
- -从根节点到该结点的路径上的连接数。
-
数的路径长度
- -树中每个叶子结点的路径长度之和。
-
结点带权路径长度
- -结点的路径长度与结点权值的乘积。
-
树的带权路径长度(WPL)
- -是树中所有叶子结点的带权路径长度之和。
-
(数结点间的连线相关的数叫做权,Weight)
其中:带权路径长度(WPL)最小的二叉树叫做赫夫曼树。
带权路径长度(WPL)的值越小,说明构造出来的二叉树性越优。
2.构造赫夫曼树的过程
初识森林
在森林中选出两棵根节点的权值最小的二叉树,小的放左边,大的放右边。
合并两颗选出的二叉树,增加一个新结点作为新二叉树的根,权值为左右孩子的权值之和。
再从剩下的森林里面选出权值最小的二叉树,如果比第一次合并的结点权值小就放左边,反之,放右边。
再次进行合并。
第二次合并完成,第三次合并同理。
合并完成,这个二叉树就是赫夫曼树。
3.赫夫曼编码原理
补充:
赫夫曼研究这种最优树的目的是为了解决当年远距通信(主要是电报)的数据传输的最优化问题。
名词解释:
- 定长编码
- -像ASCII编码,用八位二进制数来表示一个字符。
- 变长编码
- -单个编码的长度不一致,可以根据整体频率来调节。
- 前缀码
- -所谓的前缀码,就是没有任何码字是其他码字的前缀。
编码过程(encode):还是利用上面的赫夫曼二叉树。
上图为构造赫夫曼树的过程权值显示。
下图为将权值左支改为0,右支改为1后的赫夫曼树。
我们对这4个字母(ABCD)用其从树根到叶子所经过路径0或1来进行编码。
例如原文字内容是ABCD。
原编码二进制串:000001010011(共12个字符)
新编码二进制串:010110111(共9 个字符)
也就是说我们的数据被压缩了,节约了25%的存储空间或者传输成本,随着字符的增加和字符权重的不同,这种压缩会更加显出其优势。
解码过程(decode):
发送方和接收方必须要约定好同样的赫夫曼编码规则,由约定好的赫夫曼树可以成功解码。
评论区