走进科学
百科事典棒、原来如此、算术编码
读书时发现的趣事，分享给大家
以前读村上春树的《世界尽头与冷酷仙境》时就对其中《冷酷仙境：百科事典棒、不死、回形针》一章的“百科事典棒”这一设定尤为好奇。
“所谓百科事典棒，是某处一位科学家想出的理论游戏，就是说把百科事典刻在一支牙签上。知道怎么刻？”
“不知道。”
“简单得很。把情报信息也就是百科事典的文字全部换成数字。每一个字用两位数表示，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三个字符对应。每一段的长度就是前面的概率值。
- 现在第一个字符为A，则选择线段的第一部分(0, 0.4)，把这个区间作为进行下一步操作的线段。
- 第二个字符为C，对应的比例范围是0.8~1，则对上一步选择的区间，即(0,0.4)，取其0.8~1的部分，即(0.32, 0.4)。
- 第三个字符为A，则取线段(0.32, 0.4)的0~0.4的部分，即(0.32, 0.352)。
- 第四个字符仍为A，则取线段(0.32, 0.352)的0~0.4的部分，即(0.32, 0.3328)。
- 最后在(0.32,0.3328)内取一个数，比如其中点0.3264，就可以代表字符串ACAA。
解码的过程与编码过程类似，依次判断这个数属于线段(子线段)的哪个比例范围即可。
示意图如下：
虽然步骤上比百科事典棒的方法复杂一些，但性质确是类似的。随着字符串的增加，圈定的区间越来越小。最后区间的长度就相当于在牙签上刻痕迹的刀刃厚度，精度越高，编码的数据越多。
当然，算术编码作为在实际计算机科学中使用的压缩算法，比起百科事典棒最显著的优点在于其考虑了各个字符串出现的概率，而不是对所有字符都用相同长度的编码。最终的平均编码长度接近概率分布的熵。对于上面的例子而言，如果把0.3264表示成二进制，只需要保留前面的log2(1/d)个比特即可代表ACAA，其中d为最终区间的长度。
根据网络上找到的信息，村上春树的小说首次发表于1985年，《啊哈！原来如此》发表于1981年，其作者马丁·加德纳是美国著名的数学科普作家，对加密算法也颇为了解。至于算术编码早在1960年代Peter Elias就开始研究，也许马丁·加德纳也是受此启发？我不敢确定。
“人并非通过扩延时间达到不死，而是通过分解时间获得永生。”那些在人类历史上闪亮的名字，或许可作为这句话别样的注解。