@ 2022.02.18 , 03:31

百科事典棒、原来如此、算术编码

读书时发现的趣事,分享给大家

以前读村上春树的《世界尽头与冷酷仙境》时就对其中《冷酷仙境:百科事典棒、不死、回形针》一章的“百科事典棒”这一设定尤为好奇。

 “所谓百科事典棒,是某处一位科学家想出的理论游戏,就是说把百科事典刻在一支牙签上。知道怎么刻?”

“不知道。”

“简单得很。把情报信息也就是百科事典的文字全部换成数字。每一个字用两位数表示,A 为01,B为02,00为空白,标点符号也同样数字化。并在其最前面置以小数点。这样,就会出现无限长的小数点,如0.1732000631等等。然后,把它刻在牙签与数字正相符的位置。具体地说,把与0.50000……相符的部分刻在牙签正中;若是0.3333……则刻在距前端三分之一处。意思可明白?”

……

“你研究的真正目的就在这里?”

“不,不是这样。”博士说,“最初我也没注意到,起始只是出于些许兴趣开始这项研究的。研究过程中才碰到这点发现了这点。人并非通过扩延时间达到不死,而是通过分解时间获得永生。”

如果考虑实际的操作,这种存储信息的方法但对于比较短的信息(比如一个单词)确实可行,但信息一长就设计到精度的问题。无论是刻蚀(刀足够薄)还是读取(精确的位置),物理世界终有最小的单元,比如原子、比如普朗克长度。但如果一本正经的讨论可行性未免有限呆板,因为从理论上来说这确实是一种编码信息的方式。

书里说这是某位科学家想出的理论游戏,我最近发现其可能出自科普书籍《啊哈!原来如此》。

这本薄薄的书每一两页就图文并茂的讲述一个趣味小故事,在《数》的部分就有一篇《惊人的编码》。故事中来自外星球的科学家前来收集地球的相关知识,就是以“百科事典棒”的方式将整个大英百科全书刻在一根金属棒之上。

百科事典棒、原来如此、算术编码

在随后一页作者拓展讲到了“哥德尔不完备性定理”、编码的可行性、无理数圆周率是否可能包含所有数字序列。

如上所述,用这种方法编码海量的信息确是在物理上不可能,但算法并非不可行。昨天在学习Cover的《信息论基础》时看到了一种基础的压缩算法:“算术编码”(Arithmetic Coding),与以上的思想有异曲同工之妙。具体的编码过程如下:

假设一串字符由(A, B, C)组成,如:ACAA...,长度不限。不同字母出现的概率不同,假设分别为:(0.4, 0.4, 0.2),当然概率相加之和为1。现在把0到1的线段分成三段比例范围:0~0.4、0.4~0.8、0.8~1,与ABC三个字符对应。每一段的长度就是前面的概率值。

  1. 现在第一个字符为A,则选择线段的第一部分(0, 0.4),把这个区间作为进行下一步操作的线段。
  2. 第二个字符为C,对应的比例范围是0.8~1,则对上一步选择的区间,即(0,0.4),取其0.8~1的部分,即(0.32, 0.4)。
  3. 第三个字符为A,则取线段(0.32, 0.4)的0~0.4的部分,即(0.32, 0.352)。
  4. 第四个字符仍为A,则取线段(0.32, 0.352)的0~0.4的部分,即(0.32, 0.3328)。
  5. 最后在(0.32,0.3328)内取一个数,比如其中点0.3264,就可以代表字符串ACAA。

解码的过程与编码过程类似,依次判断这个数属于线段(子线段)的哪个比例范围即可。

示意图如下:

百科事典棒、原来如此、算术编码

虽然步骤上比百科事典棒的方法复杂一些,但性质确是类似的。随着字符串的增加,圈定的区间越来越小。最后区间的长度就相当于在牙签上刻痕迹的刀刃厚度,精度越高,编码的数据越多。

当然,算术编码作为在实际计算机科学中使用的压缩算法,比起百科事典棒最显著的优点在于其考虑了各个字符串出现的概率,而不是对所有字符都用相同长度的编码。最终的平均编码长度接近概率分布的熵。对于上面的例子而言,如果把0.3264表示成二进制,只需要保留前面的log2(1/d)个比特即可代表ACAA,其中d为最终区间的长度。

根据网络上找到的信息,村上春树的小说首次发表于1985年,《啊哈!原来如此》发表于1981年,其作者马丁·加德纳是美国著名的数学科普作家,对加密算法也颇为了解。至于算术编码早在1960年代Peter Elias就开始研究,也许马丁·加德纳也是受此启发?我不敢确定。

“人并非通过扩延时间达到不死,而是通过分解时间获得永生。”那些在人类历史上闪亮的名字,或许可作为这句话别样的注解。


支付宝打赏 [x]
您的大名: 打赏金额:

赞一个 (16)