压缩算法

压缩算法基础

一堆数据相当于一块海绵，可以通过压缩算法来压缩其体积，但是最终不能够无限制的进行压缩，最多把海绵中的空气挤出来不能够把海绵本身完全挤没。

无损压缩算法

无损压缩算法可以保证数据不被丢失。

常见的无损压缩算法有哈夫曼编码、字典编码、预测编码

有损压缩算法

顾名思义，这种算法会导致数据部分损失，适用于媒体传输，对数据的完整性要求不高的场景。

常见的有损压缩算法有转换编码、量化、基于模型的压缩

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）类型的组，则直接恢复这个字符，并且将这个字符加入字典。
* 如果遇到了其他类型的组，则在字典中寻找字符，并且加上后面自带的那个字符。
* 将所有的压缩后的表示形式进行展开。

## Huffman压缩算法