背景图

数字的压缩存储

最近在学习比特币的知识,突然发现一个compact合适,然后又想起了以太坊的RLP编码的问题,想着想着,就想着数据是如何压缩存储的。于是上网搜索一下,发现了thift序列化的压缩实现。

前言

不管怎么说技术的本质就是数字,再复杂的东西也只是数字累积起来的。在计算机中数据的存储采用补码的方式,当然也有反码的概念,这里就不多说了。我们下面所说的算法就是指zigzag算法。

思路

一般来说数据的存储如果遇到1这样的数据还用4个字节的存储是不是很浪费空间,00000000 00000000 00000001有那么多的0是多余的,那么我们可以选择不存储。最后放在一个字节中去存储就会变成00000001,这样就省了不少的空间。

负数

可是遇到-1会怎么样呢?(-1)10 = (11111111 11111111 11111111 11111111),前面全是1,那怎么处理呢?

zigzag给出了一个很巧的方法:我们之前讲补码讲过,补码的第一位是符号位,他阻碍了我们对于前导0的压缩,那么,我们就把这个符号位放到补码的最后,其他位整体前移一位:

(-1)10 = (11111111 11111111 11111111 11111111) = (11111111 11111111 11111111 11111111)符号后移

但是即使这样,也是很难压缩的,因为数字绝对值越小,他所含的前导1越多。于是,这个算法就把负数的所有数据位按位求反,符号位保持不变,得到了这样的整数:

(-1)10 = (11111111 11111111 11111111 11111111) = (11111111 11111111 11111111 11111111)符号后移 = (00000000 00000000 00000000 00000001)zigzag

这样就出现了很多的0,但是如果都是1的话好像也没啥问题,对负数就去1呗。这里还是以去0为主。

再看整数

(1)10 = (00000000 00000000 00000000 00000001) = (00000000 00000000 00000000 00000010)符号后移 = (00000000 00000000 00000000 00000010)zigzag

整型值与zigzag值转化

1
2
3
4
5
6
7
int int_to_zigzag(int n) {
return (n <<1) ^ (n >>31);
}

int zigzag_to_int(int n) {
return (((unsignedint)n) >>1) ^ -(n & 1);
}

压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int write_to_buffer(int zz, byte* buf, int size) {
int ret =0;
for (int i =0; i < size; i++) {
if ((zz & (~0x7f)) ==0) {
buf[i] = (byte)zz;
ret = i + 1;
break;
} else {
// 第八位补一个1
buf[i] = (byte)((zz &0x7f) |0x80);
// 换下一个七位,继续进行测试。
zz = ((unsignedint)zz)>>7;
}
}
return ret;
}

这里 (~0x7f)16 = (11111111 11111111 11111111 10000000). 他的作用就是看除开最后七位后,还有没有信息。这个看起来不是很直观,还是举一个例子吧:

(-1000)10 = (11111111 11111111 11111100 00011000) = (00000000 00000000 00000111 11001111)zigzag

这个数的转换经过下面几个步骤:

  1. 与(~0x7f)做与操作的结果,高位还有信息,所以,我们把低7位取出来,并在倒数第八位上补一个1(0x80):11001111
  2. 将这个数右移七位:(00000000 00000000 00000000 00001111)zigzag
  3. 重复1,但是检测出高位都是0,设置数据为:00001111

这个时候我们可以最终得出如下的结果:
(-1000)10 = (11111111 11111111 11111100 00011000) = (00000000 00000000 00000111 11001111)zigzag = [11001111, 00001111]压缩后

注意:这里每个字节的第一位都是有意义的,如果我们读一个数,只要发现每个字节的第八位是0,就代表这个数字读取就结束了;但是如果是1的话,就只能向下读。这里要注意一旦数据比较大,32位的数据可能就变成40位了,但是这样的数据特别大的时候才会出现。

解压

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int read_from_buffer(byte* buf,intmax_size) {
int ret =0;
int offset =0;

for (int i =0; i < max_size; i++, offset +=7) {
byte n = buf[i];

if ((n &0x80) !=0x80) {
ret |= (n <<offset);
break;
} else {
ret |= ((n &0x7f) << offset);
}
}
return ret;
}

这个就是上面操作的逆过程而已。

总结

这个设计的比较巧妙,利用高位来标记,的确可以省不少的空间。

参考和引用

小而巧的数字压缩算法:zigzag

0%