本篇文章为你整理了整数压缩编码 ZigZag（整数压缩算法）的详细内容，包含有数字压缩编码 整数压缩算法 压缩编码算法 压缩编码原理 整数压缩编码 ZigZag，希望能帮助你了解 整数压缩编码 ZigZag。
在分析Avro源码时，发现Avro为了对int、long类型数据压缩，采用Protocol Buffers的ZigZag编码（Thrift也采用了ZigZag来压缩整数）。
1. 补码编码
为了便于后面的分析，我们先回顾下几个概念：
原码：最高位为符号位，剩余位表示绝对值；
反码：除符号位外，对原码剩余位依次取反；
补码：对于正数，补码为其自身；对于负数，除符号位外对原码剩余位依次取反然后+1。
补码解决了原码中\(0\)存在两种编码的问题：
\[0=[0000 \enspace 0000]_原=[1000 \enspace 0000]_原
\]
补码\([1000 \enspace 0001]_补\) 表示\(-127\)；此外，原码中还存在加法错误的问题：
\[1 + (-1) = [0000 \enspace 0001]_原 + [1000 \enspace 0001]_原 = [1000 \enspace 0010]原 = -2
\]
若用补码，则可得到正确结果：
\[ 1 + (-1) = [0000 \enspace 0001]_补 + [1111 \enspace 1111]_补 = [0000 \enspace 0000]_补 = 0
\]
因此，在计算机存储整数时，采用的是补码。此外，整数的补码有一些有趣的性质：
左移1位（n 1），无论正数还是负数，相当于乘以2；对于正数，若大于Integer.MAX_VALUE/2（1076741823），则会发生溢出，导致左移1位后为负数
右移31位（n 31），对于正数，则返回0x00000000；对于负数，则返回0xffffffff
这些性质正好在ZigZag编码中用到了。
2. ZigZag
对于int值1，-1，20151103，均是用4 Bytes来表示：
\[1 = [00 \enspace 00 \enspace 00 \enspace 01] \\
-1 = [ff \enspace ff \enspace ff \enspace ff] \\
20151103 = [01 \enspace 33 \enspace 7b \enspace 3f]
\]
在《Huffman编码》中证明了压缩编码应满足：
高概率的码字字长应不长于低概率的码字字长
一般情况下，使用较多的是小整数，那么较小的整数应使用更少的byte来编码。基于此思想，ZigZag被提出来。
首先，ZigZag按绝对值升序排列，将整数hash成递增的32位bit流，其hash函数为h(n) = (n 1) ^ (n 31)；对应地long类型（64位）的hash函数为(n 1) ^ (n 63)。整数的补码（十六进制）与hash函数的对应关系如下：
拿到hash值后，想当然的编码策略：直接去掉hash值的前导0之后的byte作为压缩编码。但是，为什么ZigZag(64)=8001呢？这涉及到编码唯一可译性的问题，只有当编码为前缀码才能保证可译，即
任意一码字均不为其他码字的前缀
我们来看看，如果按上面的策略做压缩编码，则
h(0) = 0x0 = [00]
h(64) = 0x80 = [80]
h(16384) = 0x8000 = [80 00]
那么，当收到字节流[80 00]时，是应解码为两个整数64, 00，还是一个整数16384？因此，为了保证编码的唯一可译性，需要对hash值进行前缀码编码，ZigZag采用了如下策略：
input: int n
output: byte[] buf
if 第七位满1或有进位:
n = 0x80;
取低位的8位作为一个byte写入buf;
n =7（无符号右移7位，在高位插0）;
else:
取低位的8位作为一个byte写入buf
ZigZag编码的Java实现（从org.apache.avro.io.BinaryData抠出来的）：
/** Encode an integer to the byte array at the given position. Will throw
* IndexOutOfBounds if it overflows. Users should ensure that there are at
* least 5 bytes left in the buffer before calling this method.
* @return The number of bytes written to the buffer, between 1 and 5.
public static int encodeInt(int n, byte[] buf, int pos) {
// move sign to low-order bit, and flip others if negative
n = (n 1) ^ (n 31);
int start = pos;
if ((n ~0x7F) != 0) {
buf[pos++] = (byte)((n 0x80) 0xFF);
if (n 0x7F) {
buf[pos++] = (byte)((n 0x80) 0xFF);
if (n 0x7F) {
buf[pos++] = (byte)((n 0x80) 0xFF);
if (n 0x7F) {
buf[pos++] = (byte)((n 0x80) 0xFF);
buf[pos++] = (byte) n;
return pos - start;
ZigZag是一种变长编码，当整数值较大时，hash值的十六进制的有效位会较长，对应地ZigZag码字会出现需要5 byte存储；比如，
ZigZag(Integer.MAX_VALUE)=[fe ff ff ff 0f]
解码为编码的逆操作，首先，将ZigZag编码还原成hash值，然后用hash函数\(h(n)\)的逆函数\(h^{-1}(n)\) = (n 1) ^ -(n 1)得到原始的整数值。Java代码实现（在avro源码org.apache.avro.io.BinaryDecoder中）如下：
public static int readInt(byte[] buf, int pos) throws IOException {
int len = 1;
int b = buf[pos] 0xff;
int n = b 0x7f;
if (b 0x7f) {
b = buf[pos + len++] 0xff;
n ^= (b 0x7f) 7;
if (b 0x7f) {
b = buf[pos + len++] 0xff;
n ^= (b 0x7f) 14;
if (b 0x7f) {
b = buf[pos + len++] 0xff;
n ^= (b 0x7f) 21;
if (b 0x7f) {
b = buf[pos + len++] 0xff;
n ^= (b 0x7f) 28;
if (b 0x7f) {
throw new IOException("Invalid int encoding");
pos += len;
return (n 1) ^ -(n 1); // back to twos-complement
ZigZag总结如下：
ZigZag仅从经验出发，认为较小的整数会有较大的概率出现，故设计编码策略：小整数对应的ZigZag码字短，大整数对应的ZigZag码字长。
但是，在特定的场景下，比如，要传输的整数为大整数居多，ZigZag编码的压缩效率就不理想了。
以上就是整数压缩编码 ZigZag（整数压缩算法）的详细内容，想要了解更多 整数压缩编码 ZigZag的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。