信息论IV：宿主、时空置换、V8玄学

本系列内容一览：

1. JSON的“噪音”与“信噪比”
2. 噪音量的理论上限
3. 信息论与压缩技术：字符串vs字节串
4. 最优二叉树
5. Huffman编码
6. Message Pack
7. Message Pack 的 Huffman 树
8. 前缀 VS 分隔符
9. 性能测试
10. 序列化的极限、两个基本公理
11. UTF-8极限压缩
12. 变长类型偏移术
13. 字典压缩大法
14. 尾部残缺问题
15. Ultra Pack与时空置换原理
16. V8引擎玄学

本文是《信息论》系列（奇怪知识系列）的最后一篇，本系列全4篇分别是：

1. 《信息与熵：生命以信息为食》（信息论基础）
2. 《最优二叉树与Huffman编码》（1~5章）
3. 《寻找序列化的极限》（6~11章）
4. 《宿主、时空置换、V8玄学》（12~16章）（本文）

12

—

变长偏移实数

字符串类型通过修剪utf8的Huffman树，让所有的叶子成为独立的编码对象，虽然牺牲了一定的时间，却让minUTF8成为信息论上最优的字符编码。接下来研究研究实数类型的压缩方案，没错，压缩数字！

有人问，实数类型还能怎么压缩？IEEE定义的补码和浮点小数已经最大程度地满足了实数的存储需求，几乎完美，我难道还能设计出一套更好的格式？

我的压缩思路是从人们的使用习惯而来的，虽然前文我也提到了根据使用习惯来压缩信息是不可靠的（前面我提到了使用TypedArray的习惯），但不可否认的是，有这样一种“使用习惯”是更古不变的，那就是：较小实数的出现频率总是高于较大的实数。人总是喜欢用靠近0的正数来做度量，比如用摄氏度代替开氏度，上亿上兆的数很少出现，相信不用我证明了，所以如果每一个数都用64位浮点来存储无疑是一种浪费，所以msp提供了变长的实数类型：不同范围的实数占据不同数量的byte。

但变长实数违反了原则二。

就以变长正整数举例，图中不同长度的正整数都是以二进制原码的形式存储的，在8bit和16bit这两个范围中，【00000000】和【00000000 00000000】都表示实数0，含义相同而字节串不一样，违反原则二。

如何解决？

最好的方法是让变长实数升级成变长偏移实数。每一种长度的最低位承接上一个长度的最高位。比如图所示，每个实数还要加上本类别的偏移值才是实际值：

• 8bit整数：MIN=0，MAX=2^8-1=255
• 16bit整数：MIN=MAX[上]+1=256，MAX=MIN+2^16-1=65792
• 32bit整数：MIN=MAX[上]+1=65793，MAX=MIN+2^32-1

13

—

字典压缩大法

好了，字符串和实数的新格式都成功地达到了序列化的理论极限，但他们都是基本数据类型，接下来挑战一下复合类型：字典的压缩算法。

字典是否可压缩，首先还是得看它是否违反之前的2个原则。在msp里面，字典类型将每个键值对按照[键, 值, 键, 值...]的方式存储，每个键或值都可以是基本类型或复合类型。

为了跨平台，绝大多数场合下，“键”的类型都是string，那么可以将类型字段省略掉节省空间。

一个元素主要由三部分组成：类型、长度、内容。其中类型+长度组成了一个编码对象，长度即内容的长度。

同样在大多数场合下，键值对是无序的，顺序没有太大的意义，就像散列表一样。但是如果按照json或msp这样排列键值对，它总是有序的，即使你不使用这个顺序，这个顺序的信息总是存在，信息=物质，有信息就会占据空间，那如何去除字典的顺序呢？

办法是给键值对强行排序。

按照键的字节码来排序，即将字符串看成一个大整数，然后从小到大排序。编码时，每个键的位置不再存放键本身，而存放比上一个键的“增量”，解码时通过累加增量得到每个键。

这样一来，排序后的字典仍然是“有序的”，但这时的“顺序”已然没有任何意义了，因为按键增序排列已经是100%确定的，无任何其他可能，而信息是为了消除不确定性（熵），所以“顺序”本身提供的信息量为0，自然不占据任何空间。

14

—

尾部残缺问题

根据以上的分析，字符串、实数、字典都找到了属于自己的极限压缩算法。等等，那列表怎么办？

其实学过前端的都知道，列表是一种特殊的字典，只是列表的“键”是0, 1, 2, 3...的自然数而已，对于自然数无需任何优化，列表类型本身已经是序列化的极限。

到此为止，序列化的极限并没有真正意义上实现，因为随机输入的二进制字节串还要考虑硬件，内存最小单元是一个字节，就算随机字节串的长度补齐到8的倍数还要考虑一个更终极的问题：尾部残缺问题。

