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

导读一、压缩原理通俗地说，压缩就是找出那些重复出现的字符串，然后用更短的符号代替，从而达到缩短字符串的目的。比如，有一篇文章大量使用"中华人民共和国"这个词语，....一、压缩原理

通俗地说，压缩就是找出那些重复出现的字符串，然后用更短的符号代替，从而达到缩短字符串的目的。比如，有一篇文章大量使用"中华人民共和国"这个词语，我们用"中国"代替，就缩短了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占用率，压缩耗时：