数据结构 -- 树的应用,哈夫曼编码
时间：2010-07-15 来源：bluedrum
Andrew Huang [email protected]
在学习完二叉树后,我们自然会找一些应用来演示树的应用,其中,哈夫曼编码是用树来进行一个典型应用.
哈夫曼编码(Huffman Encoding) 是最古老，以及最优雅的数据压缩方法之一。它是以最小冗余编码为基础的，即如果我们知道数据中的不同符号在数据中的出现频率，我们就可以对它用一种占用空间最少的编码方式进行编码，这种方法是，对于最频繁出现的符号制定最短长度的编码，而对于较少出现的符号给较长长度的编码。哈夫曼编码可以对各种类型的数据进行压缩，如应用在JPEG图像的算法很多领域.
在这里我们采用一个文本文件来演示哈夫曼编码的.为了说明问题,这个文本文件是高度简化,这样程序会变得相对简单,比较好理解.
1.文件内容只会出现ASCII字符.即字符集里的字符总数不超过255.
2.用一串两进制数比如 10,110,1110,0 来代表文件里字符.每个字符有一个独立编码.而且是一种特殊前缀的编码,即任一个编码都不是另外一个编码的前缀.
3.统计文本文件中各个字符出现频率,出现频率最高的字符分配最短的号码.
4.最后把整个文件翻译成二进制文本0,1的文件.再按8个bit组成一个byte方式形成新的二进制文件.因为出现最多次数字符的长度明显没有超过8bit,绝大部分情况下,经过这样处理后的文件会比原来文件尺寸要小.
其中第4步需要构造N个二叉树进行翻译.而且如果只有最终翻译后的文本.而没有这一个哈夫曼树将无法还原出原来的文件.因此哈夫曼的第二个应用是用来做加解密.
一.哈夫曼编码过程
--------------------------------------------------
构建哈夫曼的标准过程如下。
a）检查字符在数据中的出现频率。
b）构建哈夫曼树。
c）创建哈夫曼编码表。
d）生成压缩后结果，由一个文件头和压缩后的数据组成。
我们首先看如何实现这些步骤。
a)因为只有256字符，因此我们建一个256个大数组。数组每一项要记录，每个字符出现次数，以及每一个字符对应的huffman编码。 然后把文件打开，统计字符出现次数，分别记在数组当中。
b）构建哈夫曼树（huffman Tree）；
哈夫曼编码的核心部分就在于构建哈夫曼树，它是一个二叉树。同时它的贪心策略也现在构建哈夫曼树的方法中。
哈夫曼树用下面的方式构建：首先，我们把所有出现的字符作为一个单节点数，在节点上标识一个数字代表字符出现频率。
例如如果我们要对字符串“aabbbccccdddddd" 进行编码，则字符频率表如下所示：
----------------------------
| a b c d |
----------------------------
| 2 3 4 6 |
----------------------------
一共有4个字符出现，因此最初我们有 4 个单节点的树。然后就是体现贪心策略之处，每次我们选取具有最低频率的两个树，并将他们合并，把两个树的频率相加，赋给新树的根节点。重复这个步骤，直到最后只剩下一棵树，就是最终我们需要的哈夫曼树。合并过程如下图所示：
最终的编码方式是，每个 叶子节点代表了一个在原文中出现的字符。每个字符的编码就是从根节点到该叶子节点的路径。由于字节中的每一位由0，1两种状态，这也正是二叉树尤其重要和常用的原因。从根节点出发，如果进入左子树，则在编码上填0，如果进入右子树，则在编码上填1，直到到达叶子节点，就完成了该字符的编码。从上面的哈夫曼树可见，最终的哈夫曼编码表如下：
=======================
字符 频率 编码 码长
------------------------------------
a 2 110 3
b 3 111 3
c 4 10 2
d 6 0 1
========================
哈夫曼编码是一种前缀码，即任一个字符的编码都不是其他字符编码的前缀。从我们的编码过程中可以很容易看到这一点，因为所有字符都是哈夫曼树中的叶子节点，所以每个字符所在的叶子节点的路径都不会有重叠部分（即代表字符的节点之间不存在以下关系：某节点是另一节点的祖先或后代）。这个特征能够保证解码的唯一性，不会产生歧义（在解码时只需要找到叶子节点即可完成当前字符的解码）。
可以看出，出现频率最高的字符，使用最短的编码，字符出现频率越低，编码逐渐增长。这样不同字符在文档中出现的频率差异越大，则压缩效果将会越好。字符的出现频率差异影响了它们最终在哈夫曼树中的深度。
因此字符出现频率越大，我们希望给它的编码越短（在哈夫曼树中的深度越浅），即我们希望更晚的将它所在的树进行合并。反之，字符频率越低，我们希望给他的编码最长（在哈夫曼树中的深度越深），因此我们希望越早的将它所在的树进行合并。因此，哈夫曼编码的贪心策略就体现在合并树的过程中，我们每一次总是选择根节点频率最小的两个树先合并，这样就能达到我们所希望的编码结果。
构建哈夫曼树的步骤如下：
a）把所有出现的字符作为一个节点（单节点树），把这些树组装成一个优先级队列；
b）从该优先级队列中连续抽取两个频率最小的树分别作为左子树，右子树，将他们合并成一棵树（频率=两棵树频率之和），然后把这棵树插回队列中。
c）重复步骤b，每次合并都将使优先级队列的尺寸减小1，直到最后队列中只剩一棵树为止，就是我们需要的哈夫曼树。
d)合并编码
合并编码即把转换出来哈夫曼编码合并成8bit为一个单位的byte.这样使用文件长度达到最短。
上例中，完整输是
|
当我们使用上面的代码对“aabbbccccdddddd”进行哈夫曼编码时，程序产生的输出如下：
size of input: 15 number of characters: 4
character encodings:
compressed string: (size: 32 bit) //注意后三个Bit 不携带信息，仅为了补齐成 8 Bits 整数倍；
size of compressed string: 15 uncompressed string: (size: 120 bit) aabbbccccdddddd |
参考资料
哈夫曼编码过程引自 http://www.cnblogs.com/hoodlum1980/archive/2010/02/06/1665112.html
相关阅读 更多 +
