正文

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

改变未来的九大算法 作者:(美)约翰·麦考密克


让我们尝试总结一下这个压缩算法。我们用缩写b代替“back”,c代替“copy”。因此一个如“back 18,copy 6”(数回18个字母,抄到第6个字母)的返回抄写指令简写为b18c6。因此上面的口述指令可以被总结成:

VJGDNQMYLH-KW-b12c10-ADXSGF-O-b17c16-b16c10-EW-b18c6

这个字符串只包含44个字母。原始字符串有63个字母,我们节省了19个字母,接近原始字符串长度的1/3。

同前把戏中还有一个有趣的窍门。你会如何使用相同的把戏压缩FG-FG-FG-FG-FG-FG-FG-FG这条消息?(和之前一样,破折号不是消息的一部分,只是为增强可读性而添加。)消息中的FG有8处重复,因此我们可以单个口述前4个,然后使用如下的返回抄写指令:FG-FG-FG-FG-b8c8。这会节省不少字母,但我们可以做得更好。这需要一个第一眼看起来可能显得荒谬的返回抄写指令:“back 2, copy 14” (数回2个字母,抄到第14个字母),或简写为b2c14。压缩的消息就成了FG-b2c14。在只有2个字母可供抄写的情况下,怎么理解抄到第14个字母呢?事实上,只要你从重新生成的消息中而非压缩的消息中抄写,就不会有任何问题。让我们一步步地来做。在口述了最开始的2个字母后,我们有了FG。然后我们收到b2c14指令,于是我们数回2个字母并开始抄写。因为只有2个字母(FG),让我们抄写这2个字母:当把抄写的字母加到我们已有的字母后,结果是FG-FG。但现在多了2个字母!照样抄写这些字母,在将它们添加到已有的重新生成的消息上之后,你得到了FG-FG-FG。和前一次一样,又多出2个字母,于是你又能多抄写2个字母。依此类推,直到你抄写了所要求的字母数(在这个例子中就是14个)。要检验自己是否理解了这一点,看看你能否得到这条压缩消息的解压版:Ab1c250 。

更短符号把戏

要理解名为“更短符号把戏”的压缩把戏,我们要更深入探究计算机存储消息的方式。你之前可能听说过,计算机并不真的存储a、b、c这样的字母。所有东西都以数字存储,然后根据一些固定表格翻译为字母。(这种在字母和数字之间转换的技术在校验和的讨论中有提到。)比如,我们可以同意“a”由27代表,“b”由28代表,“c”由29代表。那么字符串“abc”就可以以“272829”的形式存储在计算机中,而在屏幕上显示或打印在纸上之前,这些数字又能轻易翻译回“abc”。


上一章目录下一章

Copyright © 读书网 www.dushu.com 2005-2020, All Rights Reserved.
鄂ICP备15019699号 鄂公网安备 42010302001612号