zip 的压缩原理与实现三

gzip 在完成短语式压缩后，将转入编码式压缩的阶段。这个阶段的实现是很复杂的，对最终的压缩率至关重要，我会详细解说 gzip 的做法。gzip 是开放源代码的无损压缩程序中最著名的，其中的种种技巧很有启发意义，但是他是比较早期的程序，现在有很多的程序已经在压缩率上超过了它，所以我会根据自己对无损压缩的基本规律的理解提出对它的改进。

编码式压缩的几点考虑：
1. huffman 算法压缩率的关键是各节点值的差异要大，这样就要求分段编码输出。因为某些段落中某些节点的出现频率较高，另一些段落中这些节点出现频率较低，如果不分段输出，频率的差异会被彼此抵消，而不同段落中，节点的出现频率不同是常有的。
　　要决定分段的大小，必须解决一对矛盾：上面的分析似乎要求段落越小越好，但由于要保存码表以对 huffman 压缩结果进行解压，每个段落都要保存一份不同的码表，所以段落取得太小，保存了码表后得不偿失，这样，似乎又要求段落要尽量大，使码表的保存份数尽量少。
　　gzip 采取了这样的策略来确定段落的大小：lz77 压缩每产生 4k（小）的数据，就判断现在对未编码部分进行编码输出是否合适，最多积压到 32k（大）的时候，必定进行强制输出，因为平庸的数据积压得太多，后面即使有好的数据，频率统计在一起，也会被平庸化。
　　判断当前输出合适与否的条件是：1)用预先设定好的各节点长度和各节点实际的出现次数，计算压缩结果的大概值，看这个值是否小于未压缩时的 1/2。2)看目前为止的匹配数是否小于未匹配的字节数，因为 lz77 压缩产生的数据包括“匹配”和“未匹配的原始字节”，段落间的节点频率差异主要体现在“未匹配的原始字节”中。
　　上面的判断只是一种“猜测”，真正的精确的计算需要花费更多的时间。
　　我觉得 gzip 的策略可以改进，我的策略是：1)输出的时机是压缩率的关键之一，现在计算机的速度和九十年代时已经今非昔比，现在完全有条件采用真正的建 huffman 树的方法得到各节点的码长，作精确的判断。2)不应该与未压缩的原始数据比较，而应该与 lz77 输出的数据比较，否则计算出的压缩比很大一部分是短语式压缩的功劳。3)由于采用了真正的建 huffman 树的方法，不用再去做匹配数与未匹配的字节数的比较，因为那只是一种猜测。4)每 4k 的数据都单独统计频率，如果是合适的，就先输出之前的积压（如果有的话），再输出当前的 4k，这样可以避免当前的数据被积压的数据平庸化。如果不合适，就把当前的频率归入到积压的数据（如果有）的频率中，再判断是否合适，如仍不合适就暂缓输出，否则一起输出，这和 gzip 的作法是一样的。说明：几段差的数据积压到一起仍有可能成为好的数据，比如 01、 02、……积压在一起，0 的频率逐渐高出了其他字节。5)如果愿意付出更多的时间，在把当前的频率归入之前的频率时，可以先和之前 4k 的频率合并，如果不合适，和之前 8k 的频率合并，这样逐渐往前合并 4k，避免前面不好的数据拖累合并后的好的数据。6)有了前面的机制，32k 的强制输出点可以取消。7)进一步的改进：当要输出时，只输出积压的不好的部分，好的数据先留着，等后面的 4k，如果新的加入后，仍是好的数据，就再等，如果会降低压缩率，才输出好的部分。这样，让好的数据大段的输出，可以减少码表的保存份数。8)再进一步的改进：坏的数据放在一起可能会提高压缩率，好的数据放在一起也可能更好，当然，两种情况也都有可能降低压缩率，所以前面判断“好”还是“不好”，“合适”还是“不合适”的标准应该从某一个固定的压缩率标准改变为：提高了压缩率还是降低了压缩率。（提高的幅度应该至少抵消多保存一份码表的损失；降低的幅度也应该至少抵消少保存一份码表的得益）9)综合前面的分析，确定分段大小的策略最终调整为：当新的数据和前面的未切分数据放在一起时，两者中任何一方受到损失，都应该设置切分点，积累了两个分段后，通过计算，当切分带来的收益大于少保存一份码表时，才输出前一段，否则取消它们之间的切分点。这个策略实际上可以涵盖前面提到的所有改进，因为每个实际的分段之中的数据或者相互促进，或者彼此稍有妨害，但好过多保存一份码表；而每两个相邻的分段之间的数据彼此妨害，抵消了少保存一份码表的收益。这个策略简单直观地体现了我们设置分段的初衷：就是分段输出必须能提高压缩率。

