贪心算法——Huffman 压缩编码的实现

daklqw 2019-06-29

1. 如何理解 “贪心算法”

假设我们有一个可以容纳 100 Kg 物品的背包,可以装各种物品。我们有以下 5 种豆子,每种豆子的总量和总价值都各不相同。怎样装才能让背包里豆子的总价值最大呢?

贪心算法——Huffman 压缩编码的实现

这个问题其实很简单,我们只需要计算出每种豆子的单价,然后按照单价从高到低依次来装就好了。单价从高到低排列为:黑豆、绿豆、红豆、青豆和黄豆,因此我们往背包里装 20 Kg 黑豆、30 Kg 绿豆和 50 Kg 红豆。

实质上,这就是贪心算法的思想,用贪心算法解决问题的步骤一般是这样的。

第一步,当我们看到这类问题的时候,首先要联想到贪心算法。针对一组数据,我们定义了限制值和期望值,希望选出几个数据,在满足限制值的情况下,期望值最大。在刚才的问题中,限制值就是重量不超过 100 Kg,期望值就是豆子总价值。

第二步,我们尝试看下这个问题是否可以用贪心算法解决。每次选择当前情况下,在对限制值同等贡献的情况下,对期望值贡献最大的数据。上例中,就是选取单价最高的豆子,也就是重量相等情况下对总价值贡献最大的豆子。

第三步,我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下,举几个例子验证一下就可以了,严格证明贪心算法的正确性,需要涉及比较多的数学推理,非常复杂。从时间角度来看,大部分能用贪心算法解决的问题,其正确性都是显而易见的,也不需要严格的证明。

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

在下面的有权图中,我们需要找到一条从顶点 S 出发到顶点 T 的最短路径,使得路径中边的权重和最小。贪心算法的思路是每次选择一条和当前顶点连接的权重最小的边,最终答案是 S->A->E->T,权重和为 9。

贪心算法——Huffman 压缩编码的实现

但是,最优解实际上是 S->B->D->T,权重和为 6。在这个问题上,贪心算法不工作的原因主要是,前面的选择会影响后面的选择。一旦第一步选择了顶点 S 到顶点 A,第二步我们就和顶点 B、C 无关了。即使第一步最优,但是若因为这个选择后面的选择都很糟糕,那总体上也就不会取得最优解了。

2. 贪心算法实战分析

2.1. 分糖果

假设我们有 m 个糖果要分给 n 个孩子,因为糖果少孩子多(m<n),所以糖果只能分给一部分孩子。每个糖果的大小不等,每个孩子对糖果的需求也不同,只有糖果的大小大于等于孩子对糖果的需求时,孩子才能得到满足。如何分配糖果,才能尽可能地满足最多数量的孩子呢?

对于一个孩子来说,如果小的糖果可以满足,我们就没必要用更大的糖果,这样更大的糖果就可以用来满足需求更大的孩子。另一方面,对糖果需求小的孩子更容易满足,因此我们可以从需求小的孩子开始分配糖果,因为满足一个需求小的孩子和满足一个需求大的孩子,对我们结果的贡献是一样的。

所以,我们就可以从剩下的孩子中,找出一个需求最小的,然后发给他剩余糖果中能满足他需求的最小的糖果。这样的分配方案,最后就能满足最多数量的孩子。

2.2. 钱币找零

假设我们有面值分别为 1 元、2 元、5 元、10 元、20 元、50 元、100 元的钞票若干,现在要用这些钱来支付 K 元,最少要用多少张纸币呢?

在生活中,我们肯定首先用面值最大的来支付,如果不够,我们继续用更小一点面值的,以此类推,直到最后满足为止。在贡献相同期望值(纸币数量)的情况下,我们肯定希望多贡献点金额,这样就可以让纸币数更少,这就是一种贪心的思想。

2.3. 区间覆盖

假设我们有 n 个区间,区间的起始端点分别为 [l1, r1],[l2, r2],[l3, r3],……,[ln, rn]。我们从这 n 个区间中选出一部分区间,这部分区间满足两两不相交(端点相交不算),最多能选出多少个区间呢。

贪心算法——Huffman 压缩编码的实现

这个问题的解决思路是这样的,假设这 n 个区间的最左端点是 lmin,最右端点是 rmax。那么这个问题就相当于,我们选择几个不相交的区间,从左到右将 [lmin, rmax] 覆盖上。我们按照起始端点从小到大的顺序对这 n 个区间进行排序,每次选择的时候,左端点和前面已经覆盖的区间不重合而右端点又尽量小的区间,就能让剩下的未覆盖区间尽量大,从而就可以放置更多的区间。

贪心算法——Huffman 压缩编码的实现

这实际上就是一种贪心的选择方法,而且这种处理思想在任务调度、教师排课等问题中都有用到。

3. Huffman 压缩编码

假设有一个包含 1000 个字符的文件,每个字符占 1 个字节 8 位,那么存储这个文件就需要 8000 bits。如果通过统计分析我们发现这 1000 个字符只包含 6 个不同的字符,假定它们为 a, b, c, d, e, f。那我们只用 3 个二进制位就可以表示 8 个不同的字符,所以存储 1000 个字符就只需要 3000 bits 了,比原来省了很多空间。那还有没有更加节省空间的存储方式呢?

霍夫曼编码就要登场了。霍夫曼编码是一种非常有效的编码方式,广泛用于数据压缩中,其压缩率通常在 20% - 90% 之间。霍夫曼编码不仅会考察文本中有多少个不同字符,还会考察每个字符出现的频率,根据频率的不同,选择不同长度的编码。根据贪心的思想,我们可以把出现频率比较多的字符,用稍微短一点的编码,而对出现频率比较少的字符用稍微长一些的编码。

对于等长的编码来说,我们解压缩起来很简单,每次从文本中读取固定长度的二进制码,然后翻译成对应字符即可。但是,霍夫曼编码是不等长的,我们每次应该读取多少位的二进制来进行解码呢?为了避免解码过程出现歧义,霍夫曼编码要求各个字符的编码之间,不会出现某个编码是另一个编码前缀的情况。

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

贪心算法——Huffman 压缩编码的实现

那霍夫曼编码是如何根据字符出现频率的不同,给不同的字符进行不同长度的编码的呢?

我们把每个字符看作一个节点,并且附带着把频率放到优先级队列中。然后,从队列中取出频率最小的两个子节点 A、B,新建一个节点 C,使其频率为 A、B 两个节点的频率之和,并把这个新节点 C 作为 A、B 节点的父节点。最后,再把 C 节点放入到优先级队列中,重复这个过程,直到队列中没有数据为止。

贪心算法——Huffman 压缩编码的实现

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

贪心算法——Huffman 压缩编码的实现

参考资料-极客时间专栏《数据结构与算法之美》

获取更多精彩,请关注「seniusen」!
贪心算法——Huffman 压缩编码的实现

相关推荐