压缩算法排行榜（几款主流的压缩算法对比）

一、压缩原理

通俗地说，压缩就是找出那些重复出现的字符串，然后用更短的符号代替，从而达到缩短字符串的目的。比如，有一篇文章大量使用"中华人民共和国"这个词语，我们用"中国"代替，就缩短了5个字符，如果用"华"代替，就缩短了6个字符。事实上，只要保证对应关系，可以用任意字符代替那些重复出现的字符串。本质上，所谓"压缩"就是找出文件内容的概率分布，将那些出现概率高的部分代替成更短的形式。所以，内容越是重复的文件，就可以压缩地越小。比如，“ABABABABABABAB"可以压缩成"7AB”。

相应地，如果内容毫无重复，就很难压缩。极端情况就是，遇到那些均匀分布的随机字符串，往往连一个字符都压缩不了。比如，任意排列的10个阿拉伯数字（5271839406），就是无法压缩的；再比如，无理数（比如π）也很难压缩。

二、流行压缩算法1、LZ77

基于统计的数据压缩编码，比如Huffman编码，需要得到先验知识——信源的字符频率，然后进行压缩。但是在大多数情况下，这种先验知识是很难预先获得。因此，设计一种更为通用的数据压缩编码显得尤为重要。LZ77数据压缩算法应运而生，其核心思想：利用数据的重复结构信息来进行数据压缩。1977年和1978年，两名以色列人齐弗和兰佩尔提出了字典式编码【《AUniversalAlgorithmforSequentialDataCompression》】，即著名的LZ77算法。这种算法在数据压缩领域获得了广泛应用，我们使用的通用压缩工具：ARJ、PKZip、WinZip、WinRar等，都是这种压缩算法的变形。

（1）原理

在具体实现中，用滑动窗口（SlidingWindow）字典存储历史字符，LookaheadBuffer存储待压缩的字符，Cursor作为两者之间的分隔，如图所示：

并且字典与LookaheadBuffer的长度是固定的。

（2）压缩

用(p，l，c)表示LookaheadBuffer中字符串的最长匹配结果，其中

• p表示最长匹配时，字典中字符开始时的位置（相对于Cursor位置），
• l为最长匹配字符串的长度，
• c指LookaheadBuffer最长匹配结束时的下一字符压缩的过程，就是重复输出(p，l，c)，并将Cursor移动至l 1，

（3）解压缩为了能保证正确解码，解压缩时的滑动窗口长度与压缩时一样。在解压缩，遇到(p，l，c)大致分为三类情况：

• p==0且l==0，即初始情况，直接解码
• p>=l，解码为字典
• p<l，即出现循环编码，需要从左至右循环拼接，

作为一种基于字典的算法，LZ77将长字符串（也称为短语）编码成短小的标记，用小标记代替字典中的短语，从而达到压缩的目的。即LZ77通过用小的标记来代替数据中多次重复出现的长串方法来压缩数据。其处理的符号不一定是文本字符，可以是任意大小的符号。

LZ77通过滑动窗口”slidingwindow”实现动态字典，使用的是一个前向缓冲区和一个滑动窗口来维护这个字典。首先将一部分数据载入前向缓冲区，一旦数据中的短语通过前向缓冲区，那么它将移动到滑动窗口中，并变成字典的一部分。LZ77算法的主要思想就是在前向缓冲区中不断寻找能够与字典中短语匹配的最长短语。

大多数情况下LZ77压缩算法的压缩比相当高，这和所选择滑动窗口大小，以及前向缓冲区大小，以及数据熵有关系。其压缩过程是比较耗时的，因为要花费很多时间寻找滑动窗口中的短语匹配，但相对应的，解压过程会很快，因为每个标记都明确告知在哪个位置可以读取。

使用固定大小窗口进行短语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。常见的窗口固定大小4k、8k、16k。

2、Huffman编码

Huffman在1952年根据香农（Shannon）在1948年和范若（Fano）在1949年阐述的这种编码思想提出了一种不定长编码的方法【《一种构建极小多余编码的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）】，也称哈夫曼（Huffman）编码。

哈夫曼编码首先会使用字符的频率创建一棵树，然后通过这个树的结构为每个字符生成一个特定的编码，出现频率高的字符使用较短的编码，出现频率低的则使用较长的编码，这样就会使编码之后的字符串平均长度降低，从而达到数据无损压缩的目的。

（1）构造霍夫曼树

假如某一个文本只包含wuvxy等字符，如图对此进行如下构造过程：

步骤一：统计文本的各权重分别为7，12，15，18，20

步骤二：7，12，15，18，20选出权重最小的7、12进行构造生成19

