信息论III：寻找序列化的极限

本系列全部章节一览：

1. JSON的“噪音”与“信噪比”
2. 噪音量的理论上限、逆波兰表达式
3. 信息论与压缩技术：字符串vs字节串
4. 最优二叉树、FPS/2.0
5. Huffman编码
6. Message Pack
7. Message Pack 的 Huffman 树
8. 前缀 VS 分隔符
9. Message Pack 缺陷、宿主环境Bug
10. 序列化的极限、两个基本公理
11. UTF-8极限压缩
12. 有理数：变长类型偏移术
13. 字典压缩大法
14. 尾部残缺问题
15. Ultra Pack与时空置换原理
16. V8引擎玄学（What's happening under the hood）

来自【奇怪的知识】系列的第三篇，承接上文《最优二叉树与Huffman编码》的第1~第5章，本文从第6章开始。

啦啦啦。

06

—

Message Pack

Message Pack，以下简称msp或msgPack，就是这样一个流行于民间，基于Huffman编码，兼容json的二进制序列化格式。

msp兼容json是因为msp支持json的所有数据类型（4个基本类型及2个复合类型），除此之外msp还有自己的类型，包括纯粹二进制格式（也叫字节串）、datetime格式、自定义保留类型、变长基本类型。

msp之所以基于Huffman指的是，msp中每一种数据类型就是一个编码对象。

变长基本类型包括变长实数、变长字符串、变长字节串。变长类型意味着你可以用尽可能短的空间存放更“小”的数据，比如127以内的正整数只占1字节。

msp还支持“无缝流化”。想象一下json想要流化异常麻烦，有多种“流接”的解决方案，最常用的ndjson也要消耗换行字符来分割每个json。但是msp因为通过前缀来限定长度，无需分隔符/终止符，前后2个msp对象可以无缝衔接。

举个例子。

图中这个demo里面，29字节的json对象经过msp压缩之后变成20字节。图中高亮的字节/字符代表有效信息量，剩下灰色部分代表噪音，信息量 / 噪音 = 信噪比。显然msp的信噪比更高，体积更小。当然了，这样计算信噪比是不严谨的，实际情况还要考虑类型使用概率等因素，但举个例子足够了。

关于msp和json的全面对比，可以参考《MessagePack：最可能取代JSON的存在》这篇文章，文章的结论是：msp理论上比json更小更快更丰富。

07

—

Message Pack 的 Huffman 树

夸完了msp，来扒一扒msp的specification。

把msp支持的所有数据类型按照前缀的编码放到一棵树上就得到上图的Huffman树，由于树太大，我将“110前缀节点”为分界点，将msp的Huffman树分为“110之前”和“110之后”两部分：110之前都是长度为1~4bit的常用类型，110之后都是长度为8bit的相对“冷门”一点的类型。

08

—

前缀 VS 分隔符

图中的测试数据是在python平台下进行的，为什么选择python平台而不是JS平台的原因文章结尾会说明ε=ε=ε=┏(゜ロ゜;)┛。

可以看到，python3下具有相同信息量的json和msp，msp的体积减少16.2%，解码速度大幅提升，只有编码消耗的时间更长，总的来说msp性能优于json。

可是为什么msp编码耗时更长呢？我个人的猜测是，json属于利用分隔符划分元素的格式，msp属于通过前缀划分元素的格式。前缀的好处在于可以加速解码速度，因为前缀暗示了下一个元素的长度，让解码器可以“跳着”解码，不像json那样需要逐字符扫描，遇到分隔符或者休止符才停止。

但编码和解码是一对逆过程，解码的速度提升了，编码的速度自然就要下降，这是不可违背的自然规律。对于分隔符型序列化格式，编码的过程就是一条龙式的平铺过程，没有任何停顿，但前缀型序列化时需要在每个元素写入完成后计算元素的长度，然后将长度插入到元素开头，自然要更多的时间。

这也就是msp在编码的速度上慢于json的原因。

09

—

MsgPack的缺陷

虽然不知道msp的“信噪比”，但肉眼是能看得出msp也是有一些缺陷的。比如msp的Huffman树有待优化，还记得之前“110之后”的那棵树嘛，那棵树上32种数据类型的前缀长度完全对称，常识告诉我们，越整齐的东西性能越低，Huffman树越“整齐”越说明了变长编码没有得到好的设计，毕竟不可能每种类型的使用频率都一样。

msp的保留类型太多，它居然有9种保留类型，包括扩展类型和“never used”类型。保留类型太多也没什么意义，毕竟保留类型使用的频率也很低。

msp的生态不够完善，虽然有几十种语言开源编解码器，但没有标准库支持msp很难得到官方认可。

言而总之，msp可进一步压缩，压缩的极限在哪里？谁也不知道。

10

—

序列化的极限

从一开始的文本格式到后来的序列化格式，我们一直在寻找序列化的极限，这个极限究竟在何方，不能盲目的寻找，似乎要给这个极限下一个定义。于是我指定了2个原则，作为序列化极限的基本公理，请大家评鉴一下，看看合不合理：

1. 原则一：任意的字节串都有意义
2. 原则二：不同的字节串都有不同的意义

这两句话啥意思？对于原则一，假如给你一副只有0和1的键盘，让你随便敲，将你一顿输出后的字节串送给一个解码器去解码，如果解码总是成功则说明这个编码格式遵守原则一，如果可能报错则违背原则一。

很显然无论是json，msp，甚至是utf-8都违背原则一，而ASCII遵守原则一，因为一个字节表示的256种字符都存在。实际上绝大多数变长编码格式都违背原则一。

对于原则二，它表示n种字节串有n种含义，如果2个不同的字节串表达了相同的含义，从信息论的角度，这是一种浪费。

这两个原则都是保证了数据体积压缩到极限，并没有考虑编解码的速度，由于本文的主题只关心空间，不考虑时间，所以时间复杂度问题不在本系列研究。

言而总之，只要一个序列化格式（编码格式）满足了原则一和原则二，我们就称它达到了序列化的（空间）极限。

UTF-8极限压缩

为了达到序列化的压缩极限，我们给每种数据类型挨个分析，先从最简单的字符串开始。

uft8是耳熟能详的字符编码了，而且是变长编码，utf8的Huffman表如上图，目前utf8字符的长度从1~4字节不等，每种字符又有不同的前缀，但存在2种特殊的前缀，分别是：

1. 后续字节前缀（10）
2. 保留类型前缀（11111）

后续字节前缀10是除首字节以外的字节前缀，单字节的字符没有。虽然10前缀的存在具有字符校验、逆向索引的好处，但从信息论的视角，这是多余的噪音罢了，完全没有存在的必要，具体原因参照这篇文章：《这难道是UTF-8字符编码的设计缺陷？》

保留类型前缀11111是为了预留给未来可能出现的新字符做准备，它们主要是长度超过4字节的字符们。

无论是10还是11111都违反了原则一，因为在不恰当的位置出现这些前缀直接导致utf8解析失败。

这两个前缀之所以特殊是因为它们在utf8的Huffman树上存在但不能表示具体的编码对象，如下图：

图中标红的2个前缀就是违反原则一的2个前缀，如果把这两片叶子从树上摘掉会怎么样呢？摘掉以后就成为了minUTF8，也就是图中第二幅更简单的Huffman树，minUTF8是UTF8的压缩版本，去掉了无用的前缀，大大减少了存储成本。

minUTF-8这个名字是我随便取的，仅仅代表一种可能的编码方案，并不一定能在实际中产生应用。