vlambda博客
学习文章列表

学习Protobuf,ZigZag是啥你真的知道么?

结合上一篇文章,我们了解到通过Varint 编码整数,如遇到负数或大整数,就不具备压缩优势了?由于引入了MSB,不但没有好的压缩效果,还加大了存储,这明显不是我们想要的。以下,我们聊聊怎么解决这类问题。

这篇文章,也是学习Protobuf过程中偶然所得,算法简洁,篇幅较短,预计阅读时间 8 分钟,如果对您有帮助,还望不吝评价,求点赞、求评论、求转发

在聊ZigZag算法之前,我们先聊聊进制原码反码补码相关的知识点,如果你懂,可跳过直接往下翻。

什么是进制?

所谓进制,就是当某一位上的信息满时,需要往前进位。比如,十进制,就是当某一位上的数满十时进位;而某一位上的数满二时进位就是二进制,等等。

进位之间都可以相互转化,例如:十进制:10 → 二进制:1010 → 十六进制:A

我之前看过一个答案,说:为什么十进制比较通用?因为咱人类只有 10 个手指头,数一遍刚好十个数,所以十进制自然就成为默认的进制。那如果人类长 11 手指头,说不定就是十一进制。

后来计算机的出现,一个数据的有无是最天然的信息承载单元,所以由 0 和 1 组成的二进制很自然成为计算机的进制方式。—— 老苗

计算机系统里面对二进制定义了原码反码补码,为了更简单的理解,后续我们用1 Byte=8 bits进行讲解。

原码是啥?

定义:用第一位表示符号(0为非负,1为负数),其余位表示值,如下:

  • +8 -> 原码:0000 1000
  • -8 -> 原码:1000 1000
学习Protobuf,ZigZag是啥你真的知道么?

有了原码的表示方法就可以对数进行算法运算,但是很快就发现用带符号位的原码进行乘除运算结果正确,但在加减运算时就出现了问题,如下:

乘法规则:符号位做“异或”运算,数值位做类似十进制的“乘法”运算
十进制:+8 * (-8) = -64
原码:0000 1000 * 1000 1000 = 1100 0000 = -64

十进制:+8 + (-8) = 0
原码:0000 1000 + 1000 1000 = 1001 0000 = -16  # 显然不正确

看起来加法运算也没什么问题,发现问题是出在符号位上?于是计算机大佬们引入了反码。

反码都做了啥?

定义:用第一位表示符号(0为非负,1为负数),其余位,非负数保持不变,负数按位求反,如下:

  • +8 -> 原码:0000 1000 -> 反码:0000 1000
  • -8 -> 原码:1000 1000 -> 反码:1111 0111

我们继续进行上述的加法运算

  • 十进制:+8 + (-8) = 0
  • 反码:0000 1000 + 1111 0111 = 1111 1111 = -0

竟然结果是-0,这个结果让人猝不及防啊!!!

分析发现,如果用原码 + 补码表示二进制计算,表面上看,似乎挺好的。不过仔细思考就会发现两个问题:

第一,0竟然可以用两种编码表示,+0 和 -0:

  • +0 -> 原码:0000 0000 -> 反码:0000 0000
  • -0 -> 原码:1000 0000 -> 反码:1111 1111

第二,计算机不清楚符号位的存在,因此参加运算后,会出现结果为-0这样的现象。

这看起来怪怪的,为了解决这些问题,计算机巨佬们又引入了补码

补码有啥用?

定义:用第一位表示符号(0为非负,1为负数),剩下的位非负数保持不变,负数按位求反且末尾加一。

  • +8 -> 原码:0000 1000 -> 补码:0000 1000
  • -8 -> 原码:1000 1000 -> 补码:1111 1000

现在我们继续看看,把符号位带入运算会出现什么结果?

-> 8 + (-8)
-> 0000 1000 + 1111 1000
-> 0000 0000
-> 0

很明显,通过引入补码,我们解决了此类问题,计算机运算过程中,就不用关心符号问题,统一按照满二进一规则处理即可

学习Protobuf,ZigZag是啥你真的知道么?

好了,知识小点就说到这了,接下来,进入真正的主题。

ZigZag 是什么?

在大多数计算机系统中,我们通常使用定长整型(fixed length intergers)表示数值。比如:

  • 4 bytes表示 Int32
  • 8 bytes表示 Int64

为什么这样设置呢?这样能便于我们的计算机处理,加快处理的速度。

但是在系统网络通信(RPC)时,为了传输一个1,我们需要传输00000000 00000000 00000000 00000001 32 个 bits。这么多字符,而有价值的数据只有 1 位,这T&M也太浪费了呀!

那该怎么办呢?ZigZag算法由此而生。

ZigZag 的原理

编码介绍

ZigZag编码将有符号整数映射成无符号整数,以便绝对值较小的数字对应较小的编码值,比如:-1 -> 11 -> 2,具体如图:

原数 编码
0 0
-1 1
1 2
-2 3
2 4
... ...
-(2^31 -1) 2^32 - 3
2^31 -1 2^32 -2

如上,这种方式通常由正整数和负整数来回曲折编码,看着还挺有意思的。难道就因为这样,计算机大佬们才给取了个名字叫ZigZag(锯齿形线条)算法???

编码规则

  • a.非负整数,符号位后移
  • b.负整数,符号位后移,数据位按位求反

在大多数计算机系统中,以4 Bytes8 Bytes 来表示整数(Int32、Int64)。下面我们选择Int32进行一个简单的演示,如下:

  • 十进制:0
    • 补 码 : 00000000 00000000 00000000 00000000
    • ZigZag:00000000 00000000 00000000 0000000 0
  • 十进制:1
    • 补 码 : 00000000 00000000 00000000 00000001
    • ZigZag:00000000 00000000 00000000 0000001 0
  • 十进制:-1
    • 补 码 : 11111111 11111111 11111111 11111111
    • ZigZag:00000000 00000000 00000000 0000000 1

解码规则

  • 类似编码,反向操作即可

ZigZag 编码实现(Python)

def int32_to_zigzag(n):
    return (n << 1) ^ (n >> 31)

ZigZag 解码实现(Python)

def zigzag_to_int32(zz):
    return (zz >> 1) ^ -(zz & 1)

总结一下

大多数情况下,通过ZigZag编码结合Varint算法,对整数都有好的压缩效果,但如果遇到绝对值大的整数,就不再具有压缩优势了。

不过,我们通常使用到的整数往往也都比较小。

参考文档

  • https://en.wikipedia.org/wiki/Zigzag
  • https://developers.google.com/protocol-buffers/docs/encoding#types
  • https://studygolang.com/articles/35309

❤️❤️❤️读者每一份热爱都是笔者前进的动力!我是三十一,感谢各位朋友:求点赞、求评论、求转发,大家下期见!