贪心算法 + 霍夫曼编码

贪心、分治、回溯、动态规划这 4 个算法思想，原理解释起来都很简单，但是要真正掌握且灵活应用，并不是一件容易的事。

贪心算法

贪心算法有很多经典的应用，比如霍夫曼编码、Prim 和 Kruskal 最小生成树算法、还有 Dihkstra 单源最短路径算法。

如何理解贪心算法？

假设我们有一个可以容纳 100kg 物品的背包，可以装以下 5 种豆子，每种豆子的总量和总价值各不相同，为了使背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？

                                     

实际上，我们只要先算一算每个物品的单价，按照单价由高到低来装就好了。依次是黑豆、绿豆、红豆、青豆、黄豆，所以我们可以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆。

这个问题的解决思路本质上借助的就是贪心算法。结合这个例子，总结了一下贪心算法解决问题的步骤：

第一步、

当我们看到这类问题的时候，首先应该联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制的情况下，期望值最大。类比刚才的例子，限制值就是总量不能超过 100kg，期望值就是物品的总价值，这组数据就是 5 种豆子。

第二步、

我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况，对期望值贡献最大的数据。类比刚才的例子，就是每次从剩下的豆子里面，选择单价最高的，也就是重量相同的情况下，对价值贡献最大的豆子。

第三步、

实际上，贪心算法解决问题的思路，并不总能给出最优解。

举个例子，在一个有权图中，我们从顶点 S 出发，找一条到顶点 T 的最短路径（路径中边的权值总和最小）。贪心算法的结局思路是，每次选择都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T，按照这种思路，找出最短路径：S->A->E->T ，路径长度是 1 + 4 + 4 = 9。显然不是最短的，因为最短的是：S->B->D->T，总长度是 2 + 2 + 2 = 6。

                               

为什么贪心算法在这个问题上不工作了呢，主要原因是，前面的选择会影响后面的选择。所以即便我们第一步选择最优的走法，但有可能因为这一步选择，导致后面每一次的选择都很糟糕，最终也自然和最优解无缘了。

霍夫曼编码

接下来看看霍夫曼编码是如何利用贪心算法来实现对数据压缩编码，有效节省数据存储空间的

假设我有一个包含 1000 个字符的文件，每个字符占 1 个 byte (1 byte = 8 bits)，存储这 1000 个字符就一共需要 8000 bits，那么有没有更加节省空间的存储方式呢？

假设我们统计发现，这 1000 个字符只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。而 3 个二进制 bit 就可以表示8 个不同的字符，所以为了尽量减少存储空间的存储空间，每个字符我们用 3 个二进制位来表示，比如：a（000）、b（001）、c（010）、d（011）、e（100）、f（101），那么存储这 1000 个字符只需要 3000bits 就可以了，比原来的存储节省了很多空间，那么还有没有更加节省空间的存储方式呢？

这个时候就要用到霍夫曼编码了。霍夫曼编码是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。

霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。霍夫曼编码试图用这种不等长的编码方法，来进一步增加压缩的效率。

如何给不同频率的字符选择不同长度的编码呢，根据贪心的思想，我们可以把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。

对于等长的编码来说，压缩起来很简单。比如刚才那个例子，用 3 个 bit 表示一个字符。在解压缩的时候，每次从文本中读取 3 位二进制，然后翻译成对应的字符，但是，霍夫曼编码是不等长的，每次应该读取 1 位，还是 2 位还是 3 位等等来解压缩呢，这个问题就导致霍夫曼编码解压缩起来比较复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间不会出现某个编码是另一个编码前缀的情况。

假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f ，我们把它们分别编码成下面这样子，任何一个字符的编码都不是另一个的前缀，在解压缩的时候，每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会有歧义。经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。

                                     

尽管霍夫曼编码的思想并不难理解，但是如何根据字符出现频率的不同，给不同的字符进行不同长度的编码呢？这里的处理稍微有些技巧。

1. 我们把每个字符看作一个节点，并且辅带着把频率放到优先级队列中。

2. 我们从队列中取出频率最小的两个节点 f（20）、e（30）

3. 然后新建一个节点 x（50），把频率设置为两个节点的频率之和，并把这个新节点 x（50）作为  f（20）和 e（30）的父节点。

4. 最后再把  x（50）放入到优先级队列中。重复这个过程，直到队列中没有数据。

                          

         5. 现在我们统一给每一条边画一个权值，指向左子节点的边我们通通标记为 0，指向右子节点的边，我们通通标记为 1，那么从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。