文本压缩算法
以gzip为例
http://staff.ustc.edu.cn/~yuzhang/ds/gzip/gzip_principle.htm
先用LZ77算法压缩，在一定窗口内压缩重复字符串。
然后分组使用霍夫曼编码，依据比特出现频率重新编码。
DEFLATE算法 = LZSS + Huffman encoding
Run Length Encoding 利用空间上相邻且重复的符号来压缩，比如aaaa → a4。只能处理发生在相邻的地方的冗余，比如无法压缩abababab。
我们需要处理跨序列的冗余
Lempel-Ziv LZ77算法
改进版本LZSS，用于zip和png
look ahead buffer
前向引用偏移+序列长度，引用序列和当前序列可以重叠，在某个特殊情况下就变成了run length encoding
图片压缩算法
bmp，完全原始的图片比特
用gzip对bmp进行压缩
无损图片压缩，以png为例
https://www.bilibili.com/video/BV1wY4y1P7o7
当你面对一个每个像素都递增的图片，用LZSS不好使，因为并没有重复序列，每个像素都不太相同。用霍夫曼编码也不行，因为像素的可能值太多了，同时将每个像素视为相互独立，也没有利用空间上的冗余。
解决方案，在滤波过程中转化出可利用的冗余。比如可以使用相邻像素的差值来表示图片，这样对像素值递增的图片就能用LZSS了，而且如果原来序列能用LZSS，新序列应该对应的地方也能用。
png算法自带许多种滤波器，NONE,SUB,UP,AVG,PAETH，原理都差不多。
那么什么使用使用滤波器呢？当每个像素值取值范围不大时就没必要用，每个像素不到一个字节也没必要用。
在每一行选择什么滤波器呢？一种启发式算法，Minimum sum of absolute differences
总的来说，filtering → LZSS → Huffman encoding
后两者也就是deflate算法，因为设计png时已经有了开源的zlib，所以实际上只用处理filtering就行了
编码实在慢，但是解码快，所以问题不是太大。
png标准：https://www.w3.org/TR/png/
最近出现，QOI，无损，压缩率相似，O(n)复杂度，更快！
QOI标准：https://qoiformat.org/qoi-specification.pdf
https://qoiformat.org/
主要有四条简单规则：1. run length encoding 2. 对之前出现过的像素进行哈希索引来复用 3. 记录与之前像素的差(小,一字节版) 4. 记录与之前像素的差(大,两字节版)
听起来很随意也很简单，但是就是能充分利用图片数据自身的特性。
（据作者所说他也不是专业的，他只是试着实现了一下最简单的想法）
（有些时候也不用钻研太精巧复杂的算法，简单就是好）
（处理复杂性时，容易迷失在复杂性中，从而设计出一些复杂而且低效的东西）
有损图片压缩，以jpeg为例
https://www.bilibili.com/video/BV1iv4y1N7sq
能将图像有损压缩成原来的20~30分之一，怎么做到的呢？
首先因为人眼对亮度比色相更敏感
将RGB转化为YCbCr，然后对Cb(蓝色色度),Cr(红色色度)进行降采样，可以是平均也可以是选择一个固定位置的像素。Y指的是亮度。
这样就已经压缩到 1/3 + 1/3 * 1/4 + 1/3 * 1/4 = 1/2
上面只是利用人眼的感光特性进行了逐像素的压缩，还能怎么压呢？
- 自然界图像中以低频为主
- 人眼也对低频更敏感（想想近视眼嘛）
于是对图像采用离散余弦变换(DCT)，然后删除掉高频部分的表示，就能进行压缩。
DCT：
将离散数据改写成不同频率的离散余弦信号的叠加
需要多少个不同频率的离散余弦信号？如果输入的信号有N个，需要的不同频率的余弦信号也需要N个，频率分别为0, 2pi/(2N-1), 2pi2/(2N-1) … 2pi*(N-1)/(2*N-1)
（可能有误）
以他们为基，就能完全恢复出原来的信号了。这里没有压缩，占用的空间是一样的。
如何求出各个分量？对应相乘就可以了，因为正交分量会抵消掉。
也可以理解为乘上一个对应的正交矩阵，就完成了DCT。解码只需要乘一个逆矩阵就行。
二维的DCT变换是怎样的呢？简单来说就是对行做一次DCT，再对列做一次DCT变换。
应该说不管是先做行，还是先做列，结果都是一样的。（但自己并没有验证过）
jpeg是将图像分成88的块，然后对每个块做二维DCT的。
结果的88块中，每个数字都对应着一个二维的离散余弦图像模板。对它们加权和就能恢复原来的图像。
然后你观察一下变换后的8*8图像，就会发现大多数能量集中在低频。小部分在高频。
（据DCT提出者说，他本来想用KLT变换的，好像是能量集中的性质更好，但是计算很复杂。但最后发现用DCT近似就不错了）
发现只要1/64个系数，人眼就能分辨出来是啥了。1/4个系数就和原图差不多了。
jpeg是怎么处理高频分量的呢？变换后的8*8矩阵里面是浮点数，怎么转换成整数呢？
jpeg有一个量化表，对变换后的8*8矩阵除这个量化表然后取整就行了。想要恢复就乘这个量化表，可以看出量化表中的值越大，比如说是n，就意味着每隔个整数量化一下。原来的浮点数就近改成临近的整数。对低频来说，我们的量化值越小，对高频来说，量化值就可能上百，然而量化前数字的取值范围就大概是256，因此大概率会压成0.
接下来既然会出现大量的0，就意味着我们用普通的文本压缩思路来压缩就行了。
jpeg有不同的压缩质量选项，其实也就是有不同的量化表。压缩质量越高，量化表的数值就越小。量化表的数值是那帮人做肉眼实验测出来的。顺便，不同的channel比如Y,Cb/Cr的量化表也不同（因为视觉效果不同嘛）
量化后会出现大量的0，之后主要是run length encoding和huffman encoding这种无损压缩方法来处理。
它从左到右，从上到下，斜着Z形将二维矩阵拉成一条。目的是最大化连续0出现的可能。
这里的run length encoding在编码形式上有些改变，为了更好的压缩。当然也可以很好的适配huffman encoding
为了高效实现Huffman encoding，好像还挺麻烦的（
类似利用人对事物感知能力的冗余来做有损压缩的还有MP3，视频压缩编码等等