步骤三：19，15，18，20选出权重最小的15，18进行构造生成33

步骤四：19，33，20选出权重最小的19，20进行构造生成39

步骤五：33，39进行构造生成72

哈夫曼是一种可变长编码（VLC，variablelengthcoding)）方式，是一种用于无损数据压缩的熵编码算法，通常用于压缩重复率比较高的字符数据。比起定长编码的ASCII编码来说，哈夫曼编码能节省很多的空间，因为每一个字符出现的频率不是一致的；

1. 压缩库：Zlib

（1）Zlib

zlib是一个免费、通用、不受任何法律阻碍的、无损、跨平台的数据压缩开发库。Zlib提供内存压缩和解压缩功能，包括未压缩数据的完整性检查。目前已经成功应用在诸如MySQL、Java、3DMax、以及微软的DirectX等大型的系统中，最新版本是zlib1.2.12，更新于今年3月27日。

Zlib使用deflate算法，deflate是同时使用了LZ77算法与哈夫曼编码（HuffmanCoding）的一个无损数据压缩算法。作为如今最流行的通用压缩算法之一，Zip、7z、xz等压缩文件都用。

压缩器有三种可用的压缩模式：

1. 完全没有压缩。例如，对于已经压缩的数据，这是一个明智的选择。以这种模式存储的数据会略微扩展，但不会像已经压缩并且尝试过其他压缩方法之一那样扩展。
2. 压缩，首先使用 LZ77，然后使用 Huffman 编码。在这种模式下用于压缩的树由 Deflate 规范本身定义，因此不需要额外的空间来存储这些树。
3. 压缩，首先使用 LZ77，然后使用 Huffman 编码，使用压缩器创建并与数据一起存储的树。

数据被分解成“块”，每个块使用单一的压缩模式。如果压缩器想要从非压缩存储切换到使用规范定义的树进行压缩，或者使用指定的霍夫曼树进行压缩，或者使用另一对不同的霍夫曼树进行压缩，则必须结束当前块并创建一个新块开始了。

deflate采用的是改进版的LZ77算法，即三个字节以上重复才进行编码，否则不进行编码，即对滑动窗口进行查询的时候最短匹配大小为3个字节。由于在gzip中，<匹配长度，到匹配串开头的距离>对比中，“匹配长度”的范围为3-258，也就是有256种可能，需要8bit来保存。“到匹配串开头的距离"范围为0~32k，需要15bit来保存。所以一个<匹配长度，到匹配串开头的距离>对需要23位，差一位3个字节。

如果一个匹配串小于3个字节，使用<匹配长度，到匹配串开头的距离>对进行替换，不但没有压缩，反而还会增大。所以保存<匹配长度，到匹配串开头的距离>所队应的位数，决定了最小匹配长度至少要为3个字节。

Lz77匹配查找的时候用了哈希表，一个head数组记录最近匹配的位置和prev链表来记录哈希值冲突的之前的匹配位置

如果每次为当前串寻找匹配串时，都要和之前的每个串的至少3个字节进行比较的话，那么比较量将是非常非常大的。为了提高比较速度，deflate使用了哈希表。这是deflate实现LZ77的关键。这个哈希表是一个叫head的数组。

