zig-zag编码和group varint编码

2013-04-18

zig-zag编码

zig-zag编码是一种将有符整形转化成无符的整形的一种方式。比如int32转uint32:(n<<1)^(n>>31)

刚开始这个代码看了好久都没看懂,后来终于明白了。其实zig-zag的原理就是,将int的0,-1,1,-2,2,-3,3...对应的转换成uint的0,1,2,3,4,5,6...

找一找规律,其实转化方式就是:对正数,将它乘以2;对负数,将它的数值乘2减1

乘以2用位运算就是(n>>1),而补码做加法减法都是一样的,所以这里正好是加上符号位!于是最终就是公式(n<<1)^(n>>31)。

即使明白了zig-zag做变换的本质,那么转回来也很容易明白了。可以看到规律:偶数都对应转换前的负数,奇数都对应转换前的正数。比如2是-1转换得到的,3是2转换得到的。

转换回去就是将数值部分除以2,用奇偶决定符号位。(n >> 1) ^ -(int32_t)(n & 1)


思考,我看到zig-zag的使用场景之一是,做变长整形压缩。先将int用zig-zag转成uint,再用变长编码做uint的压缩。

我在想一个问题是这样值不值?因为用zig-zag编码之后,对于原来的正数它的值就增大了两倍,需要更长的变长编码,压缩率变低了。考虑一种极端的情景就是126,126,122,124,123,111,111,103,125,127,125,-1,3,111...这样一个序列,绝大部分都是正数,如果不进行zig-zag直接做变长编码,只要13+5个字节就可以编码下来了。但如果先做zig-zag,就需要13*2+1个字节才能压缩,亏了!

最后要想一下什么时候做是划算的。对负数,不做zig-zag需要5个字节编码,做了需要1-4个字节。对正数,不做zig-zag需要原来字节数的两倍。假设平均下来每个数的变长编码字节长度为E,负数在整个序列中占的比重是p,对于最终编码长度的期望,给套公式就是: non-zig-zag = 5p+E(1-p) = 5p+E-Ep zig-zag = Ep+E2*(1-p) = 2E-Ep

最终就是比较E跟5p的大小决定变长编码之前做zig-zag编码是否划算。如果E小于5p,则做zig-zag是划算的。E小于5p的含义就是按数值部分的变长编码平均字节长度,要小于负数比例的5倍。

group varint编码

group varint编码与varint编码不同。varint编码中用1位来决定下一字节是否还是属于同一个int。而group varint编码的出发点是,用2个位来记录长度。将4个int为一组进行编码,长度信息全部记录在第一个字节中。

由于这种方式能大大地减少分支,移位,取mask的操作,因此这种编码算法的速度非常快。

编码