冒险解谜游戏中文网 ChinaAVG

标题: 游戏常用压缩算法的介绍和识别 [打印本页]
作者: shane007    时间: 2009-12-22 17:16
标题: 游戏常用压缩算法的介绍和识别
原文; G# v6 e' r8 x  T3 i& t  y7 Z
http://blog.csdn.net/vbvan/archive/2008/02/25/2118668.aspx8 z. i7 f( f+ ^
, ]+ j# P6 X8 n. V
deflate
5 b. @# \. b  w0 a1 k( phttp://www.zlib.net/; h, D  n' F6 A2 [+ H6 U
这是ZIP默认采用的压缩算法。ZIP格式使用非常广泛，不仅有开源的C实现-zlib，还有众多的商业解决方案。因此在游戏中采用deflate，可以大大降低编程的成本。很多国外游戏的档案都采用这种压缩算法，或者直接使用ZIP文件格式存储资源。目前不少国内厂商也开始采用deflate。
) z/ G+ K" L4 f6 T: [" U默认ZIP使用的deflate，传入的WindowBits是-0xF。而zlib中默认使用的WindowBits是0xF。
- I4 E% I& m9 j$ b# B采用0xF作为WindowBits时，压缩后的数据的第一个字节往往是0x78，这可以用于识别deflate算法。: C5 J* |7 [' F& C
另外deflate算法通常都使用了zlib中的实现，在exe中会保留有版权信息：“ deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly ”，或者会带有zlib.dll。
6 I( A' `8 H6 e# w( o; D  M8 |
9 L4 l1 p1 N1 y9 ^) k( jbzip2* y' G& d/ N( B! y' S! L
http://www.bzip.org/
' {2 d" V# y' k9 c. }, Q" f在游戏中很少见，不过确实有游戏公司采用。; R3 y1 J# Z% I4 c9 L: {6 b9 g0 X
它压缩之后的数据是以BZ开头的。7 o* T4 {/ {+ O! s5 p

8 s  @+ C- F* ~; C) N0 Olzo
' x. U2 L& R. `+ J8 qhttp://www.oberhumer.com/opensource/lzo/
5 ]4 ?7 b# h% _1 I5 T6 O' R, A& tlzo是一种解压非常快速的压缩算法，通常开头若干字节不会被压缩。国内有几家公司使用了这种算法。6 {+ j9 [) l$ h- {8 G5 Y4 a
lzo的版权信息是：
, l& i) ^+ A+ x* {/ B" i. y“LZO data compression library.& }0 g* s% R6 V& a
$Copyright: LZO (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Markus Franz Xaver Johannes Oberhumer5 \& V* y/ w1 }0 }% m5 _+ P
<[email protected]>3 O+ a/ `3 w* _8 N
http://www.oberhumer.com $”/ _8 ]/ y2 I( q& }8 ?0 n/ C3 d( [

+ g  b. G, z& ^& v1 U( ^1 Srle
2 Z8 [& S& G' G3 N) p% hhttp://www.datacompression.info/RLE.shtml
4 C7 H# V% A* w3 J' z/ e4 ARLE是一个非常简单的算法，变种非常多。通常用于图像数据的压缩。5 r" y/ P0 J( K4 ~# i) `$ Q( |
较早的游戏一般用RLE算法压缩透明色。5 C0 P! u0 @1 I, R% S' E
标准的rle算法通常用字节的高2位做标记，因此比较容易识别。, V; x; R+ n& o: N% L6 R2 Q
3 d" {9 b: t$ |% k* j
lzss
( T% {5 o1 v2 ]$ z9 ~' ohttp://www.datacompression.info/LZSS.shtml! G' ~0 J- J; e+ C
日本人Haruhiko Okumura发明的压缩格式。
' Z$ I  D: k, Y, I$ T0 R这个算法有非常多的变种，在较早的游戏中比较常见。
7 L8 j# M3 |: e) E! l1 ?  M; E1 f仙剑1就采用了这种压缩算法的变种，它对压缩之后的数据做了huffman编码。8 J4 s( ]: }, \. J
标准的LZSS算法采用单独的字节存储标记，所以通常数据的开头若干字节也是不会被压缩的。, |2 h0 N4 h+ ]" h9 e6 r

( ?: w- `" s  `. w. G$ Q  jlzhuf9 T) F2 d, U3 N* e! |8 N' G
日本人Haruyasu Yoshizaki发明的压缩格式，使用了huffman编码。
) q9 m! W! I; E: Q相比lzss更复杂一些，在早期的游戏中也比较常见。) m5 q( c1 t2 m4 C* n/ J! B
2 U0 x* u5 X6 k" P: F* ~- Q7 h
最后贴一篇压缩算法的历史回顾2 {8 U) _* D0 X& a" c/ P
http://oku.edu.mie-u.ac.jp/~okumura/compression/history.html
作者: 灰色小狼    时间: 2009-12-22 19:16
我是进来膜拜霍夫曼大神的 [s:39]7 f4 C# C/ v/ ]# B1 d0 @; U

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



欢迎光临 冒险解谜游戏中文网 ChinaAVG (https://chinaavg.com/) Powered by Discuz! X3.2