如果扫描到EOF，也就是整条数据末尾，发现最后一个元素的长度尚未达到前缀中声明的长度，该怎么办？此时如果报错则违反原则一（永不报错），也不能用0补齐，这样违反原则二（拒绝冗余）。

我暂时能想到的办法是：将最后一个元素的前缀中“长度”部分给去除，相当于利用EOF休止符来暗示元素的长度。但似乎这种方法是有许多坑的，鉴于本人理论储备及精力都有限，尾部压缩的具体实现的细节交给你们了。

自从大一高等数学考完以后，本人的基础知识就没怎么进步过，后来在计算机理论上的进步完全基于以前学习过的数理化，隐约感觉这种每天都能学到新知识的日子快要到头了，就像人类的物理学一样。。

15

—

Ultra Pack

讨论了这么多压缩大法，目的当然是开发一套更棒的二进制序列化格式啦，于是我们有了UltraPack，一个改良自MessagePack，拥有精心设计的Huffman树，能够极限压缩的完美格式，它综合了实数、字符串、字节串、列表、字典等常见格式的改良数据结构，是一款理论上最优的编码！

虽然我连文件后缀名和mime类型都想好，但UltraPack只是一款活在理论中的格式，因为具体的实现和推广上还有无数的困难，所谓的“极限”是否是信息论意义上的极限还很难说。虽然这个项目目前钱不够、团队未定、代码暂无，但这些并不妨碍我们去证明它，活过，足矣。

为此，我还假想了UltraPack的编辑器，让用户可视化地读/写UltraPack格式配置文件，增添可读性的同时更提升了安全性，避免了文本格式编辑过程中可能发生的语法错误。

理论上，UltraPack比JSON：更小、更丰富、更安全。但一切只停留在理论上，在空间上到达极限的UltraPack必然在时间问题上一败涂地。

爱因斯坦的相对论用一个小小的光速统一了时间与空间，让人们意识到，时间和空间原来是可以互换的，于是在硅基科学（计算机科学）领域里就有了cpu与内存的博弈、算法与数据结构的制约、时间复杂度与空间复杂度的耦合。

从一开始，UltraPack就没考虑时间问题，而是尽可能的牺牲时间来换取空间利益。尤其是为了实现完美Huffman树，不惜跨越整字节的物理限制，这些直接导致cpu在编解码时额外的时间开销。但还是那句话，时间与空间本身就是两个不可兼得的矛盾体，如果能够牺牲时间这一方，让空间开销抵达理论极限，也是值得的。

16

—

V8引擎玄学

接近尾声，之前还遗留了一个小问题：为什么msp的性能测试选择在python平台而不是更流行的JS/node平台？因为在JS/node平台，无论是编码还是解码，msp的速度都远远小于json。是什么造成了这个悲惨的事实？

罪魁祸首是V8引擎。

总的来说，msp的理论上绝对比json快，但JS平台实验结果与理论预期大相径庭的根本原因在于，并不是json的速度太快了，而是msp的速度被V8引擎严重削弱。

下面定义同一个JS对象，请问下面两种方式，哪一种更快？

// spawn an object, which way is faster?// 第一种const data = { foo: 42, bar: 133 };   // ? // 第二种const data = JSON.parse(`{"foo":42,"bar":133}`);  // ?

直觉感觉第一种方式更快，因为第一种方式直接定义了一个对象，而第二种通过JSON串来解码似乎多了一层“编译”的操作，应该更慢才对。但事与愿违，经过测试，第二种方式远远快于第一种。

根本原因在于，第一种方式在引擎之上，第二种方式在引擎之下（under the hood）。JS是一种运行于引擎之上的高级语言，V8引擎的存在是一把双刃剑，方便了人的同时却害苦了机器。在JS的规格里，哪怕再简单的一个函数都有可能需要经历十几个步骤才完成，比如Array.prototype.push()是往数组里推入一个新元素，就这样一个基本操作，JS需要经历如下的若干步骤：

为了添加一个新元素，V8先检查检查长度，再检查检查类型，最后确保万无一失了才允许你push进去，当海量的push一起进行，浪费的时间不敢想象。仅仅为了让开发者使用愉快，就这么折腾机器，我第一次为自己还在使用弱类型语言感到羞愧?！

这就是msp在JS平台如此之慢的原因：msp解释器是运行在V8引擎之上的，虽然解析很快，但构建JS对象的效率遭到大面积封杀，而JSON是V8引擎之下的API，原生的支持让JSON的解析速度可以直接触及硬件的极限。

而在其他平台，如Python，C++之类，同样的数组push操作，由于元素拥有类型（TypedArray）和预先分配的内存，push的速度不受引擎影响，只受物理限制，在那里msp才能展现出它应有的优势。

《信息论》系列全16章完结，涉及关键词：信息熵、生命、二叉树、序列化、空间极限、V8引擎。

<完>