知道什么是数据压缩吗？

关于数据压缩，你了解多少？压缩有极限吗？...

0

最近一周，我看了一部美剧，名字叫《硅谷》。

《Silicon Valley》目前出到了三季，讲述了一群不善社交的黑客程序猿，在美国硅谷创业的故事。



剧中男主创立了一家叫做 Pied Piper 的公司，自己写了一套非常牛逼的数据压缩算法，算法名称叫做 发散压缩算法。

BTW，如果对程序猿，或者从事计算机/互联网行业感兴趣的童靴，我推荐这部剧可以看看，对了解程序猿群体和硅谷创业文化，都非常有帮助。

现在移动互联网发展的火热，每个人每天光是拍照就会产生几百兆的图片文件，而存储空间在未来都会成为瓶颈。

以前我身边不管是用iPhone的朋友，还是用Android的朋友，一般情况下都买16G版本，而现在你在看看他们新换的手机，32G，64G都已经是常态。

1

从拍照产生的数据量，以及换高存储空间这两件事情来说，我们正身处一个信息数据爆炸的时代。

有相关的研究机构做过统计分析，以最近5年人类产生的数字话信息量，已经远超人类5000年的信息量总和。

也就是说，面对未来持续指数级增长的信息数据，会需要有更多的存储设备来保存我们全人类产生的数据。

互联网云计算提供商，诸如：谷歌Cloud，微软Azure云，百度云 等，如果他们在数据中心提供云端存储，能够将数据以极高的压缩比保存的话，无疑每年可以节省数千万美元。

如果真的有一家像《硅谷》中 Pied Piper 那样牛逼的压缩算法，在互联网公司中无疑是具有非常大的市场的。

那么，我们产生的数据，到底能够压缩到什么程度呢？压缩有极限值吗？我们平时在Windows系统下面用的WinRAR，7Zip，好压这些压缩软件，到底是怎么压缩我么的数据的呢？

带着这些问题，我们来看看什么叫做数据压缩。



2

压缩原理

我们的计算机中，数据都是以比特bit为最小单位存储下来的，而8个比特构成一个字节，一般而言字节是计算机程序可以作为整体操作的最小单位。

我们在电脑中看到的一个文件，不论是word，txt，还是其他什么格式，本质上都是有一个字节一个字节构成，存储在硬盘或者内存中。

压缩一个文件，其实原理非常简单：

尽最大努力找出文件中那些有规律的，重复性的字节，用一种预先约定俗成带有规则性的方式（算法），替换那些有规律的，重复性的字节，从而达到缩短文件总数据量的目的。

额，可能我给出的定义，对于一般没有相关背景知识的童靴不好理解。

举个栗子：

假设一篇文章中，大量使用“中华人民共和国”这个词，那么我们就可以指定一个“算法”，用 “中国” 来替换 “中华人民共和国”，你看，一下子就少了5个字不是。而如果我们用 “华” 来替换呢，一下子少了6个字。

上面只是简单的说明压缩是怎么一回事。



而在实际情况中，压缩有非常多的算法，不同的算法本质上，是为了寻找那些在文件中内容的概率分布。我们说，对于那些在文件中频繁出现的文字或者字节数据，我们就可以用更短的符号来替换，而对于那些概率非常小的部分，因为不可替代性，就无法用其他更短的符号来替换了。

一个数据内容概率分布越均匀，随机性越强，那么就越难以压缩。

换句话说，一个文件经过一次压缩，那么第二次第三次以后在压缩，压缩是越来越难的。

再举个栗子：

我们说数据内容毫不重复的话，我们就无法压缩了。

0123456789，这10个数字，按照符号替换规则，那么连一个数字都压缩不了；

3

压缩的极限

根据前面讲，我们可以知道，好的压缩算法，可以将数据内容冗余降到最低，以至于再也没有办法进一步压缩。所以，压缩已经压缩过的文件（递归压缩），通常是没有意义的。

那么任意一份数据，到底存在一个理论压缩极限吗？

答案是有极限的。

假设用数据记录抛硬币，一次只有正反两个结果，只需要0和1来表示，那么只需要一个二进制位就足够了。

而一次记录球赛，有胜负平三种结果，那么就需要2个二进制位才能表示一次结果。

依次而推，在概率均匀分布的情况下，假定一个字符（或字符串）在文件中出现的概率是p，那么在这个位置上最多可能出现1/p种情况。需要log2(1/p)个二进制位表示替代符号。（注意对数的底数是2，因为计算机由0和1构成，每个比特都构成2的N次幂）

通过简单的高等数学知识，我们就可以推广到通用的情况：

一个数据文件中有n个部分，每个部分在数据中出现的概率分别为 p1、p2、...pn,那么根据替换性原则，一共需要的最少二进制位数为：

log2(1/p1) + log2(1/p2) + ... + log2(1/pn)

= ∑ log2(1/pn)

这就是压缩极限。

压缩工具有很多种，对应实现的压缩算法也有很多种，但是它们无论是多么设计精良，速度是快还是慢，压缩率是高还是低，它们都逃不出上面的 ∑ log2(1/pn) 这个数学公式给出的答案。

4

如果你问我：什么东西是人类创造出的最美好的事物？

我说：数学，没有之一。

完～

关注公众号“diwen的学习”（ID：diwen-xuexi）或长按二维码，一个中二青年的学习总结、见闻思考、成长记录史，搬过砖打过工创过业，仍在奋斗折腾中。和大家一起成长，死磕到底。
公号内容丰富，包含又不限于：创业、互联网、IT/软件技术、理财、读书音乐、轶闻故事、反常识思维，“中二不中立”。

    关注 diwen的学习