数据压缩——有益无害(3)

你也许明白为什么传真机能利用行程长度编码。从定义上来说,传真是黑白文件,文件会被转换成许多个点,每个点都是非黑即白。当你按顺序阅读这些点(从左到右,从上到下),你会遇到大段白点(背景)以及小段黑点(前景文本或笔迹)。这让使用行程长度编码变得非常有效。但正如之前所提到的,只有特定类型的数据具有这一特点。

于是,计算机科学家们发明了一系列更成熟的把戏,这些把戏使用的基本思想都相同(寻找重复并高效地描述它们),但即便重复部分不相邻也效果良好。在这里,我们只会研究其中的两种把戏:同前把戏(same-as-earlier trick)和更短符号把戏(shorter-symbol trick)。你只需要这两个把戏就能生成ZIP文件,而ZIP文件格式是个人电脑上压缩文件最流行的格式。因此,一旦你理解了这两个把戏背后的基本思想,你也就理解了计算机在大部分时间里是如何运用压缩的。

同前把戏

想象这就是你要处理的可怕任务,通过电话向某人口述如下数据:

VJGDNQMYLH-KW-VJGDNQMYLH-ADXSGF-OVJGDNQMYLH-ADXSGF-VJGDNQMYLH-EW-ADXSGF

这里有63个字母需要沟通(顺便说一句,我们忽略了破折号,加入它们只是为了让数据更容易阅读)。和每次一个字母地口述全部63个字母相比,我们有更好的办法吗?第一步也许是去识别数据中大量的重复部分。事实上,大多数被破折号分开的“块”都至少重复了一次。因此,在口述这份数据时,你可以通过“这部分和我之前告诉你的某个部分一样”节省大量力气。更精确点讲,你要讲是多久前说的,还要讲重复的部分有多长——也许是“往回数27个字母,然后复制从那一点开始往下的8个字母”。

让我们来看看这一策略在现实中效果如何。最开始的12个字母没有重复部分,你没有其他选择,只能按字母逐个口述:“V、J、G、D、N、Q、M、Y、L、H、K、W”。但接下来的10个字母和之前的一些字母相同,因此你可以说“back 12,copy 10”(数回12个字母,抄到第10个字母)。再下面7个字母是新出现的,按字母逐个口述:“A、D、X、S、G、F、O”。但之后的16个字母是个大的重复部分,因此你可以说“back 17,copy 16”(数回17个字母,抄到第16个字母)。接下来的10个字母也是之前的重复部分,因此“back 16, copy 10” (数回16个字母,抄到第10个字母)就可以了。再接下来的两个字母没有重复,需要逐个口述为“E、W”。最后的6个字母是之前的重复,可以通过“back 18,copy 6”(数回18个字母,抄到第6个字母)沟通。

读书导航