和其他的二进制序列化格式比如MessagePack、ProtocolBuffer相比,Zipack算是比较复杂的编码格式,因为我设计Zipack的时候引入了一些全新的概念,用以取代传统的UTF8字符编码和IEEE浮点数,总的来说Zipack是一套很完美的编码格式。
编码(序列化)是与平台相关的多元对象变成Zipack类型的过程,与之相对,解码是编码的逆过程。比如,JavaScript的Array(列表)应该与Zipack的List类型对应。
大端字节序的Base128编码是一套以7bit为单位编码变长物理量的技巧,它用每个字节的最高位来暗示当前数据的连续性。0xxxxxxx代表最后一个字节,1xxxxxxx表示还有后续字节,解码器从左向右扫描的时候遇到0xxxxxxx才停止。所以不同长度的Base128字段如下:
- 0xxxxxxx
- 1xxxxxxx 0xxxxxxx
- 1xxxxxxx 1xxxxxxx 0xxxxxxx
- ......
Zipack对Base128的实现方式是一种经过偏移的Base128非负整数,从而实现Base128和非负整数(自然数)的一一映射关系:
| 自然数(十进制) | Base128(二进制) |
|---|---|
| 0 | 0000000 |
| 1 | 0000001 |
| ...... | ...... |
| 127 | 1111111 |
| 128 | 0000000 0000000 |
| 129 | 0000000 0000001 |
| ...... | ...... |
| 16511 | 1111111 1111111 |
| 16512 | 0000000 0000000 0000000 |
| 16513 | 0000000 0000000 0000001 |
| ...... | ...... |
这样做的好处很明显:将信息空间的利用率提升至100%。确保你理解了这个概念,因为这是Zipack的核心原理,以下将Base128偏移自然数简称Base128或B7。
为了更好地压缩字符串,我放弃了UTF8编码,取而代之的是基于Base128的字符串。因为每一个Unicode字符都是独一无二的自然数,所以很容易想到将Unicode编号与Base128自然数一一映射,实现100%的信息利用率。可想而知Zipack的字符编码与UTF8在0~127字符段(单字节字符)上是一致的。Zipack中有2个地方出现字符串:字符串类型和字典类型的“键”。
为了更好地压缩小数,我放弃了IEEE浮点数编码,取而代之的是“精度反转算法”。首先在Zipack中,整数和小数是分开来编码的:和IEEE浮点数不同,小数不包含整数。因为正小数和负小数是对称的,我们只讨论正小数的情况。
每个二进制形式的正小数可以被小数点分成左右2部分:左边整数部分和右边小数部分。左部最左侧的“0”和右部最右侧的“0”都无意义,比如010=10、0.10=0.1,所以可将这些“0”剔除。左部很显然与自然数一一映射,右部将bit数组逆转后与正整数一一映射,由于整数类型是独立的,