压缩算法
压缩算法是软件工程实践中经常需要用到的算法，在网络传输、数据存储方面我们都需要使用压缩算法来提高效率，在这篇博客我就分享一些比较出名的压缩算法，长期更新。
Gzip简介
gzip是用于UNIX系统的文件压缩算法，后缀为.gz的文件使用的就是gzip压缩过的文件，其背后的压缩算法被改造后，广泛应用于web应用。gzip的编码算法主要由两部分构成：LZ77算法和Huffman编码。
LZ77算法
LZ77压缩算法是由Jacob Ziv和Abraham Lempel在1997年提出的，它的核心思想是：如果文件中有两块内容相同的话，那么只需要知道前一块的位置和大小，后面的部分就可以用大小确定的信息替换掉。由于替换的信息大小小于文本本身的内容，所以文件得到了压缩。所以算法的关键就在于这个信息，定义为：**<两者之间的距离，相同内容的长度>**。
举个例子理解，假设文件内容如下：
1 | this.is.demo.hello |
那么文件中重复的信息块有两个，一个是this.is.，另一个是.hello，所以这些信息块第二次出现的时候我们就可以替换掉。按照上面的定义，替换后的结果为：
1 | this.is.demo.hello |
了解了压缩的原理后，我们来看看如何对一个文件进行压缩。首先压缩和解压缩的过程中，我们要知道接下来这个字节是否是被压缩了，这里需要用额外的一个位来记录，0表示后面的这个字节没有压缩，1表示后面这个字节压缩了。
同时，我们还必须有一个最小匹配长度，只有当两个信息块的匹配长度大于这个最小匹配长度，我们才会更换。举个极端的例子，我们不会把每一个重复出现的字母进行替换，因为替换后的信息比原有的字母占用的空间还大，达不到压缩的效果。
由于LZ77在压缩过程中需要使用滑动窗口扫描的方式，同时需要增加标记位、计算距离等信息，所以压缩开销很大，但解压时的工作相对就会较少，所以对于一次压缩多次解压的使用场景，LZ77压缩算法是一个不错的选择。
Huffman编码
Huffman编码相信大家都不陌生，其核心思路就是出现频率高的符号的编码长度短，出现频率低的符号的编码长度长。对于文件编码来说，我们把每一个字节都看作是一个编码单元，一个字节由8bits组成，看成是256个符号，所以我们Huffman编码就是对这256种符号的编码。Huffman树的具体实现和构成就不再这里赘述了。
