1 压缩算法概述

总述

在数据压缩领域里，文本压缩的历史最久，从Morse到Huffman和算术编码(Arithmetic coding)，再到基于字典和上下文的压缩算法。
各种算法不断改进，从通用算法，到现在更具针对性的算法，结合应用场景的垂直化的趋势越来越明显。
综上，在选择或者评价压缩算法，一定要结合实际应用场景加以考虑，包括：字符集、内容的大小、压缩及解压的性能、以及各端支持情况(特别是操作系统、浏览器和应用软件中)。

数据压缩算法

一套完整的压缩算法，实际以下几个部分：

其中，除编码外的三项目的都是找到一个适于编码的表示方法，而编码则是以简化的方法进行输出。
最典型的建模方法是基于字符的概率统计，而基于上下文的建模方法(Context Modeling)则是从文本内容出发，它们追求的目标都是让字符的出现概率越不平均越好。
转换方法是最具代表性的是基于词典的转换，比如庞大的LZ族系。Huffman和算术编码则是常见的编码方法。

因为语言本身的特性，基于上下文的建模方法(Context Modeling，如PPM*系列算法)可以得到更好的压缩比，但却由于它的性能问题却很难普及。当前比较流行的压缩算法中其突破的核心只有两个:

ANS (FSE是它的一个实现): Facebook zStd, Apple的lzfse等。

Context Modeling + LZ77 (编码是Huffman): Brotli, bz2也应用了其中的BWT算法。

下图为六种算法的压缩比测试的结果，分别针对一本英文小说，一本中文小说，和一份较小(4KB+)的中文混合的JSON数据。

其中PPM是Context Modeling的代表算法。

可以看到算法对字符集(中文与英文)和大小都是敏感的，表现各不相同。

算法思想的简述

Huffman编码受到了Morse编码的影响，背后的思想就是将最高概率出现的字母以最短的编码表示。比如英文中字母e出现概率为12%，字母z的出现概率还不到1%（数据来源:Letter Frequency）。
算术编码以及区间编码，它们是利用字符概率分布，将字符组合转变为概率的层次划分，最终转换一个固定的数字(算术编码和区间编码最大差别就在于一个使用小数，另一个使用整数)。可以对应下图考虑下AAAA，以及AAB的编码输出 (在0-1的轴上找到一个数字来表示。)。

参考维基上的说明:算术编码。上面这两类算法一直霸占着算法编码领域，各自拥有大量的变形算法。

Gzip

Gzip压缩原理是以Deflate压缩算法为基础，而Deflate算法是LZ77压缩算法的优化和Huffman编码的一个结合。

LZ77压缩算法

LZ77压缩算法是由Jacob Ziv 和 Abraham Lempel 于1977年提出，以此得名。
LZ77相关术语：

滑动窗口：编码的过程类似算法中“滑动窗口”算法的逻辑过程，包含look ahead buffer和search buffer

look ahead buffer（待检区）：

search buffer（搜索区）：

为了编码待编码区， 编码器在滑动窗口的搜索缓冲区查找直到找到匹配的字符串。
匹配字符串的开始字符串与待编码缓冲区的距离称为“偏移值”，匹配字符串的长度称为“匹配长度”。编码器在编码时，会一直在搜索区中搜索，直到找到最大匹配字符串，并输出(o, l )，其中o是偏移值， l是匹配长度。然后窗口滑动l，继续开始编码。如果没有找到匹配字符串，则输出(0, 0, c)，c为待编码区下一个等待编码的字符，窗口滑动“1”。
LZ77压缩逻辑示例：

示例元素：ABCCABCAD

搜索区长度：5

待检区长度：3

搜索前，搜索区和待检区以及字符串状态，搜区区为空，待检区内进入了三个元素，如图所示
待检区检查第一个元素A，发现搜索区没有匹配项目，因此元素A按照原码记录，如下图
依次检查后面的元素B和C，发现搜索区没有与之相匹配的重复元素，因此按照源码记录

下面检查元素C，发现在搜索区有该元素，因此使用（offset，length）编码元素C，即（1，1），如图：
后面进行元素A匹配，发现匹配项，然后在继续一位元素B，即AB元素，也发现匹配，最后找到ABC在搜素区找到匹配项，因此使用（4，3）进行对ABC元素的编码，后续查找方式类似，知道遍历元素末尾

