深入理解gzip原理

gzip 使用deflate算法进行压缩。gzip 对于要压缩的文件，首先使用LZ77算法的一个变种进行压缩，对得到的结果再使用Huffman编码的方法

和平ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：18980820575（备注：SSL证书合作）期待与您的合作！

如果文件中有两块内容相同的话，那么只要知道前一块的位置和大小，我们就可以确定后一块的内容。所以我们可以用（两者之间的距离，相同内容的长度）这样一对信息，来替换后一块内容。由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。

举一个例子

有一个文件的内容如下

其中有些部分的内容，前面已经出现过了，下面用()括起来的部分就是相同的部分。

( .)nease(.net )

我们使用 (两者之间的距离，相同内容的长度) 这样一对信息，来替换后一块内容。（22,13)中，22为相同内容块与当前位置之间的距离，13为相同内容的长度。(23,4)中，23为相同内容块与当前位置之间的距离，4为相同内容的长度。由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。

LZ77算法使用"滑动窗口"的方法，来寻找文件中的相同部分，也就是匹配串.

解压缩：

从文件开始到文件结束，每次先读一位标志位，通过这个标志位来判断下面是一个(之间的距离，匹配长度) 对，还是一个没有改动的字节。如果是一个（之间的距离，匹配长度）对，就读出固定位数的（之间的距离，匹配长度）对，然后根据对中的信息，将匹配串输出到当前位置。如果是一个没有改动的字节，就读出一个字节，然后输出这个字节。

LZ77压缩时需要做大量的匹配工作，而解压缩时需要做的工作很少，也就是说解压缩相对于压缩将快的多。这对于需要进行一次压缩，多次解压缩的情况，是一个巨大的优点。

深入理解

要理解这种算法，我们先了解3个关键词:短语字典，滑动窗口和向前缓冲区。

前向缓冲区

每次读取数据的时候，先把一部分数据预载入前向缓冲区。为移入滑动窗口做准备

滑动窗口

一旦数据通过缓冲区，那么它将移动到滑动窗口中，并变成字典的一部分。

短语字典

从字符序列S1...Sn，组成n个短语。比如字符(A,B,D) ,可以组合的短语为{(A),(A,B),(A,B,D),(B),(B,D),(D)},如果这些字符在滑动窗口里面，就可以记为当前的短语字典，因为滑动窗口不断的向前滑动，所以短语字典也是不断的变化。

LZ77的主要算法逻辑就是，先通过前向缓冲区预读数据，然后再向滑动窗口移入（滑动窗口有一定的长度），不断的寻找能与字典中短语匹配的最长短语，然后通过标记符标记。

当压缩数据的时候，前向缓冲区与移动窗口之间在做短语匹配的是后会存在2种情况:

短语标记包含三部分信息：（滑动窗口中的偏移量（从匹配开始的地方计算）、匹配中的符号个数、匹配结束后的前向缓冲区中的第一个符号）。

我们采用图例来看:

1、开始

2、滑动窗口中没有数据，所以没有匹配到短语，将字符A标记为A

3、滑动窗口中有A,没有从缓冲区中字符（BABC）中匹配到短语，依然把B标记为B

4、缓冲区字符（ABCB）在滑动窗口的位移6位置找到AB,成功匹配到短语AB,将AB编码为(6,2,C)

5、缓冲区字符（BABA）在滑动窗口位移4的位置匹配到短语BAB,将BAB编码为(4,3,A)

6、缓冲区字符（BCAD）在滑动窗口位移2的位置匹配到短语BC，将BC编码为（2,2,A）

7、缓冲区字符D,在滑动窗口中没有找到匹配短语，标记为D

8、缓冲区中没有数据进入了，结束

解压类似于压缩的逆向过程，通过解码标记和保持滑动窗口中的符号来更新解压数据。

我们还是采用图例来看下:

1、开始

2、符号标记A解码

3、符号标记B解码

4、短语标记(6,2,C)解码

