前面讨论分段策略时已经说过,为了避免个段落间节点频率差异被互相抵消,要求段落划分尽量细致、准确,最小的段落可以仅为 4k,而采用上面这种简单的方式,码表要超过 80k,显然是无法接受的。 对码表的保存方式的深入研究,确实是个无法绕开的挑战,如果不攻克这个难关,编码式压缩无法进行下去!挑战会带来乐趣,困难会激发豪情。我们所要做的是:观察 gzip 如何一步步地通过繁复但又巧妙的做法解决这个难题,对其中的做法的道理务求知其然、知其所以然,通过观察、思考,把握无损压缩内在的、深层的、本质的规律!事实上,对 gzip 的这些做法进行阅读(源代码)、分析、挖掘其中的智慧,本身就是一个对智慧、耐力、乃至决心的长期的挑战,我接受了这个挑战,并把它描述、解释出来,读者面对的挑战是花费较长期的时间去阅读、理解,希望读者完全有耐力、豪情、兴趣来接受这个挑战,深化自己的技术层次、思维层次。 3.1 只保存码长,并增加一些特殊的值。 3.1.1 把 huffman 树的每一层上的叶子节点都换到该层的左边,按照其原始值从小到大依次排列,非叶子节点则集中在该层右边,这时仍是一棵二叉树,得到的编码仍符合前缀编码的要求。每个叶子节点的编码长度不变,所以压缩率也不变。仅需要按照原始值从小到大依次保存每个值的码长,解压时就可以还原这套编码表,还原方法是:码长为 n 的第一个值的编码是码长为 n - 1 的最后一个值的编码加 1,并左移一位(也就是说,在编码最后加个 0),而码长为 n 的其他值的编码是前一个码长为 n 的值的编码加 1。从上面所说的树的角度来解释,每一层的第一个叶子节点是其上层最后一个叶子节点的右边一个节点的左子节点,所以它的编码是上层最后一个叶子节点的编码加 1 并左移一位,而每一层上的叶子节点都紧密排列,所以除了第一个叶子节点外,其他叶子节点的编码都是前一个叶子节点的编码加 1。编程上的实现方法是:遍历码表,得到每个码长(n)上有多少个值,计算出每个码长上第一个值的编码,放在数组 bit_len[]中,再次遍历码表,依次根据每个值的码长(n),赋予它的编码为该码长上的前一个值的编码 (bit_len[n]) 加 1,bit_len[n] ++。 由于只需要保存码长,现在码表由超过 80k 字节减小到约 20k 字节。 3.1.2 如何只保存在段落中出现过的节点(有效节点)的编码? 一个 ASCⅡ文本,128 以后的值是不会在文件中出现的,按照 3.1.1 的方法,码表中后半部分(都是 0)在解压缩时是用不到的。为了避免这类浪费,只保存有效节点(码长不为 0 的节点),一种方法是保存有效节点的原始值和新编码的码长,当有效节点超过所有节点的1/4,这种方法保存的码表的大小会超过 3.1.1 的方法。 gzip 采用的方法是:在 3.1.1 的基础上,于若干种码长之外,增加一些特殊的值,他们表示当前为之前一个码长或 0 码长(无效节点)的重复,遇到这种值,那后面的一个数字表示重复的次数。第一种值代表当前为之前一个码长的重复 3 - 6 次,后面跟着 2 bit 为具体的重复次数;第二种值代表当前为 0 码长的重复 3 - 10 次,后面跟着 3 bit 为具体的重复次数;第三种值代表当前为 0 码长的重复 11 - 138 次,后面跟着 7 bit 为具体的重复次数。限制最小重复次数为 3,可以确保这种方法得到的码表不会大过 3.1.1。第一种值限制最大重复次数为 6,是因为连续 6 个值以上的码长相等(说明频率十分接近)的情况不常见,做这个限制可以节省附加 bit;第二第三种值区分重复次数的范围,也是为了节省附加 bit。在只有少数有效节点的情况下,这种方法只需要保存较少的数据,同时也具有简单的去重复的作用。 如果最大码长是 15,0 - 15 共 16 种值,一个码长需要 4 位,加上上面 3 种值,共 19 种值,需要 5 位,在重复不多时,加了这 3 种值,是不是会增大码表?其实不用担心,gzip 会对码表再进行一次 huffman 压缩,根据这 19 种值的频率分配给它们可变码长的编码,不会造成浪费,由于涉及到一些其他情况,对码表的再编码压缩在后面还会详细介绍! 3.2 把原始字节值和匹配长度值建在一棵树上。 现在先考虑另一个问题:如何使解压时能区分当前是一个未匹配的字节,还是一个匹配?未匹配字节值和匹配长度、匹配距离是三棵不同的 huffman 树,它们的编码互相不符合前缀编码的要求,部分节点甚至可能编码相同,解压时如何区分? 第一种方法是用标志位。输出压缩结果时,除了输出每一段的码表、重新编码后的数据流,还要保存对应于这一段数据的标志位流,流中的每一位 0 或 1 表示当前是一个未匹配的字节,还是一个匹配。 第二种方法是给原始字节值和匹配长度值不同的编码,并符合前缀编码的要求。最好的做法是把它们建在一棵树上,以确保它们符合前缀编码的要求,并由它们的频率来确定各自的码长。 第一种方法相当于原始字节值和匹配长度值的编码都增长一位。 第二种方法中这两套节点的码长变化要根据具体节点各自的频率而定。 经过分析,第二种方法更好,因为第一种方法可以看作是第二种方法的变种,相当于简单地在两棵 huffman 树的根节点上再加一个父节点,这样显然是不能保证最佳的结果的。 3.3 把匹配长度、匹配距离变为长度范围、距离范围,减少节点。 经过上面对保存码表的方法的改进后,现在码表还有多大? 由于有了上面介绍的去重复机制,码表的实际大小和节点的重复情况有关,如果有很多连续 3 个以上节点的码长相等的情况出现,或有很多连续 3 个以上的无效节点的情况出现,码表可能是很小的,但作为通用的无损压缩算法,必须考虑重复不多的情况。“匹配距离”是码表中最主要的部分,我们来分析一下它的重复情况,“匹配距离”共有 32k 个取值,如果一个段落不到 32k,“匹配距离”的有效节点数当然是不可能到 32k 的,思考一下,可以知道,它的有效节点数和这样几个因素有关:一段有多长,段落中匹配数和未匹配数的比例,决定了它有多少个值,再加上这些值的重复性,决定了它有多少个有效节点。再分析一下这些值的重复性:不同于原始字节和“匹配长度”都只有 256 个取值,它有 32k 个取值,相同的匹配有相同的匹配长度但不一定有相同的匹配距离,所以它的去值范围广,重复率低,有效节点多。虽然实际的情况无法预测,但我们可以做一些“大致合理”的假设,以便对码表的大小有一个基本的概念,假如短语式压缩的输出段落的大小为 90k 字节,其中未匹配字节数和匹配数的比例为 3 : 1,每个未匹配字节占 8 位;每个匹配中,长度占 8 位,距离占 15 位,共 23 位,约为未匹配字节的 3 倍,所以匹配占了 90k 字节中的约 45k 字节,匹配数约 15k 个,也就是说有 15k 个距离值,假如距离值的平均节点频率为 3,那么去掉重复后有 5k 个有效距离值节点,保存到码表时每个码长需要 5 位,保存 5k 个码长需要 5k * 5 / 8 约 3k 字节,算上无效节点、码长的重复的因素,原始字节值、匹配长度的保存,最终码表约 5k 字节,为 90k 的 18 分之一。当段落减小时,有效节点趋于稀疏,无效节点容易连成片,去重复机制能发挥更大的作用;当段落增大时,无效节点密度减小,可能无法大片连接,去重复机制的效用降低,码表的比例可能会增大。一旦“匹配距离”需要保存的码长数达到了 32k个,码表达到最大,之后段落再增大也不会增大码表,于是码表的比例又会逐渐下降。当然段落通常不会达到这么大,使得“匹配距离”需要保存的码长数能有机会达到 32k。 gzip 以牺牲压缩率的代价来换取码表的进一步的大幅度减小。我们先描述一下它的具体做法,再来分析其利弊。 gzip 把匹配长度划成 29 个范围,把匹配距离划成 30 个范围,根据每个范围中节点的总频率,为 29 个长度范围加 258 个字节值建 huffman 树:l_tree,为 30 个距离范围建 huffman 树:d_tree。输出一个值时先输出该值所在范围的编码,再输出附加码,即它是该范围中的第几个值。这样码表中只需保存范围的码长。范围的大小都是 2 的乘方,所以范围大小和附加码的位长是互相决定的。 29 个长度范围的附加码位长是: {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; 30 个距离范围的附加码位长是: {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}; 可以看出:范围的划分是从小到大的。为什么不平均划分呢? 如果仍以单个节点的角度来看,被分到同一范围的节点相当于被赋予了相同的码长:范围编码的码长加附加码的码长。若频率差别很大的节点因划分入同一个范围而拥有相同的码长,就不符合 huffman 编码的初衷,会对压缩率产生不良影响。因此要求划分后,范围里的节点频率相近,以尽量降低同一个范围里不同节点间的相互影响。 “匹配长度”从短到长,频率会逐渐衰减,而且衰减的幅度有从大到小的特点,这个特点是在大多数原始文件中“自然存在”的。比如在 google 上搜索,2 个字的短语和 22 个字的短语,搜到的结果数差别巨大,200 个字和 220 个字,搜到的结果数差别就没有那么大。频率大致上单向地逐步变化,所以划分范围后,范围内节点的频率较接近;变化速度由大到小,所以范围的划分应该从小到大。
“匹配距离”也有类似的特点,对大多数文件来说,匹配发生在 1k 以内比发生在 5k 左右的可能性要大得多,但发生在 28k 处附近的可能性和发生在 32k 处附近的可能性的差别就没那么明显。所以范围划分也应该是从小到大。 “未匹配的原始字节”不具有频率衰减或递增的单向变化的规律,它们的频率分布往往是参差不齐、难以预测的,不可能用预先设定的范围表对它们进行大致合理的划分,就像“匹配长度”和“匹配距离”那样。虽然也可以通过计算分析,对它们进行不设定范围数量和大小的划分,以求每个范围中的各节点频率大致相近,但 1) “匹配距离”的划分已经大幅度地缩小了码表的大小;2) 由于不具有频率单向变化的趋向,要强行划出节点频率相近并且节点数是 2 的乘方的范围太勉强,难度也大;3) 未匹配的字节数一般要大于“匹配数”(注意:不是“匹配字节数”),强行划分造成的不良反应较大。所以 gzip 保留了这套节点,没去拆分。 长度范围的最后一个附加码位长是 0,是因为长度大于 258 的匹配都被截断到 258,所以 258 的频率可能会高出前面的节点,单独划为一个范围。 如果一个范围里的节点频率相同,节点数是 2 的乘方,且没有无效节点,那么这个范围可以看作 huffman 树中的一棵子树,范围的编码可以看作这棵子树的根的编码,这样的划分是不会影响压缩率的。 对压缩率的损害来自频率不一致,以及无效节点的存在。范围里的有效节点如果没有过半,“附加码”的位数就至少有一位浪费了,也就是说,范围里所有有效节点的码长无端增长了一位,如果有效节点没有过 1/4,至少就有 2 位附加码浪费。 划分范围的收益是使码表减小到不足 0.2k,加上后面会介绍的对码表的第二次压缩,码表的最终大小是微不足道的。 现在我们来近似地估计一下划分范围在“一般情况”下对压缩率的损害的情况,以便有一个大致的概念,仍举前面的例子:段落大小为 90k,设其中未匹配字节数和匹配数的比例为 3:1,未匹配字节有 45k 个,匹配距离值和匹配长度值各 15k 个,有效距离值节点为 5k个(节点平均频率为 3),无效距离值节点为 32k - 5k = 27k 个,有效距离值节点的平均密度为 5/32,不到 1/6。范围的划分是前小后大,有效节点频率是前大后小,无效节点是前少后多。距离值有 15k 个,设前面有效节点频率高、密度较大的部分占一半,约 7k 个值,这个部分中无效节点带来的损害较小,而且范围划分细,节点间频率不一致带来的损害也小,姑且不去计算。后面的范围划分大、有效节点密度小的部分损害较大,这个部分占了约 7k 个值,由于前面的部分有效节点密度大,所以假设这个部分有效节点密度为 1/8(也就是说,约一半的匹配发生在 1k 距离以内,且 1k 以内无效节点很少,那么 4k / 31k 约等于 1/8),附加码浪费了 3 位,7k 个值浪费 3 位,共浪费了 21k bit 约等于 3k 字节。 再看频率不一致带来的损害:huffman 编码如果要达到 50% 的压缩率,需要节点间频率的差异达到几百倍。读者可以虚拟一些节点频率,试着建一下 huffman 树,会发现当节点频率差异在几十倍甚至只有几倍的时候,压缩率其实微乎其微。经过上面这样合理地划分范围,范围内的节点频率差异一般不会那么大,所以我们假设频率不一致造成的损害为 1k - 2k。 匹配长度值的取值范围只有 258 个,而且匹配长度可能很少会超过 20 字节,而前 20 字节的范围划分是很细的,所以无效节点的损害和频率不一致的损害都较小。 这样,在这个例子中,划分范围带来的损害约在 5k - 6k,和不划分范围时码表的大小非常相似,至少也是在一个数量级上。 再来看看损害比例变化的趋势:当段落很小时,范围中的有效值稀疏,损害比例会加大。而不划分范围时,码表的去重复机制会有更大作用,无效节点连成片,损害比例减小。反之,段落增大,范围里有效节点密度大,损害比例降低,而不划分范围时,无效节点可能无法大片连接,去重复机制的效用降低,损害比例增大。 由于划分范围能使 huffman 树的节点从最多 32k 减到不足 320 个,从而使压缩速度显著改善。综上所述,段落小(比如不到 10k),不宜划分范围,否则划分范围是有益的。 3.4 对码表进行第二次压缩。 目前为止,码表中只需要保存各个节点经过 huffman 编码后的新编码的码长。共两棵树,l_tree: 256 个原始字节值加 29 个长度范围值加 1 个段落中止符,共 286 个节点,段落中止符用来在解压时标示一个段落的终结。d_tree: 30 个距离范围值。也就是说,共需要保存 286 + 30 = 316 个编码的码长。gzip 限制 huffman 树的最大层数为 15,这样,码长就有 0 - 15 共 16 种值,再加上前面介绍过的去重复机制使用的 3 种特殊值,共 19 种值,如果就这样保存码表的话,每个码长都需要 5 位,才能表示 19 种值。我们观察一下,316 个码长,一共只有 19 种值,码长值的重复是必然的,而且由于 huffman 树上每层的节点数不同,所以各个码长值的频率也不一样。所以还可以为这 19 种值再建 huffman 树,进行第二次编码。这棵树只有 19 个节点,限制它的层数为 0 - 7,可以用 3 个 bit 表示这 19 个节点的“长度”。这样,用新的“码长的编码”来保存 316 个码长,另需额外保存 3 * 19 = 57 bit,就可以解压出这 19 个“码长的编码”。(至于这 57 bit,就没有必要再作第 3 次编码了) 4. 解决了码表的问题,现在再回过头来看静态编码。 静态编码是 gzip 预先设定的编码方案,它的码表是固定的。 该如何合理设计这套编码?作为 huffman 编码的补助,它的耗时应尽量少,前面说过,lz77 输出一个分段之前,要比较 huffman 编码和静态编码的压缩结果,为了直接利用 lz77 输出时做的匹配长度范围、匹配距离范围的频率的统计,静态编码采用了同样的范围-附加码的方案,这样可以快速得到静态编码的压缩结果大小。 静态编码的码长的分配是这样的:29 个长度范围中前 24 个范围的码长为 7,后 5 个范围的码长为8。原始字节值中 0 - 143 的码长为 8,144 - 255 的码长为 9。而 30 个距离范围的码长为 5。根据这些预先设定的码长建立静态的 l_tree 和 d_tree,编码也就产生了。结合前面提到的附加码位数的定义: 29 个长度范围的附加码位长: {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; 30 个距离范围的附加码位长: {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}; 读者可以知道每一个值的实际码长。长度范围值和原始字节值建在一棵树上,节点多所以码长较长,30 个距离范围值只需要 5 位二进制数表示。短匹配的长度范围值位长较短,字节值 0 - 143 的位长中等,其他字节值和长匹配的长度范围值较长。这样的分配反映了 gzip 作者对“大多数”文件中各种值的频率的粗略估计。作为一个通用的压缩算法,无法预先知道一个文件的实际情况,不可能做精确的估计。 进一步的思考:静态编码有必要吗?静态编码采用了和 huffman 编码相同的范围-附加码的方案,在码长的分配上不可能超过 huffman 编码,如果能“获胜”,那就是胜在不需要保存码表上,而前面分析过,码表是很小的,对压缩率没有多大影响,所以 gzip 设计的这个静态编码方案应该是可有可无的。
5. 关于堆排序算法。 似乎已经解决了所有的难题,但是对于没有学过数据结构的读者,仍然有一个会对程序效率产生影响的问题需要关注,那就是“排序”。 已经讲过,huffman 算法就是从一个节点序列中,不断找出两个最小的节点,为它们建一个父节点,值为这两个节点之和,然后从节点序列中去除这两个节点,加入它们的父节点到序列中,不断重复这样的步骤,直到节点序列中只剩下一个节点。如何快速地找出最小的元素呢? 在普通的线性罗列的数据结构中,从 N 个元素中找出最小的元素的时间和 N 成正比,如果数据以我们所要介绍的“堆”的结构存储,时间和 lg N 成正比(注:lg 以 2 为底数,如 lg 256 = 8,lg 1024 = 10 ...)。 集合中的元素越多,堆排序算法的优势越突出,而且堆排序非常适合于在数据序列中不断地取走最小的元素并加入新的元素。 5.1 什么是堆? 堆首先是一棵“完全二叉树”,即所有的叶子节点都在树的最低二层,最低一层的节点依次靠左排列的二叉树。如图: 完全二叉树 | +----------○----------+ | | +-------○------+ +---○---+ | | | | +---○---+ +---○---+ +-○-+ +-○-+ | | | | | | | | +-○-+ +-○-+ +-○-+ +-○-+ ■ ■ ■ ■ | | | | | | | |
|