当所有元素遍历完毕之后，会得到一个新的经过编码的表示串，即：ABC(1,1)(4,3)(2,1)D

可以看出LZ77算法的中心思想就是利用数据的重复结构信息来进行数据压缩。

通过LZ77对数据进行初步的压缩之后，后续通过Huffman编码再次进行数据压缩，下面看下Huffman coding的原理。

Huffman coding

相信很多人对Huffman这个词并不陌生，因为它是大学里面数据结构课程的一个算法内容。
该算法依据元素出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

哈夫曼编码，核心逻辑是根据使用频率来最大化节省字符（编码）的存储空间。通过较大的字符串表示频率小的字符串，相应的通过较小字符串表示出现频率比较大的字符串，通过这个差值减少元素串的尺寸。

下面以元素串【emm tell me the truth】为例子，演示Huffman编码过程以及结果：

首先扫面原元素串，统计每个元素的出现频率信息

依据二叉树的规则，将元素信息以出现频率为权重，构造一个最优二叉树，示例树如图所示：
根据既定路径规则（左子树路径：0，右子树路径：1），得到每个元素的Huffman编码如下所示：

上图展示了元素串：【emm tell me the truth】，经过Huffman编码后用位串表示：【01 110 110 00 01 100 100 110 01 00 101 01 00 1110 1111 00 101】。可以看到Huffman编码占用比较少的位来描述元素信息，且频率高的元素使用的描述位比较少。

Snappy

LZ4

LZ4以其超高的吞吐量而出名，它的压缩和解压缩速度非常快，其底层压缩原理特使参考了LZ77算法，在其基础之上做了优化，可以粗暴的理解为是一个用16k大小哈希表储存字典并简化检索的LZ77。
在LZ77算法进行压缩时，耗时最多的部分是在字典中找到待搜索缓存中最长的匹配字符。若是字典和待搜索缓存过短，则能找到匹配的几率就会很小。所以LZ4对LZ77针对匹配算法进行了改动。
首先，LZ4算法的字典是一张哈希表。字典的key是一个4字节的字符串，每个key只对应一个槽，槽里的value是这个字符串的位置。
LZ4没有待搜索缓存，而是每次从输入文件读入四个字节，然后在哈希表中查找这字符串对应的槽，下文称这个字符串为现在字符串。如果已经到最后12个字符时直接把这些字符放入输出文件。如果槽中没有赋值，那就说明这四个字节第一次出现，将这四个字节和位置加入哈希表，然后继续搜索。如果槽中有赋值，那就说明我们找到了一个匹配值。
LZ4压缩的数据结构：

Token：令牌长为1字节，其中前4个字为字面长度(literal length)，而其后4个字为匹配长度(match length)

Literal length：literal长度超长补充

literals：非编码元素

Offset：偏差，和LZ77中的offset一样的含义，表示距离重复串的index

Match length：match串长度超长补充

ZSTD

Zstd (Zstandard) 是由 Facebook 开源的快速无损压缩算法，主要应用于 zlib 级别的实时压缩场景，并且具有更好的压缩比。
Zstd 还可以以压缩速度为代价提供更强的压缩比，速度与压缩率的比重可通过增量进行配置。
Zstd 是一项性能优秀的压缩技术，与 zlib、lz4、xz 等压缩算法不同，Zstd 寻求的是压缩性能与压缩率通吃的方案。Zstd 还为小数据提供了一种特殊的压缩模式 “字典压缩”，支持以训练方式生成字典文件，以提高对小数据包的压缩率。

压缩算法性能对比

X 参考文献

Apache common-compress : https://commons.apache.org/proper/commons-compress/examples.html
GzipUtil、LZ4Util、SnappyUtil、ZipUtil、TarUtil、CompressUtil

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-compress</artifactId>
    <version>1.21</version>
</dependency>

标签：编码,Huffman,元素,算法,概述,LZ77,压缩算法,数据压缩
From： https://www.cnblogs.com/johnnyzen/p/18324406

[数据压缩] 压缩算法概述