5、短语标记(4,3,A)解码

6、短语标记(2,2,A)解码

7、符号标记D解码

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

哈夫曼树也叫最优二叉树（哈夫曼树）

问题：什么是哈夫曼树？

例：将学生的百分制成绩转换为五分制成绩：≥90 分: A，80～89分: B，70～79分: C，60～69分: D，＜60分: E。

判别树：用于描述分类过程的二叉树。

如果每次输入量都很大，那么应该考虑程序运行的时间

如果学生的总成绩数据有10000条，则5％的数据需 1 次比较，15％的数据需 2 次比较，40％的数据需 3 次比较，40％的数据需 4 次比较，因此 10000 个数据比较的

次数为： 10000 (5％＋2×15％＋3×40％＋4×40％)＝31500次

此种形状的二叉树，需要的比较次数是：10000 (3×20％＋2×80％)＝22000次，显然：两种判别树的效率是不一样的。

问题：能不能找到一种效率最高的判别树呢?

那就是哈夫曼树

树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：

其中，n表示叶子结点的数目，wi和li分别表示叶子结点ki的权值和树根结点到叶子结点ki之间的路径长度。

赫夫曼树（哈夫曼树，huffman树）定义：

在权为w1,w2,…,wn的n个叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树称为赫夫曼树或最优二叉树。

例：有4 个结点 a, b, c, d，权值分别为 7, 5, 2, 4，试构造以此 4 个结点为叶子结点的二叉树。

WPL=7´2+5´2+2´2+4´2= 36

WPL=7´3+5´3+2´1+4´2= 46

哈夫曼树的构造(哈夫曼算法)

1.根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.

2.在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.

3.在F中删除这两棵树,同时将新的二叉树加入F中.

4.重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)

哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。

例：如果需传送的电文为 ‘ABACCDA’，它只用到四种字符，用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00, 01,10, 11，则上述电文便为 ‘00010010101100’（共 14 位），译码员按两位进行分组译码，便可恢复原来的电文。

能否使编码总长度更短呢？

实际应用中各字符的出现频度不相同，用短（长）编码表示频率大（小）的字符，使得编码序列的总长度最小，使所需总空间量最少

数据的最小冗余编码问题

在上例中，若假设 A, B, C, D 的编码分别为 0，00，1，01，则电文 ‘ABACCDA’ 便为 ‘000011010’（共 9 位），但此编码存在多义性：可译为： ‘BBCCDA’、‘ABACCDA’、‘AAAACCACA’ 等。

译码的惟一性问题

要求任一字符的编码都不能是另一字符编码的前缀，这种编码称为前缀编码（其实是非前缀码）。 在编码过程要考虑两个问题，数据的最小冗余编码问题，译码的惟一性问题，利用最优二叉树可以很好地解决上述两个问题

以电文中的字符作为叶子结点构造二叉树。然后将二叉树中结点引向其左孩子的分支标 ‘0’，引向其右孩子的分支标 ‘1’； 每个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如此得到的即为二进制前缀编码。

编码： A：0， C：10，B：110，D：111

任意一个叶子结点都不可能在其它叶子结点的路径中。

用哈夫曼树设计总长最短的二进制前缀编码

例：如果需传送的电文为 ‘ABACCDA’，即：A, B, C, D 的频率（即权值）分别为 0.43, 0.14, 0.29, 0.14，试构造哈夫曼编码。

编码： A：0， C：10， B：110， D：111 。电文 ‘ABACCDA’ 便为 ‘0110010101110’（共 13 位）。

译码

从哈夫曼树根开始，对待译码电文逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。

电文为 “1101000” ，译文只能是“CAT”

gzip怎么压缩和怎么解压缩文件到其他目录

解决：gzip -c test.txt /root/test.gz，文件流重定向，解压也是，gunzip -c /root/test.gz ./test.txt

经验：更常用的命令tar同样可以解压*.gz，参数为-c

附gzip帮助文件

