概述
哈夫曼在通信领域有很多的用途，将需要传输的数据转换01串，相比直接传输，极大提高了传输的速率，同时还在数据压缩的重要方法。而本篇主要介绍的是哈夫曼压缩算法。
哈夫曼压缩思路
假设一字符串是，“abcabcabcabcabcabcddddddddd”，统计各字符出现的次数如下表。
| 字符 | 出现次数 |
|---|---|
| a | 6 |
| b | 6 |
| c | 6 |
| d | 9 |
按照一搬的存储方法，一个字符占用一个字节，那么共花费(6+6+6+9)*sizeof(char) = 27字节，27字节确实不算什么，但是如果是海量数据的时候，就可能要考虑存储空间的问题了。
来看看哈夫曼压缩算法是怎么做的，同样是上面的例子，我们试着建立哈夫曼树，出现的次数就当做是权重，出现的次数越多的话，越靠近根节点，那么编码越短，如下图：
image
于是上面的“abcabcabcabcabcabcddddddddd”，就可以转化为“0001,1000,0110,0001,1000,0110,0001,1000,0110,1111,1111,1111,1111,11”，注意这里采用的按位存储的，也就是说0和1都是位，而非char型。那么之前的27字节就被我们转换成了7个字节（7字节不足，不足的话就补零），而这就达到了压缩的效果。
所以总结一下：利用哈夫曼树编码的特点，权重越大越靠近根节点，得到的编码就越短的原理，而如果把字符出现次数作为权重的话，文本当中出现次数最多的字符就被压缩成了很短的编码。
哈夫曼压缩算法（Huffman compression）详解
众所周知，计算机存储数据时，实际上存储的是一堆0和1（二进制）。
如果我们存储一段字符：ABRACADABRA!
那么计算机会把它们逐一翻译成二进制，如A：01000001；B: 01000010; !: 00001010.
每个字符占8个bits, 这一整段字符则至少占12*8=96 bits。
但如果我们用一些特殊的值来代表这些字符，如：
image
图中，0代表A; 1111代表B；等等。此时，存储这段字符只需30bits，比96bits小多了，达到了压缩的目的。
我们需要这么一个表格来把原数据翻译成特别的、占空间较少的数据。同时，我们也可以用这个表格，把特别的数据还原成原数据。
首先，为了避免翻译歧义，这个表格需满足一个条件：任何一个字符用的值都不能是其它字符的前缀。
我们举个反例：A: 0; B: 01;这里，A的值是B的值的前缀。如果压缩后的数据为01xxxxxx,x为0或者1，那么这个数据应该翻译成A1xxxxxx, 还是Bxxxxxxx?这样就会造成歧义。
然后，不同的表格会有不同的压缩效果，如：
image
这个表格的压缩效果更好。
那么我们如何找到最好的表格呢？这个我们稍后再讲。
为了方便阅读，这个表格是可以写成一棵树的：
image
这棵树的节点左边是0，右边是1。任何含有字符的节点都没有非空子节点。（即上文提及的前缀问题。）
这棵树是在压缩的过程中建成的，这个表格是在树形成后建成的。用这个表格，我们可以很简单地把一段字符变成压缩后的数据，如：
原数据：ABRACADABRA!
表格如上图。
令压缩后的数据为S；
第一个字符是A，根据表格，A：11，故S=11;
第二个字符是B，根据表格，B：00，故S=1100;
第三个字符是R，根据表格，R：011，故S=1100011;
如此类推，读完所有字符为止。
压缩搞定了，那解压呢？很简单，跟着这棵树读就行了：
image
压缩后的数据S=11000111101011100110001111101
记住，读到1时，往右走，读到0时，往左走。
令解压后的字符串为D；
从根节点出发，第一个数是1，往右走：
image
第二个数是1，往右走：
image
读到有字符的节点，返回此字符，加到字符串D里。D:A;
返回根节点，继续读。
image
第三个数是0，往左走：
image
第四个数是0，往左走：
image
读到有字符的节点，返回此字符，加到字符串D里。D:AB;
返回根节点，继续读。
第五个数是0，往左走：
image
第六个数是1，往右走：
image
第七个数是1，往右走：
image
读到有字符的节点，返回此字符，加到字符串D里。D:ABR;返回根节点，继续读。
如此类推，直到读完所有压缩后的数据S为止。压缩与解压都搞定了之后，我们需要先把原数据读一遍，并把每个字符出现的次数记录下来。如：
ABRACADABRA!中，A出现了5次;B出现了2次;C出现了1次;D出现了1次;R出现了2次;!出现了1次。
理论上，出现频率越高的字符，我们给它一个占用空间越小的值，这样，我们就可以有最佳的压缩率。
简介哈夫曼压缩文件DL结构
前一段时间在接触位图的时候被位图结构触动了，感觉它存储得有条理，于是萌生了为哈夫曼压缩文件定义一个存储结构，称之为哈夫曼压缩文件DL结构。关键是要统一，这篇博文用的是一种结构，另一篇用的又是另一种，纷杂的样式会让初学者发晕，所以统一结构对于学习哈夫曼压缩文件会有很大的帮助。
DL结构组成部分：
- 节点个数-用以规定创建哈夫曼树节点个数，以便读入节点域；
- 节点域-用以创建哈夫曼树和产生字符编码；
- 源文件字符数-在解压的时候有用；
- 编码长度（以位为单位）-源文件编码的总长度，以位为单位；
- 编码域-存储所有字符编码的存储域。
为了便于让你不看文字就能明白，看下图，按着这种结构就相当于有了大概的思路。
image
image
上面就是哈夫曼算法详解，更多Android性能优化系列可以参考《Android性能优化学习手册》里面内容包含了7个以上的核心优化学习文档。
文末
哈夫曼算法的主要思想是：
①首先遍历要处理的字符串，得到每个字符的出现的次数；
②将每个字符（以其出现次数为权值）分别构造为二叉树（注意此时的二叉树只有一个节点）；
③取所有二叉树种种字符出现次数最小的二叉树合并为一颗新的二叉树，新二叉树根节点的权值等于两个子节点的权值之和，新节点中的字符忽略；
④重复过程③直到所有树被合并为同一棵二叉树
⑤遍历最后得到的二叉树，自顶向下按路径编号，指向左节点的边编号0，指向右节点的边编号1，从根到叶节点的所有边上的0和1链接起来，就是叶子节点中字符的哈夫曼编码。
网友评论