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