信息论II：最优二叉树与Huffman编码

本期内容一览：

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）

“ 这里不谈技术，只谈思想。”

一些废话。

本来这份ppt是打算在公司的FEConf大会上展示的，但是年初的新型冠状病毒疫情把这事儿给鸽了。话说16XX年春天，伦敦地区也爆发了一场惨绝人寰的鼠疫，然后牛顿大神在家隔离时宅出了包括二项式定理和微积分在内的一系列顶级学术成果，进而导致了人类第一次理论物理大爆发...

如今人类的理论物理已经将近100年毫无进展了，所有的应用还基于上世纪初的相对论&量子力学。于是我等社畜在微博和朋友圈“理论储备告急”运动的鼓励下也试图利用在家隔离的时间装模做样的搞搞科学，尤其是脱离了应用趣味的理论研究。

我研究的方向是香农的信息论（是从B站上进化论专区上过来的，据说进化论基于信息论?），想着能对信息、熵、生命有更好的理解，通过学习来降低自己的信息熵，关于信息与熵的关系，参考上一篇文章《信息与熵【上】生命以信息为食》。本文是系列第二篇，主题是关于信息论中的信息压缩算法，将年前准备在公司演讲用的ppt完整地翻译成一篇文章，内容更多的回到了计算机软件上。

01

—

JSON的噪音

主题：寻找序列化的极限。

什么是序列化？序列化是一种将多维度的数据无损地转换成一维的线性数据，是一种编码手段，之所以要转换成一维是为了更好地存储和传输，关于序列化的知识参考这篇文章。

信息论认为，“编码”是信息从一种形式或格式转换为另一种形式的过程，比如，字符编码就是将文本格式的信息转换成字节码格式，反之，base64编码是将字节码格式转换成文本格式。“解码”是编码的逆过程。 名词解释：编码

那JSON就是这样一种流行的序列化格式，JSON支持实数、字符串、布尔、null这4个基本类型和列表、字典这2个复合类型，非常好用的同时当然也是有缺点的，JSON的“信噪比”很低，但具体是多少很难说。

根据信息论的观点，数据 = 信息 + 噪音。这个理论放在文本型序列化格式中的公式就是：JSON = 类型位 + 信息位。其中信息位就是json含有的有效信息量，类型位则是剩下所有噪音，包括双引号，逗号，方括号，花括号等。

json中的噪音是可压缩的，举一些一眼就能看出来的可优化之处：如果把键值对中“键”的双引号去掉，把true和false用字母t和f来代替，也不会产生歧义。

还有更高端的玩法：把json里所有的括号换成逆波兰表达式。也是一种有效减少体积的方式。

除此之外，实数类型是用十进制字符的形式存储的，这不仅造成了许多噪音，还增加了进制转换的时间。

再仔细找还能发现json许多多余的数据，可以一直不断的被压缩，但这个压缩的极限在哪里？一定是有极限的，json不可能被无限压缩。

02

—

数据压缩有极限吗？

西班牙有个叫González的老哥设计了一个json的压缩算法，也是基于文本的，据说能将嵌套很深的json压缩至55%，比如有下面这样的一个json：

{    "type": "world",    "name": "earth",    "children": [        {            "type": "continent",            "name": "America",            "children": [                {                    "type": "country",                    "name": "Chile",                    "children": [                        {                            "type": "commune",                            "name": "Antofagasta"                        }                    ]                }            ]        },        {            "type": "continent",            "name": "Europe"        }    ]}

通过老哥的“压缩算法”得到的这样一串：

type|world|name|earth|children|continent|America|country|Chile|commune|Antofagasta|Europe^^^$0|1|2|3|4|@$0|5|2|6|4|@$0|7|2|8|4|@$0|9|2|A]]]]]|$0|5|2|B]]]

而且压缩率惊人，甚至超过了之后要说的MessagePack，但是仔细研究便发现，它其实是利用了人们对json的使用习惯来压缩的，比如人们经常使用TypedArray（有类型列表），像json-schema一样限定列表内对象的属性，González老哥正是将经常出现的相同键名比如name、id、children这些，把他们收集起来使用，才降低了耦合度，压缩了体积。

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray TypedArray介绍

但这种利用习惯的压缩算法毕竟是不持久的，因为习惯会变化，所以并不推荐使用。在特定场合下，或者习惯固定的一个团队内，这种算法尚有用武之地。

但不能说今天用这个格式，明天又想到一个更好的压缩算法，再换新格式，这个“更好”到底是好多少，如何定量，以及上限是多少，这些才是信息论关心的。为了寻找这个极限，就得研究信息的“根本”格式：二进制格式；而不是基于二进制格式的文本格式。在文本格式上改良优化永远无法达到信息压缩的极限。所以序列化格式进化历程中的核心矛盾是：文本格式vs数字格式。

言而总之，文本格式是时代发展中一种”偷懒”的过渡格式。正因为文本格式简单易扩展的特点，早期的许多序列化格式，http，甚至ip协议族都有很多还保留着文本格式。尤其是占据9成以上互联网流量的http/1.X协议，由于http/1.1的头部和body（json）全都是文本格式，http也遇到了性能瓶颈：从时间上看，http文本编译与解析浪费时间；从空间上看，http头部大量的字段浪费空间。

03

—

信息论与压缩技术

但是从http/2.0开始（以下简称h2），这种不良风气开始改变了，对于head和body，h2采用了不同的压缩算法来提高效率。对于静态的header，h2采用定长编码来压缩，也就是为每个常用的头部如content-type:text/html分配一个固定的编号表示。对于动态的head，即可自定义的head和value值，h2则采用的是对ASCII的变长编码：Huffman编码。

至此，http的head部分已经全部数字化了，body部分由于是用户自定义的，仍然保留着json这个文本格式，但是w3c呼吁大家使用json的替代品，但没有直说是哪种替代品，让我们自由的去选择二进制序列化格式。

注：文本格式变成二进制格式的过程叫做“数字化”，因为二进制格式更像是一种“数字格式”。

04

—

最优二叉树

既然w3c推荐我们使用Huffman编码的二进制序列化格式，很有必要去认识一下Huffman的数据结构：最优二叉树。

设计一套编码最直接的方式是定长编码，就是每种类型/字符的长度一定，比如ASCII编码定长的8bit。如图，用定长编码设计5种字符至少需要3bit的编码长度，图中的深度为3的满二叉树的每一片叶子都是一个字符，但剩下3个叶子因没用到而浪费了。

这时候可以将使用频率最高的一个字符的长度从3压缩至1。这样做的意义是牺牲那些无意义的编码的数量来节省有意义编码的长度。给使用频率最高的那个字符赋予1bit的编码长度后就生成了一个最优二叉树。

05

—

Huffman编码

这个“最优二叉树编码”其实就是“Huffman编码”的同义词。Huffman编码是变长编码，即每个编码对象的长度不一样，但是任意排列组合起来不会产生歧义。但是从定长编码转向变长编码的代价是：体积增加（叶子的总深度损失）。所以，所有对象使用频率一定（或者频率无法预知）的情况下，使用定长编码的效率更高，这有一点“周长一定，正方形面积最大”的意思。

当然，Huffman树本身的生成算法是根据不同对象的使用频率，从树叶收敛到树根，使得二叉树最优，算法细节略。