2. 如果不考虑码表，huffman 算法能得到最短的编码式压缩结果，但是这种算法必须保存码表以便解压缩，所以不能保证结果是最佳的。gzip 预先拟定了一套通用的静态的编码，当要输出一个段落时，比较 huffman 压缩结果加码表的长度和静态编码的压缩结果长度，再决定用哪种方法输出这个段落。静态编码不需要建树，计算压缩结果长度时耗时很少。如果各节点的频率的差异很小，huffman 压缩结果加码表反而增大了结果，静态编码也不合适，同样增大了结果，gzip 就直接保存 lz77 的原始输出。由于输出一个段落时，增加了静态编码的方案，使输出的实际长度和之前确定分段点时计算的值可能不同，那么前面计算出的这个分段点是否仍是正确的？前面的分段策略是否需要调整？
　　分析：1)静态编码的各节点编码是不变的，对于段落的合并是无所谓的，两个连续段落即使都采用静态编码，也不用合并，因为合并后结果长度是不会变的。2)所以只对一种情况可能有影响：一个段落中拆分出一些部分用 huffman 编码，另一些部分用静态编码，压缩结果更好。当这种情况发生时，则必有一些部分的优势节点（频率高的节点）与静态编码预先拟定的优势节点相近，采用静态编码后有稍许改善，其他部分则与静态编码预先拟定的优势节点有一定分歧，采用静态编码后会有稍许不利。之所以说“稍许”，是因为我们已知同一个段落里的各部分数据或者互相促进，或者仅有稍许妨害，说明它们的优势节点是大致趋同的。考虑到拆分后可能要多保存几份码表，拆分带来收益的可能性和程度是很小的，而且计算的复杂度较大，所以前面的拆分策略可以不作调整。
　　至于直接保存 lz77 的原始输出，可以看作静态编码的一种特殊形式，只不过它假定各节点的频率相近，没有优势节点。它可以套用静态编码的分析，来证明不影响前面已经制定的分段策略。

3.采用 huffman 编码，必须深入研究码表的保存方式。
　　只要计算一下采用简单的方式来保存码表，需要多大的空间，就知道这是一个挑战。
　　简单地保存码表的方法是顺序地保存每一个值的码长和编码。之所以要保存码长，是因为编码是不定长的，没有码长，解压时无法正确读取编码。码长必须是定长的，也就是说必须限制 huffman 树的最大层数，使码长的位数能恰好表示这个层数。限制 huffman 树的最大层数的方法是：如果规定的最大层数为 n，则在 n - 1 层找到一个叶子节点 a（如果 n - 1 层没有叶子节点，就逐层地往上寻找，直到找到一个叶子节点），在节点 a 的位置放一个非叶子节点 A，使 a 成为 A 的子节点，把某个超过 n 层的叶子节点 b 提上来作为 A 的另一个子节点，此时 b 的父节点 B 只剩下一个子节点 c，取消 B，把 c 放在 B 的位置，重复这样的过程，直到所有 n 层以下的节点都被提上来。之所以要从 n - 1 层开始逐层往上找，是因为下层的节点频率小，码长变化后的影响小。假设每一层节点的频率相近，那么上层父节点的频率是其下层子节点的两倍，第 11 层节点的频率只有第一层节点频率的 1 / 1024，所以应该从下往上找。
　　现在就开始计算码表大小：
　　对于 256 个原始字节值，限制它的 huffman 树的层数为 0 － 15，码长就需要 4 位，256 个码长需要 4 bit * 256 = 128 字节；而 256 个新编码需要至少 256 字节。（当二叉树的所有叶子节点都放在第 8 层 —— 不算根节点一层，正好能放下 2 的 8 次方 = 256 个叶子节点，其中任何一个叶子节点往上升，至少造成两个叶子节点往下降。换一个角度说，如果在第 8 层以上存在一个叶子节点 a，在节点 a 的位置放一个非叶子节点 A，使 a 成为 A 的子节点，把某个超过 8 层的叶子节点 b 提上来作为 A 的另一个子节点，此时 b 的父节点 B 只剩下一个子节点 c，取消 B，把 c 放在 B 的位置，此时 a 增长了一位，c 缩短了一位，b 缩短了至少一位，编码的平均位长缩短。所以，当第 8 层以上不存在叶子节点，所有叶子节点都放在第 8 层时，编码的平均位长达到最短 —— 8位。）这套码表共需至少 128 + 256 = 384 字节。
　　256 个“匹配长度”的情况与原始字节值相同，两套码表共需至少 384 * 2 = 768 字节。
　　对于 32k 个“匹配距离”，如果限制该 huffman 树的层数为 0 － 31，保存每个值的码长需要 5 位，新编码的平均长度超过 15 位。（因为所有叶子节点都放在第 15 层 —— 不算根节点一层，正好能放下 2 的 15 次方 = 32k 个叶子节点。）这套码表要超过80k 字节（ (5 + 15) * 32k / 8 = 80k ）。
　　前面讨论分段策略时已经说过，为了避免个段落间节点频率差异被互相抵消，要求段落划分尽量细致、准确，最小的段落可以仅为 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），不宜划分范围，否则划分范围是有益的。