2020编码大赛(3)无损压缩算法

举报
用户已注销 发表于 2021/11/19 03:21:15 2021/11/19
【摘要】 无损压缩算法,按照我的理解,可以分为三大块知识:直接编码、转换、上下文编码。   一,直接编码 1,哈夫曼编码 哈夫曼编码就是把各个字符转换成不同长度的01串,按照固定的替换规则全文替换即可。 当然,哈夫曼编码的依据,可以是硬编码的,也可以是根据文本内容统计计算出来的。 2,算术编码、区间编码 这2个编码方式在我...

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

 

一,直接编码

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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200