变长浮点编码原理

2021-01-04 11:36:20 浏览数 (1)

上一期介绍了Base128编码，这次谈谈Base128的实现——Zipack。以下内容是我Zipack格式的中文规范，其中最精彩的部分在“变长浮点数”的部分。

zipack开发指南

前言

zipack格式比较复杂，需要集大家的贡献才能建设出一个良好的生态，目前已经开发出的JavaScript版本zipack编码解码器可作为参考，请根据本文的伪代码开发其他语言的版本。关于zipack设计的思路和优缺点不在本文中重述，请参考之前的文档，本文只提供为开发者服务的specification。

常用变量

代码语言：javascript复制
r7 = 2 ^ 7
r14 = 2 ^ 14
r21 = 2 ^ 21
r28 = 2 ^ 28
r35 = 2 ^ 35
r42 = 2 ^ 42
  
R7 = r7
R14 = r14   r7
R21 = r21   r14   r7
R28 = r28   r21   r14   r7
R35 = r35   r28   r21   r14   r7
R42 = r42   r35   r28   r21   r14   r7

r = [1, r7, r14, r21, r28, r35, r42]
R = [0, R7, R14, R21, R28, R35, R42]

准备工作：VLQ自然数

zipack采用原创的VLQ偏移算法编码自然数，一个VLQ面值要加上一个偏移值才得到实际值，比如0111,1111代表127，而1000,0000 0000,0000代表128。

从字节流中index处读取一个自然数

从第index字节开始解析一个vlq字节串（到最高位是0的字节为止），将其转成自然数

  • 函数名：vlq2nature
  • 输入：字节流bytes，下标index
  • 输出：自然数，新的下标index

步骤：

  1. 记录初始下标start=index
  2. 从start字节开始循环，index自增，直到找到最高位比特是0的字节为止，即 byte < 1000,0000
  3. 让index指向下一个字节：index
  4. 在bytes身上从start截取到index为止，左包含，右不包含，即 vlq = bytes.slice(start, index)
  5. 将vlq的每个最高位去掉，生成一个7bit组
  6. 将7bit组组合成一个自然数 nature
  7. 将这个自然数加上偏移值，nature = R[vlq.length - 1]
  8. 输出nature和index

将一个自然数转换成字节流

是上面的vlq2nature的逆过程

  • 函数名：nature2vlq
  • 输入：自然数nature
  • 输出：字节流bytes

步骤：

  1. 遍历R，直到nature < R[i]为止
  2. 取出自然数的面值faceValue = nature - R[i-1]
  3. 将faceValue的二进制形式拆成7bit组
  4. 最后一个7bit的最高位添加一个bit：0
  5. 其余每个7bit的最高位前添一个bit：1
  6. 输出字节流bytes

准备工作：VLQ字符串

zipack的字符串禁用utf8，而是开创性地用VLQ自然数编码的Unicode字符，即将每个字符的Unicode编号和一个vlq自然数一一对应。

将字节流转换成字符串

  • 函数名：vlqs2string
  • 输入：字节流bytes，起始下标index，字符串长度length
  • 输出：字符串

步骤：

  1. 循环length次
  2. 每次调用vlq2nature函数得到一个Unicode编号
  3. 将这些编号转换成Unicode字符，输出字符串

将字符串转换成字节流

  • 函数名：string2vlqs
  • 输入：字符串string
  • 输出：字节流bytes

步骤：

  1. 循环string.length次，或遍历string的每个字符
  2. 每次提取出字符的Unicode编号（是一个自然数）
  3. 调用nature2vlq函数将编号转换成字节流
  4. 将所有字节流拼接成大字节流并输出

zipack类型树

zipack类型树

zipack的数据类型大致可以分为3个部分的前后拼接：前缀、长度、负载。上图是所有的前缀，长度代表负载的某种长度，不同类型的“长度段”有不同的含义，负载则是数据内容本身。

整数编码

整数有3个类型：小自然数、VLQ正整数、VLQ负整数，其中小自然数的最大值（127）紧接VLQ正整数的最小值（128），VLQ负整数从-1开始。

小自然数

  • 前缀：0
  • 长度：无
  • 负载：7bit

小自然数的总长度是固定的1byte，大小从0到127，即从 0000 0000 到 0111 1111。

VLQ正整数

  • 前缀：1111 1000
  • 长度：无
  • 负载：vlq自然数 128

VLQ负整数

  • 前缀：1111 1001
  • 长度：无
  • 负载：-1-vlq自然数

小数编码

zipack的小数不采用IEEE的浮点数编码规则，而采用一种原创的“精度反转编码”算法。

  • 前缀：正小数1111,0010，负小数1111,0011
  • 长度：无
  • 负载：精度反转(整数部分，小数部分)

精度反转算法

以一个二进制正小数110.0101为例，将其编码为一段字节流，负小数同理

  1. 将小数分为整数部分和小数部分，分为110、0.0101
  2. 将整数部分编码成VLQ自然数（A）
  3. 将小数部分末端无意义的0去掉
  4. 小数部分截取小数点后的内容得到一个字符串“0101”
  5. 将字符串反转得到“1010”
  6. 通过类型转换转成自然数1010
  7. 减一得1001
  8. 将该自然数存储为VLQ自然数（B）
  9. 输出A、B

字符串编码

zipack字符串的长度段代表字符的数量。

短字符串

  • 前缀：100
  • 长度：5bit
  • 负载：string2vlqs(string)

VLQ字符串

  • 前缀：1111,0101
  • 长度：vlq自然数 32
  • 负载：string2vlqs(string)

字典中的“键”

  • 前缀：无
  • 长度：vlq自然数
  • 负载：string2vlqs(string)

纯字节流类型

zipack纯字节流的长度段代表字节的数量。

  • 前缀：1111,0100
  • 长度：VLQ自然数
  • 负载：字节流

简单类型：Boolean和Null

True

  • 前缀：1111,0000
  • 长度：无
  • 负载：无

False

  • 前缀：1111,0001
  • 长度：无
  • 负载：无

null

  • 前缀：1111,1010
  • 长度：无
  • 负载：无

复合类型：列表

zipack列表的长度段代表列表中元素的数量，元素可以是任何其他zipack类型。

短列表

  • 前缀：101
  • 长度：5bit
  • 负载：若干个子元素的拼接

VLQ列表

  • 前缀：1111,0110
  • 长度：VLQ自然数 32
  • 负载：若干个子元素的拼接

复合类型：字典

zipack字典的长度段代表字典中键值对的数量，其中键是string类型，值是任意zipack类型。zipack字典是有序字典，键值对之间可以有顺序。键是string类型，但和zipack本来的string类型不同之处在于，键没有前缀，而且长度段是一个没有偏移的vlq自然数，可以参考上面的定义。

小字典

  • 前缀：110
  • 长度：5bit
  • 负载：键,值,键,值...

VLQ字典

  • 前缀：1111,0111
  • 长度：vlq自然数 32
  • 负载：键,值,键,值...

保留类型

zipack预留了6个尚未定义的类型前缀，开发者和用户可以自行扩展，赋予其新的意义。

  • 1110
  • 1111 1011
  • 1111 1100
  • 1111 1101
  • 1111 1110
  • 1111 1111
编程算法 unicode

0 人点赞