对Lz77得到的压缩后结果，需要统计字符生成编码表huffmantree(指示每个编码代表什么字符），根据码表对内容进行编码，具体的压缩大小在于精细分配结构体的位域来实现Huffman编码的压缩效果的。

基于Zlib压缩率的测试，包含压缩比，压缩时间，cpu占用率，压缩耗时：

压缩等级	源数据大小（MB）	压缩后大小（MB）	耗时（S）	cpu占用率	压缩比	压缩速率（MB/s）
0	368	368	7	50%	0.00	52.57
1	368	179	23	50%	0.49	7.78
3	368	178	24	50%	0.48	7.41
6	368	168	34	50%	0.46	4.91
9	368	168	37	50%	0.46	4.54
（default）-1	368	168	35	50%	0.46	4.8

1. SnappySnappy是一个Google开发的压缩和解压缩的库。其目标不是最大限度压缩或者兼容其他压缩格式，而是旨在提供高速压缩速度和合理的压缩率。Snappy比zlib更快，但压缩后的文件相对要大20%到100%。在64位模式的Corei7处理器上，可达每秒250~500兆的压缩速度，并以大约 500 MB/秒或更高的速度解压缩。如果允许损失一些压缩率的话，那么可以达到更高的压缩速度，虽然生成的压缩文件可能会比其他库的要大上20%至100%，但是，相比其他的压缩库，Snappy却能够在特定的压缩率下拥有惊人的压缩速度，压缩普通文本文件的速度是其他库的1.5-1.7倍，HTML能达到2-4倍，但是对于JPEG、PNG以及其他的已压缩的数据，压缩速度不会有明显改善。
2. LZ4

Lz4压缩算法是由YannCollet在2011年设计实现的，lz4属于lz77系列的压缩算法，lz4算法是lz77算法的一种实现，具有固定的面向字节的编码格式，就是查找重复的字符串，重复的字符串使用(距离，长度)来表示。

比如abcdefgabcdefg，被压缩后就表示成了：abcdefg，(1，7)

距离有多重表示方法：

• 重复的字符串尾部距离当前正在处理的字符的距离
• 重复的字符串头部距离当前正在处理的字符的距离
• 重复的字符串在输入字符串的位置
• 重复字符串头部位置的内存地址数据格式压缩块有多个序列组成，一个序列是由一组字面量(非压缩字节)，后跟一个匹配副本。每个序列以token开始，字面量和匹配副本的长度是有token以及offset决定的。
• literals指没有重复、首次出现的字节流，即不可压缩的部分
• literals length指不可压缩部分的长度
• match length指重复项(可以压缩的部分)长度

下图为单个序列的数据格式，一个完整的lz4压缩块是由多个序列组成的。

压缩过程

lz4遵循上面说到的lz77思想理论，通过滑动窗口、hash表、数据编码等操作实现数据压缩。压缩过程以至少4字节为扫描窗口查找匹配，每次移动1字节进行扫描，遇到重复的就进行压缩。

举个例子：给出一个字符串: abcde_fghabcde_ghxxahcde，描述出此字符串的压缩过程【按照6字节扫描窗口，每次1字节来进行扫描】

1. 假设lz4的滑动窗口大小为6字节，扫描窗口为1字节；
2. lz4开始扫描，首先对0-5位置做hash运算，hash表中无该值，所以存入hash表；
3. 向后扫描，开始计算1-6位置hash值，hash表中依然无此值，所以继续将hash值存入hash表；
4. 扫描过程依次类推，直到图中例子，在计算9-15位置的hash值时，发现hash表中已经存在，则进行压缩，偏移量offset值置为9，重复长度为6，该值存入token值的低4位中；
5. 匹配压缩项后开始尝试扩大匹配，当窗口扫描到10-16时，发现并没有匹配到，则将此值存入hash表；如果发现hash表中有值，如果符合匹配条件（例如10-15符合1-6）则扩大匹配项，重复长度设为7，调整相应的token值
6. 这样滑动窗口扫描完所有的字符串之后，结束操作

最终，这样压缩过程就结束了，得到这样一个字节串[-110， 97， 98， 99， 100， 101， 95， 102， 103， 104， 9， 0， -112， 103， 104， 120， 120， 97， 104， 99， 100， 101]。

解压过程

lz4压缩串: [-110， 97， 98， 99， 100， 101， 95， 102， 103， 104， 9， 0， -112， 103， 104， 120， 120， 97， 104， 99， 100， 101]

二进制是字符串经过utf-8编码后的值

下图是对上面压缩串的解释：

1. 当lz4解压从0开始遍历时，先判断token值(-110)，-110转换为计算机二进制为10010010，高四位1001代表字面量长度为9，低四位0010代表重复项匹配的长度2 4(minimum repeated bytes)
2. 向后遍历9位，得到长度为9的字符串(abcde_fgh)，偏移量为9，从当前位置向前移动9位则是重复位起始位置，低四位说明重复项长度为6字节，则继续生成长度为6的字符串(abcde_)
3. 此时生成(abcde_fghabcde_)，接着开始判断下一sequence token起始位，最终生成abcde_fghabcde_ghxxahcde(压缩前的字符串)

LZ4 压缩器的核心是检测过去 64 KB 的重复数据。该格式既不假设也不限制压缩器在源数据块中搜索和选择匹配项的方式。例如，可以使用称为“完全优化解析”的技术以高 CPU 和内存成本达到压缩上限。但是可以考虑多种其他技术，具有不同的时间/性能权衡。只要遵守指定的格式，结果将与任何兼容的解码器兼容并可由其解码。

在当前的安卓和苹果操作系统中，内存压缩技术就使用的是lz4算法，及时压缩手机内存以带来更多的内存空间。本质上是时间换空间。

4、压缩性能对比

• 快速比较：单线程，Corei5-3340M@2.7GHz，使用Open-SourceBenchmarkbym^2(v0.14.2)

声明一下，以上内容，多为阅读其他大佬的文章，自己汇总，如有侵权，可联系删除。

文章来源：蔓蔓不慢_https://zhuanlan.zhihu.com/p/566312289

,