integer - 为什么 varint 是一种有效的数据表示？

Question

我目前正在研究 protocol buffers 的文档.变体被描述为:

Each byte in a varint, except the last byte, has the most significant bit (msb) set – this indicates that there are further bytes to come. The lower 7 bits of each byte are used to store the two's complement representation of the number in groups of 7 bits, least significant group first.

我的问题是为什么人们会选择在每个字节上丢失一位的表示？这种方法有什么好处？

Answer 1

实际上，绝大多数整数值都很小。即使在您预计某个值有时会非常大的情况下，因此您将其设为 32 位甚至 64 位，但它通常很小，因为从统计上讲，大多数物理量都遵循幂律分布。因此，如果小值可以存储在更少的字节中，那么大值占用一个额外的字节就可以了。

唯一没有好处的整数类型是散列或随机生成的 ID 号，它们实际上并不代表数量，而只是一个位串。对于这些，你应该使用 Protobufs 的 fixed32或 fixed64类型。

请注意，varint 编码节省了线路上的空间，但实际上相对较慢，因为它需要大量分支来编码/解码。当然，它不像文本编码那么慢，但随着二进制格式的发展，它并不是那么好。这就是为什么Cap'n Proto的原因之一决定覆盖这个决定，只在线路上放置固定宽度的整数。 Cap'n Proto 还包括一个可选的“打包”算法，它压缩零值字节，产生与 Protobuf 相似的消息大小，但通常更快，因为该算法使用较少的分支。

(披露:我是 Cap'n Proto 的作者，也是 Google 发布的大部分 Protobuf 代码的作者。)