游戏常用压缩算法的介绍和识别

shane007

原文
' D% _% ?2 c5 v- p! y& F+ |http://blog.csdn.net/vbvan/archive/2008/02/25/2118668.aspx
& P4 R& C1 b0 U
* e6 N! E* v, t; y$ Ideflate
http://www.zlib.net/
这是ZIP默认采用的压缩算法。ZIP格式使用非常广泛，不仅有开源的C实现-zlib，还有众多的商业解决方案。因此在游戏中采用deflate，可以大大降低编程的成本。很多国外游戏的档案都采用这种压缩算法，或者直接使用ZIP文件格式存储资源。目前不少国内厂商也开始采用deflate。
默认ZIP使用的deflate，传入的WindowBits是-0xF。而zlib中默认使用的WindowBits是0xF。
采用0xF作为WindowBits时，压缩后的数据的第一个字节往往是0x78，这可以用于识别deflate算法。
9 Q5 z3 F9 x4 o5 o另外deflate算法通常都使用了zlib中的实现，在exe中会保留有版权信息：“ deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly ”，或者会带有zlib.dll。
" g1 h8 U* \8 t- d0 L
bzip2
$ d" J; [8 V' Zhttp://www.bzip.org/
0 m& B0 z1 Y3 {3 s8 {4 r( c在游戏中很少见，不过确实有游戏公司采用。
它压缩之后的数据是以BZ开头的。
8 W! `. g7 p8 E% J* V$ N' Z
lzo
http://www.oberhumer.com/opensource/lzo/
7 [- w. x/ ~$ Y1 J, K3 hlzo是一种解压非常快速的压缩算法，通常开头若干字节不会被压缩。国内有几家公司使用了这种算法。
lzo的版权信息是：
“LZO data compression library.
. W  x9 \/ N  J$Copyright: LZO (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Markus Franz Xaver Johannes Oberhumer
<[email protected]>
2 p0 X) `/ U* D' Rhttp://www.oberhumer.com $”

8 D/ l- z. u  ^1 f* y' Rrle
  u1 o7 G* N+ v* |) zhttp://www.datacompression.info/RLE.shtml
RLE是一个非常简单的算法，变种非常多。通常用于图像数据的压缩。
较早的游戏一般用RLE算法压缩透明色。
标准的rle算法通常用字节的高2位做标记，因此比较容易识别。

. K! f7 S6 f0 s0 l" P1 v# Elzss
http://www.datacompression.info/LZSS.shtml
5 z3 q/ _0 g: A: K" r; q" X日本人Haruhiko Okumura发明的压缩格式。
这个算法有非常多的变种，在较早的游戏中比较常见。
8 a: M' ?7 J$ w! X$ z仙剑1就采用了这种压缩算法的变种，它对压缩之后的数据做了huffman编码。
( A$ ^. p* \1 E3 u- B+ A+ I标准的LZSS算法采用单独的字节存储标记，所以通常数据的开头若干字节也是不会被压缩的。
( `. r5 I8 F, i5 d1 y8 D& Y
lzhuf
' K8 Z6 [) Z0 X' t4 a) @+ C4 U日本人Haruyasu Yoshizaki发明的压缩格式，使用了huffman编码。
' m1 Q) E  y2 {' M# G" S4 [% @相比lzss更复杂一些，在早期的游戏中也比较常见。

最后贴一篇压缩算法的历史回顾
; W* `8 O( F# c0 n. Q- g! yhttp://oku.edu.mie-u.ac.jp/~okumura/compression/history.html

灰色小狼

我是进来膜拜霍夫曼大神的 [s:39]
1 v  e% s% K7 Y) {! K% a, G
Huffman编码
Huffman编码是第一个真正实用的编码方法，由D.A.Huffman在1952年提出。当时Huffman是麻省理工学院的一名学生，据说为了向老 师证明自己可以不参加某门功课的期末考试，他设计了这个看似简单却影响深远的编码方法。Huffman编码效率高，运算速度快，实现方式灵活，从20世纪 60年代直到现在，在数据压缩领域得到了广泛的应用。而20世纪80年代初，Huffman编码又出现在CP/M和DOS系统中，即使在今天，在许多知名 的压缩工具和压缩算法里（如WinZip、gzip和JPEG），也都有Huffman编码的身影。不过，Huffman编码所得的编码长度只是对信息熵 计算结果的一种近似，并不能真正逼近信息熵的极限。Huffman编码影响力很深远，至今还在计算机大专学生必修课程《数据结构》中被提及。