GZIP(1)                     General Commands Manual                    GZIP(1)

NAME

 gzip, gunzip, zcat - compress or expand files

SYNOPSIS

 gzip [ -acdfhlLnNrtvV19 ] [-S suffix] [ name ...  ]

 gunzip [ -acfhlLnNrtvV ] [-S suffix] [ name ...  ]

 zcat [ -fhLV ] [ name ...  ]

OPTIONS

 -a --ascii

        Ascii text mode: convert end-of-lines using  local  conventions.

        This  option  is  supported  only  on some non-Unix systems. For

        MSDOS, CR LF is converted to LF when compressing, and LF is con‐

        verted to CR LF when decompressing.

 -c --stdout --to-stdout

        Write  output on standard output; keep original files unchanged.

        If there are several input  files,  the  output  consists  of  a

        sequence  of  independently compressed members. To obtain better

        compression, concatenate  all  input  files  before  compressing

        them.

 -d --decompress --uncompress

        Decompress.

 -f --force

        Force compression or decompression even if the file has multiple

        links or the corresponding file already exists, or if  the  com‐

        pressed data is read from or written to a terminal. If the input

        data is not in a format recognized by gzip, and  if  the  option

        --stdout  is  also  given, copy the input data without change to

        the standard output: let zcat behave  as  cat.   If  -f  is  not

        given,  and  when not running in the background, gzip prompts to

        verify whether an existing file should be overwritten.

 -h --help

        Display a help screen and quit.

 -l --list

        For each compressed file, list the following fields:

            compressed size: size of the compressed file

            uncompressed size: size of the uncompressed file

            ratio: compression ratio (0.0% if unknown)

            uncompressed_name: name of the uncompressed file

        The uncompressed size is given as -1 for files not in gzip  for‐

        mat,  such  as compressed .Z files. To get the uncompressed size

        for such a file, you can use:

            zcat file.Z | wc -c

        In combination with the --verbose option, the  following  fields

        are also displayed:

            method: compression method

            crc: the 32-bit CRC of the uncompressed data

            date time: time stamp for the uncompressed file

        The  compression  methods  currently supported are deflate, com‐

        press, lzh (SCO compress -H) and pack.   The  crc  is  given  as

        ffffffff for a file not in gzip format.

        With  --name,  the  uncompressed name,  date and time  are those

        stored within the compress file if present.

        With --verbose, the size totals and compression  ratio  for  all

        files  is  also  displayed,  unless some sizes are unknown. With

        --quiet, the title and totals lines are not displayed.

 -L --license

        Display the gzip license and quit.

 -n --no-name

        When compressing, do not save the original file  name  and  time

        stamp by default. (The original name is always saved if the name

        had to be truncated.) When decompressing,  do  not  restore  the

        original  file name if present (remove only the gzip suffix from

        the compressed file name) and do not restore the  original  time

        stamp if present (copy it from the compressed file). This option

        is the default when decompressing.

 -N --name

        When compressing, always save the original file  name  and  time

        stamp;  this  is  the  default.  When decompressing, restore the

        original file name and time stamp if  present.  This  option  is

        useful on systems which have a limit on file name length or when

        the time stamp has been lost after a file transfer.

 -q --quiet

        Suppress all warnings.

 -r --recursive

        Travel the directory structure recursively. If any of  the  file

        names  specified  on the command line are directories, gzip will

        descend into the directory and compress all the files  it  finds

        there (or decompress them in the case of gunzip ).

 -S .suf --suffix .suf

        When compressing, use suffix .suf instead of .gz.  Any non-empty

        suffix can be given, but suffixes other than .z and  .gz  should

        be  avoided  to  avoid  confusion  when files are transferred to

        other systems.

        When decompressing, add .suf to the beginning  of  the  list  of

        suffixes to try, when deriving an output file name from an input

        file name.

        pack(1).

 -t --test

        Test. Check the compressed file integrity.

 -v --verbose

        Verbose. Display the name and percentage reduction for each file

        compressed or decompressed.

 -V --version

        Version. Display the version number and compilation options then

        quit.

 -# --fast --best

        Regulate the speed of compression using the specified  digit  #,

        where  -1  or  --fast  indicates  the fastest compression method

        (less compression) and -9 or --best indicates the  slowest  com‐

        pression  method  (best  compression).   The default compression

        level is -6 (that is, biased towards high compression at expense

        of speed).

