KnifeFly
0%

压缩算法概览

Posted on Edited on

压缩算法概览

压缩的理论（它与算法信息论密切相关）以及率有损理论，这个领域的研究工作主要是由美国学者克劳德·香农（Claude Elwood Shannon）奠定的，他在二十世纪四十年代末期及五十年代早期发表了这方面的基础性的论文。

Lempel-Ziv（LZ）压缩方法是最流行的无损存储算法之一。DEFLATE是LZ的一个变体，它针对解压速度与压缩率进行了优化，虽然它的压缩速度可能非常缓慢，PKZIP、gzip以及PNG都在使用DEFLATE。LZW（Lempel-Ziv-Welch）是Unisys的专利，直到2003年6月专利到期限，这种方法用于GIF图像。另外值得一提的是LZR （LZ-Renau） 方法，它是Zip方法的基础。LZ方法使用基于表格的压缩模型，其中表格中的条目用重复的数据串替换。对于大多数的LZ方法来说，这个表格是从最初的输入数据动态生成的。这个表格经常采用霍夫曼编码维护（例如SHRI、LZX）。 当前一个性能良好基于LZ的编码机制是LZX，它用于微软公司的CAB格式。

压缩算法分为两个层面：

  1. 熵编码：根据消息中每个符号出现的概率，然后通过某种映射用更短的符号替代原来的符号，核心在于提高符号的信息熵，哈夫曼编码最为典型。
  2. 字典编码：提取信息中的重复部分作为字典，然后通过字典和某种映射替代这些重复的部分，核心在于替代重复，LZ77和LZ78算法最为典型。

gzip

Gzip是若干种文件压缩程序的简称，通常指GNU计划的实现，gzip的基础是DEFLATE，DEFLATE是LZ77与哈夫曼编码的一个组合体。Gzip编码格式在RFC 1952中定义。

Gzip亚搜文件格式如下为：

1
| ID1 | ID2 | CM | FLG | MTIME（4字节） | XFL | OS | ---> more

在Centos操作系统中空Gzip文件文件大小为26字节，用二进制查看工具查看文件内容：

1
2
3
0000000 8b1f 0808 c8fb 5d60 0300 6568 6c6c 006f
0000020 0003 0000 0000 0000 0000
0000032
  • 其中 ID1 和 ID2 分别是 0x1f 和 0x8b，用来标识文件格式是 gzip
  • CM 标识 加密算法，目前 0-7是保留字，8 指的是 deflate 算法
  • FLG标志位
  • MTIME 指的是源文件最近一次修改时间，存的是 Unix 时间戳
  • XFL defalte 算法中 2 表示使用压缩率最高的算法，4 表示使用压缩速度最快的算法
  • OS 标识压缩程序运行的文件系统，以处理 EOF 等的问题
  • more 后面是根据 FLG 的开启情况决定的，可能会有 循环冗余校验码、源文件长度、附加信息等多种其他信息

HTTP Gzip

在HTTP协议中 可以通过设置Content-Encoding字段来说明数据的压缩方法，客户端也可以再请求时设置Accept-Encoding 字段说明自己可以接受哪些压缩方法

1
2
3
Content-Encoding: gzip
Content-Encoding: compress
Content-Encoding: deflate
1
Accept-Encoding: gzip, deflate

Nginx服务器中设置gZip的配置大概如下：

1
2
3
gzip on;
gzip_types application/javascript application/x-javascript text/css;
gzip_disable "MSIE [1-6]\.";

文件Gzip

CentOS系统自带的gzip命令默认压缩级别是-6，可支持的级别为[-1, -9] ，越高的压缩率则在压缩和解压时更耗CPU，同时耗时也更长，但事压缩之后文件同时也会越小。

对于nginx原始日志采用gzip压缩之后可大大减小文件体积，410M非压缩文件的nginx原始日志，文件行数758515，每行大概700字节，采用6级别gzip压缩之后的文件大小为89M，可大大的减小原始文件大小，达到了500%的压缩比。可以发现gzip命令对同一个文件压缩和解压耗时不一样，通常压缩会更耗时，因为这和gzip压缩算法有关系。

gzip文件可以直接追加写gzip压缩的二进制数据，且不会破坏原先完整的压缩包，这也是日志系统中经常会用到的技术手段。

deflate 算法

DEFLATE是同时使用了LZ77算法与哈夫曼编码（Huffman Coding）的一个无损数据压缩算法。它最初是由菲尔·卡茨（Phil Katz）为他的PKZIP软件第二版所定义的，后来被RFC 1951标准化。

典型的字典编码，较早出现并流行的两种通用压缩算法。LZ77压缩算法用于分析输入数据，并确定如何通过用元数据替换冗余信息来减小输入数据的大小。与已编码数据部分相同的数据部分被少量元数据替换，这些元数据指示如何再次扩展这些部分。编码算法用于将数据和元数据结合起来，并将其序列化为字节流，随后可以对其进行解码和解压缩。LZ77算法的核心思路是如果一个串中有两个重复的串，那么只需要知道第一个串的内容和后面串相对于第一个串起始位置的距离 + 串的长度。比如： ABCDEFGABCDEFH → ABCDEFG(7,6)H。7 指的是往前第 7 个数开始，6 指的是重复串的长度，ABCDEFG(7,6)H 完全可以表示前面的串，并且是没有二义性的。

压缩：LZ77 用 滑动窗口（sliding-window compression）来实现这个算法。具体思路是扫描头从串的头部开始扫描串，在扫描头的前面有一个长度为 N 的滑动窗口。如果发现扫描头处的串和窗口里的 最长匹配串是相同的，则用（两个串之间的距离，串的长度）来代替后一个重复的串，同时还需要添加一个表示是真实串还是替换后的“串”的字节在前面以方便解压（此串需要在 真实串和替换“串” 之前都有存在。压缩因为要在窗口里寻找重复串相对来说效率是比较低的（LZ77 还是通过 Hash 等系列方法提高了很多）

具体可以参考这篇微软的文章

解压：gzip的解压流程大概是：观察压缩后的整个串，每个小串前都有一个标识要标记是原始串还是替换“串”，通过这个标识就能以 O（1）的复杂度直接读完并且替换完替换“串”，整体上效率是非常可观的。

Huffman Coding

霍夫曼编码（英语：Huffman Coding），又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）算法。由美国计算机科学家大卫·霍夫曼（David Albert Huffman）在1952年发明。

霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现几率的方法得到的，出现几率高的字母使用较短的编码，反之出现几率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低。

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度。

压缩：压缩过程就是创建一棵树的过程

解压：Huffman Coding 之后需要维护一张 Huffman Map 表，来记录重新编码后的字符串，根据这张表，还原原始串也是非常高效的。

特定领域压缩算法

快速压缩算法：LZ4，Snappy，都衍生自L77算法，具有还不错的压缩率以及极快的压缩解压速率，广泛用于RPC调用时传输数据压缩，LZ4还被用于内存压缩技术

无状态Zip压缩算法：Stateless ZIP library - SLZ，提供了基于 zlib 实现的流数据压缩器

数值压缩算法：Varint 与 ZigZag，Varint 可以压缩较小的正数，ZigZag 可以处理负数及大整数使之也可以使用 Varint 编码压缩，protobuf和thrift二进制序列化算法中都使用了二者结合的方式来压缩数字类型

JSON字符串压缩算法：CJSON 和 HPack，通过数据格式转换减少字符数实现数据压缩

其他还有各种针对如数据库数据，时序数据，图片，音频，视频等各种数据的无损压缩算法

参考文章：

  1. [无损压缩算法理论学习总结]