数据结构之Haffman编码

2021年9月7日深夜，本地生活B2B与商家服务小组的帅小伙“全全”意外得到了一份只由’a’-‘f’，6种字母组成的种子文件，这个文件中一共有100w个字母，只要精通了这份种子文件对应的学习资源，就能够升职加薪，赢取白富美，走上人生巅峰。

平时就热爱分享的帅小伙“全全”当然不会忘了他的好基友“明明”，于是赶紧想把这份资源传给“明明”，但是不凑巧的是“明明”家的宽带是按流量收费的，刚摇到房的“明明”每个月的开销已经都贡献给了房贷，每多消耗一点流量的开销就会让“明明”在未来的日子生活质量严重降低。

“明明”的好基友“全全”当然不会让这种事情发生，他想起了之前在网上看到的一种算法，完美的减少了传输文件需要的流量大小，保障了“明明”未来日子的生活质量，你知道聪明的“全全”是怎么做的吗？

下面由我来给大家解密“全全”是怎么做的，在此之前，我们先来大概看一下正常情况下这么一个文件压缩是怎么做的，
像上面说的，这个文档只有6种字母，我们肯定不会使用诸如UTF-8这样的编码模式。

一般情况下我们会给每个字母一个唯一标识，这样，接收方就能根据这个唯一标识重新解析成原文，如下表所示

实际，在网络传输过程中，会转化成2进制的编码形式，如下表所示：

这样，实际传输这个文件需要的网络带宽开销为1000000 * 3 = 3000000位

这里可能有部分同学会有疑问，为什么a，b，c，d，e，f都使用定长长度编码，而不是下面这样可变长度编码

这样传输的实际平均位数就变成了2位，总位数就变成了2000000位。

我们继续来看这样的场景，发送方同时发送cb：

可以发现，接收方接收到101的时候，解析的时候就出现了歧义，可以解析成cb，也可以解析成f。

虽然根据上面的思路来压缩数据会导致数据解析出现歧义，但是整体的压缩的思路是正确的，我们需要减少某些字符的开销，并且为了出现歧义性，每个字符的编码都不能是其他编码的前缀。
那么减少哪些字符的编码长度收益最大呢，肯定是出现频率最大的字符编码越短越好。
这实际就是Haffman编码的基本思路。

看到上面的描述的时候，大家是不是会想起一种数据结构-二叉树：
1、根节点到叶子节点的路径，天然不是其他路径的前缀 。
2、叶子节点所在树深度越低，路径越短。

我们设树左子节点路径对应编码0，右字节点路径对应编码1，根节点到叶子节点路径编码的组合就是字符对应的变长编码。
那么我们如何构建这颗树呢？

首先，我们需要统计每个字符的出现频次，我们假设6种字符出现的频率如下表所示：

简单起见我们将平次都除以1W来演示，首先我们将频次从小到大排列

将权重最小的两个节点的权重相加，生成一个新的节点并重新按权重排序

继续将权重最小的两个节点的权重相加，生成一个新的节点并重新按权重排序

继续相同的操作就会得到如下结果

继续上面的操作

再继续相同的操作，最终我们就可以得到一颗最优二叉树

并且满足之前所有需求的每个字符对应的变长编码也可以得到了

我们可以计算得出压缩后需要传输的位数为
450000 1+1300003 +1200003 + 1600003 + 90000 4 + 50000 4 = 2240000，比未压缩钱节省了76W位的空间。