让我们回顾第一章范式huffman的内容,显然的如果给出一段数据,比如我们叫它literal data,如果要对它进行动态的huffman压缩,压缩之后肯定分为2个部分:
第一部分是压缩后的比特流
第二部分就是原始数据每一个值的bits_length,我们可以把这个bits_length视作一个数组,如果literal data中每一个值的范围是0-287,那么,bits_length就是一个大小为288的数组
现在又要划重点了,因为我们知道,bit_length的长度本质上就是该节点在huffman树中的深度,如果literal data的样本足够大,并且足够的"巧合",那么,这个bits_length最深可以达到288-1,显然那么深的bits_length是不可接受的,但如果我们稍微变通一下,限制一下literal data输入的长度,因为huffman树本质上是通过literal频率生成的,因此即使是最坏的情况下,huffman数的深度都不会超过
$log2^{length}$,比如说literal data的长度是4,那么深度最坏情况下也是2,如果长度是8,最坏情况也是3
重点来了,在Deflate中,我们限制literal data生成huffman树的深度也就是bits length不能超过15,那是不是说输入的literal data长度不能超过32768呢?其实也不对,只有在极度倒霉的情况下,32768长度的深度才会达到15,大部分时候,大于这个尺度并不会导致位深超过15,而16,17,18被赋予了额外的意义,因此如果你需要用动态huffman编码,一定要选择一个合适的literal data长度.
第二个重点也来了,我们知道literal data是已经被lz77压缩后的结果,在上一章我们有讲述到,当literal的值大于256时,它是一个(length,distance)类型的数据,但是distance其实是一个参照了map table也就是映射表的数值,它本质上是一个0-29范围的索引数值,deflate为了把压缩进行到极致,单独为distance indices设置了一个范式huffman树来编码,因此,对原始数据的构造其实是2个huffman树,一个是literal tree,一个是distance tree.
现在让我们观察下图,我们使用范式huffman对literal data进行了编码,生成了一个literal compressed data和一个literal bits length,当然就和上面说的一样,distance indices也要建立一个huffman树来编码,我们就叫它distance compressed data和distance bits length.
这波操作下来,有一定成效.但对DEFLATE要把压缩进一步发挥的算法来说,还不够,因为literal bits length和distance bits length,我们可以合起来,再用huffman算法压缩一次
你以为这就结束了,当然没有,依据大部分数据的统计ld bits length那些出现的比较多的值,我们可以做成一个映射表放到前面去,而出现的比较少的值放到后面去,这样一来,我们就可以再节省几个bit的空间:
当然,都做到这一步了,索性把压缩做到底,我们literal bits length,distance bits length,ld bits length肯定有很多的0,索性我们存储2个表前面有数值的个数,这样还能再节省一些空间,下图中的hlt,hdist,hclen就是干这个的
最后,我们只需要存储map indices就可以还原整个压缩流程中用到的huffman树了
又一个重点来了,ld bits length的长度是使用3个bits存储的,也就是说,ld bits length中的每一个值不能超过7,当然,整个和你数据长度和到底里面有什么有关系.
之前那个literal bits length说到的16,17,18额外的意义是指16表示重复前一个值n次,这个n通过接下去读的2个bits获得的,17表示重复0值n次,这个次数是通过3加上接下来读的3个bits获得的,18表示重复0值n次,这个次数是通过11加上接下来读的7个bits获得的
为了进一步说明动态huffman树的解析流程,我们举个简短的栗子
1.依据上一章内容,我们先读取3个bit,然后发现这个block是用动态huffman编码的
2.读取5个bits,然后加上257,就是hlit的值
3.读取5个bits,然后加上1,就是hdist的值
4.读取4个bits,然后加上4,就是hclen的值
5.循环hclen次,每次读取3个bits,参照map indices,重建ld bits length,然后创建ld tree
6.循环hlit次,使用ld tree解码,code的意义可以参考上文,还原literal bits length.(lhit后面的值都是0),构造literal tree
7.循环hdist次,使用ld tree解码code,code意义同上(hdist后面同样都是0),还原distance bits length,构造distance tree
8.通过literal tree和distance tree解码原始lz77_code数据
9.通过lz77_code还原最初的原始数据.