写给互联网冬天里程序员看的数据压缩

原文地址:
http://blog.52sox.com/data-co...

网上戏说2018是互联网的冬天,先有阿里、腾讯、华为不扩招进行人员优化,后有美团、知乎裁员,好生热闹。不得不说,中国的经济进入1个新的阶段,用官方的话就是新生态,用百姓的话说就是,我们告别了粗旷的放养,迎来了精耕细作的时代。
当我们在为互联网冬天感到担惊受怕的时候,前方传来董小姐厂加薪的捷报。然而这次又是别人家的公司。

听你说了大半天的话,就是为了跟我说这些伤心的事情?如果内里是这样想的,那么你可以关闭你网页上的标签页了。

适合读者人群

下面要说的内容,适合以下人群:

• 小白程序员,无论编程语言
• 准备年后跳槽的程序员
• 数据开发工程师
• 数据算法工程师
• 在校相关专业(数分、应用数学)大学生
• 喜欢装X的某些人

作为已经入坑2家的数据人,只能从自身的经验和发展路线来讲述数据压缩。下面我们要准备开始上车了。

引言

在过去10多年里,我们见证通信方式的变革,而且这一过程仍在持续。这一变革既包括因特网规模持续不断的增长(从2M到100M带宽的飞跃),也包括移动通信的爆炸式发展(从2G到4G,以及即将商用的5G),还体现在视频通信重要性的不断增加。而在这个革命的所有这些领域中,数据压缩都是基础支撑技术之一。
在2013年,大数据概念的提出,Hadoop打响了第一炮。而在2016年,我们迎来大数据的元年。而2017年,迎来了人工智能AI元年。技术和工具的不断推陈出新,我们也在成长中老去。那么,你可能会提出这样的问题:

• 为什么需要数据压缩?
• 了解数据压缩有什么好处?
• 我工作都不涉及这部分,跟我讲这个,你不是在浪费我的时间?

为了回答这样问题,我们有必要先说下什么是数据压缩再回答这些问题也不迟。

什么是数据压缩

简而言之,数据压缩就是以紧凑方式表示信息的技术或科学。人们识别出数据中存在的结构特征,并加以利用,生成这些紧凑表示方式。
说完了数据压缩的概念,我们将注意力回到之前的问题上,分别进行解释。

为什么需要数据压缩

之所以需要数据压缩,是因为人们以数字形式生成和利用的信息越来越多。在大数据时代里,我们可以说,当前我们被大量的各种信息所包围。比如在百度中输入1个智能手环的搜索,然后你会在隔天发现各种智能手环的广告。当然,这些精准的广告营销并没有达到我们的期望,至少现在看来还不够智能。
而随着需要传输、存储的数据呈爆炸式增长,人们在致力于开发更好的传输与存储技术方面取得很大的进步,但是取得的成果还不够。相关技术也层次不穷,比如大数据处理中的Hadoop工具,关于Hadoop及其生态圈,可以参见。
根据帕金森第一法则的推论,对大容量存储与传输能力需求的增长,至少是存储与传输能力增长速度的2倍。而在有些情况下,存储与传输能力并没有显著的提高,比如通过无线电波传送的信息量会受到大气特性的限制。
而通过数据压缩,我们可以提高其传输能力,降低存储的空间。

了解数据压缩有什么好处

说了大白天的数据压缩的问题,你还没有告诉我们了解或学习数据压缩到底有什么用。
学习数据压缩并不一定能让你拿高薪,也不一定能让你找到新的岗位,但是可以让你具备一定的数据思维的基础。至少,在实践中会懂得应用,并选择合适的方案。
切记,数据压缩只是基础,所谓基础就是没有它,你的上层建筑是没法构建起来的。

对持有浪费时间观念的辩诉

这个时候,有人会说,你真是浪费我的时间。我的工作又不涉及这部分内容,跟我唠叨这东西干嘛?
如果你是这样的观点,那么你不妨问下你自己,你平时是不是不听歌、看电影?而这些都与JPEG、MP3、H.264标准息息相关。

数据压缩真的有那么重要

而学习数据压缩,只是1种扩展你技术的1种选择,比如选择合适的方案解决工程问题。当然,如果你已经厉害到可以设计出合理的数据压缩方案,你也可以选择自助创业。

