压缩算法基础#
一堆数据相当于一块海绵，可以通过压缩算法来压缩其体积，但是最终不能够无限制的进行压缩，最多把海绵中的空气挤出来不能够把海绵本身完全挤没。
无损压缩算法#
无损压缩算法可以保证数据不被丢失。
常见的无损压缩算法有哈夫曼编码、字典编码、预测编码
有损压缩算法#
顾名思义，这种算法会导致数据部分损失，适用于媒体传输，对数据的完整性要求不高的场景。
常见的有损压缩算法有转换编码、量化、基于模型的压缩
LZ77压缩算法#
简介#
LZ77算法是一个无损压缩算法，是一种基于字典的压缩算法，现代很多压缩算法都是基于LZ77。
原理介绍#
定义以下几个：
- lookahead buffer 等待编码的区域
- search buffer 已经编码的区域，搜索缓冲区，也有一个大小（其实就是字典）
- sliding window 滑动窗口，一个固定长度
从待编码区域的第一个数据开始，从已编码区域中寻找这样的一个子串，使得子串和待编码区域起始位置的串相同。如果能找到这样的一个串，则返回一个组**（O,L），其中O表示两个匹配串的偏移值，即待编码区第一个数据到已编码数据**中串的第一个数据；L表示找到的串的长度。
一旦找到一整个串，就将这个待编码区的串全部放到已编码区中，并且返回那个组。
如果从第一个数据开始就没有找到对应串，则返回一个**（0,0,Byte），其中Byte是这个待编码区没有找到的串，并且将这个数据放进已编码区**。
对一个要进行编码的串，编码之后就会变成一系列的组，然后这个组本身就代表了压缩前的字符串。
简单代码实现。
解压缩#
有了一整个压缩后的串之后，就从前往后对每一个组进行解码。
- 如果是（0,0,Byte）类型的组，则直接还原Byte的这个字符。
- 如果是（O,L）这样的组，则向前寻找通过偏移量和串长度，找到这个位置应该是字符。
缺陷#
原本的数据是一系列的字符，那么将这些字符转化成一系列的组按理说可以减少编码的字符数量。
实际上，我们想象一个字符串，其中每一个字符第一次出现时都需要以一个组（0,0,Byte）表示，那么也就是将一个字符变成了三个字符！在这里就会失去压缩的意义，因为数据竟然变多了。当然我们可以将（0,0,Byte）进行特殊处理，将其直接记为Byte。
再想象一下，如果在待编码区遇到了一个数据，这个数据在已编码区出现过，那么就用一个组来表示它，也就是一个字符变成了两个字符！和上面类似，直接用一个字符来记录它。
再一次考虑一种情况，这个待编码区的子串长度为2，那么会用两个字符的组来表示，也就是说数据量基本没有被压缩。
以上的情况告诉我们，当串的长度小于三时，压缩是没有意义的，空间并不能够被压缩
LZ78算法#
简介#
LZ78和LZ77类似，但是不是采用滑动窗口而是字典的形式。
原理介绍#
从前向后进行编码，会遇到以下三种情况，进行不同的操作。
- 第一次遇到一个字符，也就是这个字符不在字典当中，将其表示为（0,Byte），并且将这个字符做一个顺序的索引存入字典，（n,Byte），n为存入字典的顺序。
- 如果这个字符在字典当中，则在字典中寻找以这个字符为前缀的最长串，然后将这个最长串和往后的一个字符，表示为（n,Byte），这里的n表示字典中的最长串在字典中的顺序，后面的Byte表示往后的一个字符。这个表示就是压缩后的形式，并且将这个最长串和往后的这个字符按顺序加入到字典中，也是按照一个组（n,Byte）的形式加入。
- 如果最后一个串，是已经在字典中存在的串，也就是其后不存在多余的那个字符，则直接（n,）来表示，n表示这个串在字典中的顺序。
简单实现
解压缩#
- 如果遇到（0,Byte）类型的组，则直接恢复这个字符，并且将这个字符加入字典。
- 如果遇到了其他类型的组，则在字典中寻找字符，并且加上后面自带的那个字符。
- 将所有的压缩后的表示形式进行展开。