2020编码大赛（3）无损压缩算法

无损压缩算法，按照我的理解，可以分为三大块知识：直接编码、转换、上下文编码。

一，直接编码

1，哈夫曼编码

哈夫曼编码就是把各个字符转换成不同长度的01串，按照固定的替换规则全文替换即可。

当然，哈夫曼编码的依据，可以是硬编码的，也可以是根据文本内容统计计算出来的。

2，算术编码、区间编码

这2个编码方式在我理解差不多，根据不同字符的概率不一样，把一个字符串编码成一个实数。

二，转换

1，游程编码    Run-Length Encoding

输入: AAABBCCCCDEEEEEEAAAAAAAAA
输出: 3A2B4C1D6E9A

这种转换，是字符到字符的转换，转换之后，仍然可以用哈夫曼编码等从字符转换成二进制。

2，BWT转换算法    Burrows-Wheeler Transform

BWT算法，就是压缩之前把字符串A转换成字符串B，压缩B即可，解压的时候得到B之后，再把B转换成A。

例如字符串“banana#”转换为了“annb#aa，其中#是算法添加的特殊标识符。

如果字符串比较长，转换后的字符串可以出现很长的一段相同字符，所以BWT转换之后再用别的压缩算法，比如LZW，可以提高LZW的压缩率。

3，滑动窗口（LZ系列算法）

如果ABCDE出现两次，第一次出现是在下标3处，第二次出现是在下标13处，那么第二次出现的ABCDE就可以用二元组（10,5）表示

三，上下文编码

上下文编码，如PPMD、PAQ 利用的是上下文预测，消除二进制串的重复，达到压缩的目的。

四，复合压缩算法

常见的压缩算法，都是转换+编码

1，LZW

初始化字典为255个字符，随着压缩的过程，字典一步步扩充，最终把全文本转换成字典的id序列，再用变长编码的方法，把id序列编码成二进制。

2，deflate

LZ77 + 哈夫曼编码

3，LZMA

LZ77 + 区间编码

五，我对压缩算法的理解

1，压缩算法能接力吗？

不能，无论是先用A压缩再用A压缩，还是先用A压缩再用B压缩，都没有效果。

2，有没有一种无损压缩算法，保证压缩之后一定比原数据要小？

不存在，无损压缩是一种从二进制流到二进制流的一一映射，任何一种无损压缩算法，都能找到某个二进制流，使得用这个算法压缩之后长度不变或变长。

也就是说，当数据有重复信息的时候，通过去除重复信息可以压缩数据量，但是如果数据没有任何重复信息，压缩率可能就是接近1或者超过1

3，压缩算法为什么不能接力？

简单理解，数据可以分为文本信息、二进制流、图片等。

这里的二进制流指的是随机二进制流，比如一个常见的exe，它的二进制流就几乎是随机的，压缩算法很难压缩。

理论上来讲，所有数据都是二进制流，都是0和1组成的序列，但是数据的属性决定了我们如何理解数据。

比如一个通用英文文本，虽然也是二进制串，但是26个英文字母的ASCII码对应的8个比特，肯定是大量出现的。

所有的算法，经过压缩之后，都会变成二进制流，剩下的重复信息就很少了。

所有的算法，都是几乎无法压缩二进制流的。

4，BWT转换算法，只涉及把字符重排，是否可以用在所有压缩算法上？比如先用BWT转换再用PPMD？

不行。通用英文文本，先用BWT转换再用PPMD，压缩率比单纯的PPMD还小。

BWT转换可以提高某些算法的压缩率，比如LZW，但是并不能提高所有算法的压缩率。

因为，同样的二进制流，不同的压缩算法有不同的理解角度，并不是每个角度看来，字符串重排都变得更加规整。

例如，我的算法依据是，当一个单词是字母e开头的时候，下一个字母大概率是n，（随便举的例子）

也就是说空格符合字母e连续出现的话，下一个字母大概率是n，那么这就是我消除重复的一个依据，如果重排就没有这个依据了。

这里说的对数据的理解角度，还有算法依据，其实都是数据本身的特点。

5，数据有哪些特点可以用来压缩？这些特点是怎么来的？

如果把01串看成数列，那么所有我们能想到的数列规律，都能以某种形式展现在某个01串的，但是并不是所有的都能用来压缩。

反过来，对于一个01串，可以用任意角度去理解它，如果某个角度看来，它具有一种重复性的规律，那么就可以用来压缩。

这么说还是太主观了，或许还是用熵来表述更为精确。

数据的特点，自然是来自产生数据的源，比如文本，来自人类交流的语料库，有语法限制，字母按照一定的规则组合成词，汉字按照一定的规则组合成词，比如图片，来自大自然，由于地球（宇宙）上的原子排列是有规律的，原子都是扎堆出现的，而光学原理是简洁而和谐的，所以拍出来的照片总是以色块的形式展现出来。

再比如，假设我在手算圆周率Pi，需要记录一串实数：

3,   3.1,   3.14,   3.141,   3.1415   ......

显然，这串数据把它当做通用文本压缩，也会有不错的压缩率，应该比一般的通用文本压缩率更高。

但是，如果我确定所有的数据都是Pi的前若干位，而Pi的前10000万都是确定的，那么以此规律为基础，就可以自创一个压缩算法，针对此类数据压缩率很高。

上面的串其实就可以转换成0   1   2   3   4   ......

如果规律变得复杂一点，每个数都是Pi的前若干位向上或者向下取整，比如：

3,   4,   3.1,   3.2,   3.14,   3.15   ......

那么，压缩算法肯定要复杂一点。

如果再允许一点误差，比如3.16也是有可能出现的，但是统计规律显示3.16出现的概率远小于3.14和3.15，那么我们仍然可以定制压缩算法，使得压缩率远高于通用压缩算法。

总之，数据的特点，无论是数学公式的强规律，还是基于统计的弱规律，都可以用来压缩。

6，什么是信息？什么是熵？

信息是由数据来承载的。

个人理解：数据的信息，是一个主观的属性，而信息的信息熵，是一个客观的属性。

就像文本，它所传达的信息到底是01串还是字符串，这是一个主观的，甚至我们可以把某个01串先按照计算公式转换成3,   3.1,   3.14,   3.141,   3.1415   ...... ，再按照Pi的数值作为对照表，把序列转换成0   1   2   3   4   ......，然后说这才是这个01串表达的信息。

也就是说，信息是由数据+理解数据的角度决定的。

而在每一个角度之下，这个数据的信息熵都是一个确定的量，同一个数据在不同的角度下信息熵不一样。

再举个例子，如果一个文本全都是数字和空格组成的，那么我们可以说，这个文本熵比较低。

如果我们又知道，这个文本其实是一串正整数的最简表示，那么它的熵更低了，因为我们排除了形如01 02 03这样的文本，因为01不是任何正整数的最简表示，当然，形如额外约定用第一个数字表示正负的规则除外，这又是一种新的理解这个文本的角度。

所以，这个文本可以是这样的：1   3     124    56     2     38   ......

如果我们又知道，每个整数都是素数，比如2     13    5    7   11   5    97  ...... 这样的串，那么熵就更低了。

所以，熵表示的是不确定性，规律越严格，熵越低。

热力学里面的熵，和信息学里面的熵，本质上是一样的。

PS：2     13    5    7   11   5    97  ...... 这样的素数串，如果看做通用文本，先用BWT转换，再用任何压缩算法压缩都不好用了。

这也是一个例子，可以用来帮助理解为什么BWT转换针对文本并不具有普适性。

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/109391616