在互联网冬天,有1家科技公司近期完成了数千万的A轮融资。如果你对图像处理领域有所了解的话,就会发现实际上就是AI+DSP的模式,并不算多大的事情。
当然这也是别人家公司的事情,该干嘛干嘛。
说了这么多,如果你觉得没有什么看点,那么可以直接关闭标签页了。如果没有,我们就继续把。

数据压缩的方式

在数据压缩的早期,1个典型的例子就是是摩尔斯电码的使用,它通过对电报发送的字符以点和划来编码。通过统计发现,某些字符的出现频率要高于其他字符,于是为出现频率较高的字符分配较短的序列,从而减少发送1条消息所需要的平均时间。其中,霍夫曼(Huffman)编码就是利用思想。
我们可以通过许多不同类型的结构来实现压缩,而不仅仅局限于利用统计其结构来进行压缩。
在不同类型的数据中,存在许多其他类型的结构可以为压缩技术所用。例如,在语音中,我们在说话时,喉部的物理构造决定了所能发出的声音。换句话说,产生语音的力学特征使语音具有了某种结构。因此,我们可以不直接传送语音本身,而是传送喉部构造的相关信息,而接收器利用这些信息来合成语音。这样,我们只需要很少的数据就能表示足够的喉部结构信息,从而实现压缩。而这就是压缩方法早期版本中的声码器。
除了对数据的结构的利用外,我们还可以对数据的一些特性入手。比如,在许多时候,比如传送或存储语音和图像时,这些数据最终是由人来体验的,而人的感知能力是有限的。对于这些数据中表示的一些内容无法被用户感知,那么就可以将没有必要保留这些信息。我们通过利用人类的知觉局限,通过丢弃一些不相干的信息来实现压缩。
在开始研究数据压缩技术之前,我们先对这一领域作一整体概述。

什么是压缩技术

对于数据压缩而言,我们需要先设计出对应的算法及方案。
压缩技术或压缩算法实际上指的是如下的2种算法组成的:

• 压缩算法,取得输入X,生成1种需要较少二进位的表示Xc
• 重构算法,对压缩后的表示Xc执行操作,生成重构结果y

这些操作的示意图如下图所示:

我们沿循惯例,将压缩算法和重构算法结合在一起,称为压缩算法。
而根据重构需求,我们可以将数据压缩划分为2大类:

• 无损压缩,重构结果y和X相同
• 有损压缩,实现的压缩比通常高于无损压缩,但重构结果y可能与X不同

无损压缩

在无损压缩技术中,不允许存在信息的损失,该技术通常用于一些不允许原数据与重构数据之间存在任何差别的应用中,其中以文本压缩作为代表。
对于文本压缩而言,如果压缩后的文本与原文不一致,可能会造成语义的谬以千里。

有损压缩

有损压缩技术会造成一些信息损失,采用该技术压缩后的数据通常不能再准确还原或重构。但是,如果可以接受重构结果中存在的这种失真,那么它所实现的压缩比通常要比无损压缩高的多。
而在设计出1种数据压缩方案之后,我们还需要能够测量它的性能。而数据压缩的应用领域多种多样,所以用于描述和测量压缩性能的术语也有所不同。

性能的测量

我们可以用多种方式来评估一种压缩算法,我们可以从如下一些方面进行测量:

• 算法的相对复杂度
• 算法在给定计算机上的运行速度
• 压缩量
• 重构结果与原数据之间的类似程度

常用的指标有:

• 压缩比
• 速率

建模与编码

而对重构结果的要求可能直接决定了应当采用有损还是无损压缩方案,但具体使用哪1种压缩方案,则可能需要许多不同因素来决定。其中最重要的一些因素就是待压缩数据的特性。比如,1种能够有效压缩文本的技术,不一定能同样有效地压缩图像。
而要针对特定数据开发数据压缩算法,我们可以分为2个阶段来进行:

• 建模
• 编码

在第1阶段,我们通常称之为建模,我们尝试了解数据中存在的冗余情况,并用1个模型来描述这种冗余。而第2阶段,我们通过编码的方式来描述这个模型,描述数据与模型之间的差别。而数据与模型之间的差别通常称为残差。
比如在前面的摩尔斯电码中,我们先通过统计的方式了解到某个字符的频率比其他的字符高,这就是1个建模的过程。而使用较短序列分配给较高频率的字符,就是1种编码方式。

结语

在数据压缩中,我们有许多不同方法来描述数据的特征,而不同的特征描述方式可以得到不同的压缩方案。

参考书籍:

《Introduction to Data Compression,Fourth Edition》P1-8