golang中compress/flate包

官方标准库对flate包的定义是：flate包实现了deflate压缩数据格式，参见 RFC 1951 。gzip包和zlib包实现了对基于deflate的文件格式的访问。

这边什么是deflate？

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

1）func NewReader(r io.Reader) io.ReadCloser

2）func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser

3）func NewWrite(w io.Write, level int) (*Write, error)

4）func NewWriteDict(w io.Writer, level int, dict []byte) (*Writer, error)

5）func (e InternalError) Error() string

6）func (e *ReadError) Error() string

7）func (e *WriteError) Error() string

8）func (w *Writer) Close() error

9）func (w *Writer) Flush() error

9）func (w *Writer) Reset(dst io.Writer)

10）func (w *Writer) Write(data []byte) (n int, err error)

非常好的一个资源链接：

如果有很好的资源，欢迎在评论区留言分享

zstd，未来可期的数据压缩算法

最近了解到了 zstd 这种新的压缩算法。不像lz4，lzo，snappy等近几年流行的压缩算法专注于压缩和解压缩性能，zstd在性能不错的同时号称压缩率跟Deflate（zip/gzip的算法）相当。下面是 官网 列出的数据：

我们知道，压缩算法的效果和性能跟被压缩的数据类型和模式有很大的关系，光看别人的测试数据、benchmark是不够的。正好有功能开发需要，于是结合我们的使用场景真实测试的一下。

惊喜的是，实测的结果比官方提供的还好，终于找到了我们的cup of tea。

Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz, 8G内存

CentOS 7.0

对几种支持流式写入的压缩算法，使用对应的命令行工具进行压缩测试。

除了snappy，各种压缩算法/工具都支持设置压缩级别，高级别意味着以更长的压缩时间换取更高的压缩率。

100万行不重复的某个应用的日志文件，大小为977MB。

从上面可以看出：

zstd无论从处理时间还是压缩率来看都占优。snappy, lz4, lzo的压缩率较低，但压缩速度都很快，而zstd甚至比这些算法更快。Gzip的压缩率比lz4等高不少，而zstd的压缩率比gzip还提升一倍。

如果从上面的比较还不是特别直观的话，我们再引入一个创造性的指标（从网上其他压缩算法对比没有见过使用这项指标）：

代表单位处理时间可以压缩去掉多少冗余数据。其中 权重系数 用来指定压缩率和压缩速度哪个更重要，这里我们认为在我们的使用场景里两者同样重要，取系数为1。

从这里我们可以明显看出， zstd lz4 lzo snappy 其他 。

对1000行、大小约为1MB的文件进行压缩测试，各种算法的压缩率跟1GB大文件的压缩率几乎一样。

下面再对更小的数据量——10行日志数据的压缩率进行对比。虽然我们的使用场景里没有对小数据量的压缩处理，但还是比较好奇zstd字典模式的效果。

其中最后一组数据为zstd使用10000行日志进行训练生成字典文件，并利用字典文件辅助压缩测试数据。

可以看出来，除了zstd字典模式外，各种压缩算法在处理更小的数据量时压缩率都下降很多。而zstd字典模式对压缩率带来帮助非常明显，与gzip对比，压缩率从1000行时相差1倍，到10行时变为了相差接近3倍。

下一篇文章将给大家对比这几种算法的golang开源库的性能和压缩率。敬请期待。

当前文章：go语言gzip压缩 go语言打包
本文路径：http://pwwzsj.com/article/dogcgjh.html