聊聊字符集编码与数据压缩( 五 ) _数据压缩

deflate 中的解压：
读取二进制文件，构建huffmantree 表，读取数据根据huffmantree 生成字符。LZ77 解码需要对窗口生成哈希表(数组+链表) ，对解压的数据，进行搜索匹配拷贝替换为相应的串即可。
8.gzip 格式分析
GZIP 本身只是一种文件格式，其内部通常采用 DEFLATE 数据格式，而 DEFLATE 采用 LZ77 压缩算法来压缩数据。GZIP 文件由 1 到多个“块”组成，实际上通常只有 1 块。每个块包含头、数据和尾三部分。块的概貌如下：
gzip = gzip 头 + deflate 编码的实际内容 + gzip 尾
zlib = zlib 头 + deflate 编码的实际内容 + zlib 尾

文章插图

（1）头部分
ID1 与 ID2：各 1 字节。固定值， ID1 = 31 (0x1F) ， ID2 = 139(0x8B) ，指示 GZIP 格式。CM：1 字节。压缩方法。目前只有一种：CM = 8 ，指示 DEFLATE 方法。FLG：1 字节。标志。
bit 0 FTEXT - 指示文本数据
bit 1 FHCRC - 指示存在 CRC16 头校验字段
bit 2 FEXTRA - 指示存在可选项字段
bit 3 FNAME - 指示存在原文件名字段
bit 4 FCOMMENT - 指示存在注释字段
bit 5-7 保留
MTIME：4 字节。更改时间。
XFL：1 字节。附加的标志。当 CM = 8 时，
XFL = 2 - 最大压缩但最慢的算法；XFL = 4 - 最快但最小压缩的算法 OS：1 字节。操
作系统，确切地说应该是文件系统。有下列定义：
0 - FAT 文件系统 (MS-DOS, OS/2, NT/Win32)
1 - Amiga
2 - VMS/OpenVMS
3 - Unix
4 - VM/CMS
5 - Atari TOS
6 - HPFS 文件系统 (OS/2, NT)
7 - macintosh
8 - Z-System
9 - CP/M
10 - TOPS-20
11 - NTFS 文件系统 (NT)
12 - QDOS
13 - Acorn RISCOS
255 - 未知
额外的头字段：
(若 FLG.FEXTRA = 1)
(2)数据部分
DEFLATE 数据格式，包含了一系列子数据块。结构如下:

文章插图

BFINAL：1 比特。0 - 还有后续子块；1 - 该子块是最后一块。BTYPE：2 比特。00 -- 不压缩， 01--静态Huffman编码压缩。10--动态Huffman 编码压缩。11--保留。
(3)尾部分
CRC32：4 字节。原始数据的32位校验和。ISIZE：4 字节。原始数据长度的低32位。
GZIP 中字节排列顺序是 LSB 方式，即 Little-Endian ，与 ZLIB 中的相反。
9.zlib 库 API 分析
(1)下载源码包
下载 http://www.zlib.net/ ，选择 zlib-1.2.11.tar.gz
(2)下载
wget http://www.zlib.net/zlib-1.2.11.tar.gz
(3)解压
tar -zxvf zlib-1.2.11.tar.gz
(3)进入目录
cd zlib-1.2.11
(4)配置
./configure
(5)编译
make
(6)检查，要全部为 yes
make check
(4)安装
sudo make install
基础数据结构:

文章插图

文章插图

压缩函数:
deflateInit :参数比较少，里面实际就是调用deflateInit2
deflateInit2:
deflate : 压缩函数。
deflateEnd :压缩完成后，释放空间，注意，仅仅释放deflateInit 中申请的空间，自己申请的空间还是要自己释放。
compress :全部附加选项默认压缩，内部调用 compress2 。
compress2 : 带 level 的压缩方式。
deflateInit2 : 初始化函数

文章插图

功能:压缩初始化内部流状态， zalloc ， zfree和opaque字段必须在调用之前初始化，若zalloc 和 zfree 被初始化为 Z_NULL ， deflateInit会更新它们而使用默认的分配函数。
压缩级别为Z_DEFAULT_COMPRESSION ，使用0到9之间的数， 1表示最快速度的压缩， 9表示最优压缩， 0表示不做任何压缩， Z_DEFAULT_COMPRESSION是速度和最优压缩的折衷。
level: 压缩的等级，目前有四个值
#define Z_NO_COMPRESSION 0 //不压缩
#define Z_BEST_SPEED 1 //速度优先,可以理解为最低限度的压缩.