绪论
最近在写PNG文件的编码解码,因为PNG的数据压缩使用的是DEFLATE压缩,因此也就有了这篇文章,DEFLATE算法本质是范式Huffman算法和LZ77算法的结合体,Huffman算法及LZ77算法本身并不复杂,但在RFC1951中,一些细节问题讲解并不详细,因此deflate实现的麻烦点主要在数据结构的处理上,这也是本文讨论的重点,笔者将内容尽可能整理到比较简略的模式,以便各位看官能够快速的恰到RFC1951中的一些坑点及关键点,同时,本文讨论的更多是原理结构上的问题,因此,如何达到压缩的最优值,并不在本文的讨论范围内，最后deflate、inflate的代码你都可以在PainterEngine中的PX_RFC1951.x PX_Huffman.x PX_LZ77.x中找到。
范式Huffman树
Huffman树是什么如何构造Huffman树并不在本文的讨论范围之内，在网上应该很容易找到相关的资料，因此在本文中笔者就不再复述了，我们举一个简单的例子，例如我们对序列
${a,b,c,c,c,d,d,d,d,d,d}$
进行编码,首先我们计算每个值出现的频率
依据这个频率,我们建立一个典型的Huffman树
如果我们将左边以0编码,右边以1进行编码,那么,每个字母(Symbol)都可以编码为一个"Code" ,那么,huffman树可以构造成一个类似下表的结构:
| symbol | code | bit(s) length |
|---|
| a | 000 | 3 |
| b | 001 | 3 |
| c | 01 | 2 |
| d | 1 | 1 |
因此,如果是常规的huffman树,我们需要保存huffman树每个symbol对应的code,和code对应的位长度(bits length)
那么什么是范式huffman呢,范式huffman本质是确定了code的一个结构,就是把code的内容规范化,比如上面这个huffman树,a是000,b是001,那么如果换成a是001,b是000,这样重新构造的huffman树也是完全成立的,但范式huffman树说不行,a可以通过它的bits length计算出来,它的值一定是确定的,那么我们就可以通过只保存bits length来重建huffman树,省了不少空间
| 常规huffman树 | 范式huffman树 |
|---|
| 需要保存code和bits length | 只需要bit length就行了,因为code可以通过bit length计算出来 |
那么,剩下的问题就是如何通过bit length来还原code了,在这里,RFC1951还是说的很清楚了,我引用什么的例子重新计算一遍:
1.首先,我们保存了a,b,c,d的位长(bits length),它们分别是(3,3,2,1)
2.然后,我们计算位长出现的频率,比如位长3出现2次,2和1只出现1次,我们根据这个构造下表
| 位长(bits length) | 出现次数(bl_count) |
|---|
| 0 | - |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
3,然后我们需要构造next_code,next_code构造如下代码(MAX_BITS为最大位长,比如这里是3)
code = 0;
bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++)
{
code = (code + bl_count[bits-1]) << 1;
next_code[bits] = code;
}
这样我们就可以构造出next_code了
| 位长(bits length) | 出现次数(bl_count) | next_code |
|---|
| 0 | - | - |
| 1 | 1 | 0 |
| 2 | 1 | 2 |
| 3 | 2 | 6 |
最后,我们依据位长出现频率构造出code(其实就是next_code根据频次累加),代码如下
for (n = 0; n <= max_code; n++)
{
len = tree[n].Len;
if (len != 0) {
Code[n] = next_code[len];
next_code[len]++;
}
}
| symbol | 位长(bits length) | code | code的二进制 |
|---|
| a | 3 | 6 | (110) |
| b | 3 | 6+1=7 | (111) |
| c | 2 | 2 | (10) |
| d | 1 | 0 | (0) |
于是,我们的范式huffman树,仅仅需要保存bit length就能够还原了,大大节省了存储空间
一个思考,bit length一定能生成合法的huffman树么?
Huffman树有一个原则,一个短的Code,不可能和一个长的Code重合
例如,下面的Code
|Code|
|:---|
|000|
|010|
|0101|
第一个code不和其它两个code冲突,但第二个code和第三个冲突,你可以注意到了,长度4的code前三个bit的010和第二个code是重复的,这显然是不合理的
因此在使用Bits Length构造Huffman树的时候,我们需要检查生成的Code是否存在冲突问题,如果存在冲突问题,那么这个BitS Length表就无法构造一个合法的huffman树,例如位长序列{2,2,2,2,3}肯定无法构造一个合法的huffman数,因为位长2已经把00,01,10,11占满了,位长3无论是什么都肯定和位长2的会有冲突.