我们的游戏资源数据、例如图片、声音、脚本等，都是使用gzip压缩的。之前做BREW的时候，大部分手机支持BREW的ZIP解压接口，有的不支持，只好在网上找了一份解压的代码。找的代码好像在解析压缩数据头部信息时，有点bug。另外在一些超低端机型上，解压过程中会死机，怀疑是解压需要的内存过大的原因。因为不熟悉gzip压缩的原理，当时胡乱改了改，有些问题也不了了之了。
现在转做智能平台，看到很多引擎里都使用了zlib模块。上网查了查，发现zlib和gzip是使用的同样的压缩算法（deflate，另外png也是使用的这个噢）。但是我们在使用zlib解压gzip压缩的数据时也遇到了一些问题，后来发现是对zlib的接口不熟悉导致的误用。经过这几次挫折，以及见识了zlib应用的广泛，我决定花些时间啃啃这块硬骨头，开始阅读zlib的源代码。
这里先说一下zlib接口的事情。zlib被设计成在内存有限的情况下，可以压缩解压远远超出内存大小的数据的能力，因此它提供的接口，也大多是对数据进行一段段的处理。我们使用时，图省事，直接使用它提供的一个一次解压的函数uncompress，但是这个函数实际上在zlib的默认条件下，无法识别gzip的头部信息。查看这个函数的源代码，发现它只不过是对zlib一些公共接口的封装。参照它的写法，只是修改一下deflateInit2函数的一个参数，就可以解压gzip数据了。
通过阅读源码直接理解zlib算法，对我还是一件比较困难的事情。建议先看看源代码doc目录下的几个zlib标准文档、以及zlib网站上的技术解释文章。下面说下我对ZLIB算法的一些理解。
ZLIB使用的defalte压缩方法，简单来说，就是先将数据中重复的字符串，替换成（距离，长度）对；再对替换后的数据，使用huffman编码，将字符按出现频率重新编码。同时在替换过程中，保证不论数据有多大，算法所占用的内存都是可控的。
算法的思想很直观，但具体到实现上，有一些难点。比如采用什么方式查找一个字符串是否在前面出现过。直接的循环字符比较效率很低，我觉得zlib是参考了Rabin–Karp字符串查找算法，即使用hash方法来确定一个字符串是否在前面出现过。zlib压缩过程中会维护一个比较大的hash值数组，这个数组存储了数据流中每3个字符组成的字符串的hash值，例如4、5、6号字符计算一个hash值，5、6、7号字符也计算一个hash值。计算出的hash值作为下标，用来在hash值数组里存储当前三字字符串的下标。当数据流中出现一个新字符时，和之前的两个字符组成一个字符串，计算hash值，看在hash数组里该值的位置是否已经有值，有的话就取出这个值(上一次得到这个hash值的三个字符的下标)，检查是否是有效匹配。可以将查找过程理解为一个查字典的过程，只不过这个字典的条目也是处理过程中逐渐生成、逐渐抛弃的。
zlib会将得到的纯字符与（距离、长度）对中的距离统一编码（0~285），长度单独编码（0~29）。当然这两个范围对于长度（3~258），距离（1~32768）来说都是不够的，需要在编码后紧跟额外bit来确定具体值。
接下来的一步是对这两个字符集使用huffman编码。这时有两种方式，静态编码和动态编码。静态编码是指压缩和解压部分规定好一个静态编码方式，例如字符256~279编码为0000000~0010111，0~143编码为00110000~10111111。采用这种方式，压缩数据中就不用包含每个字符对应的huffman编码了。
另外一种动态编码，就是根据字符在数据中出现的频率，动态构造huffman编码。与教科书的算法相比，要加入一些限制。保证生成的huffman树是唯一的。这样的好处就是动态数据里也不直接记录编码对应的huffman编码，只要记录huffman编码的长度就好了。这个过程我是这样理解的，生成的huffman树的形状，是左边深度低、右边深度高，叶子节点从左往右看，是先按频率，再按字符在字典里的顺序排的序。这样就比较好理解通过hunffman编码长度，反推出字符-编码对应关系的方法了。
不过令我惊讶的是，动态编码到这一步还没有完，生成的huffman编码长度序列，还要再经过一次RLE压缩，即序列变成这样：字符，字符，这个字符重复几次...。RLE压缩后的长度序列，单个元素的范围是（0~18），其中0~15是huffman编码长度，16~18是长度编码重复次数（3~138，需要额外bit位确定）。然后，再把这个序列，来一次huffman编码...
明白了这些实现上的难点，源代码还是很好理解的，只是对于为什么要这么设计，我还有些浆糊。不过最近要学习的东西有点多，只能先理解到这种程度了。
参考资料：
zlibdoc下的各种文档
zlib网站上的相关文章（zlib网站竟然被墙了，为什么）
一篇不错的算法细节分析文章