压缩算法gorilla paper encoding原理
目录
引：
从之前研究TSM文件格式，发现float类型的value是以facebook的gorilla paper encoding的算法进行压缩。
当时没有去深究，现在把这个算法的详细逻辑给理出来.
这个算法是float的压缩，首先得清楚float的在内存中是如何保存的。
IEEE754
浮点数简述
以64位float为例，下文float都是指64位float
IEEE754规定了float在内存中的存储方法，以 num * 2^n 来描述(num为二进制的1.xxxxx )
符号位顾名思义，正数为0，负数为1
指数位是 n + （2^10 - 1）也就是 n+1023
尾数位就是 num 小数点后面的所有值了。
举例
以数字 2300为例。
其二进制为：100011111100
转化成指数形式：1.00011111100*2^11
指数位就是 11+1023 = 1034， 二进制：10000001010， （指数位基准为1023）
尾数位： 取小数点后面的值 00011111100
剩下的尾数位补0，凑成一共64位
结果：0100000010100001111110000000000000000000000000000000000000000000
转换成16进制：40A1F80000000000
由此可知，float在内存中的存储形式。可以看出来，有效数字普遍靠前。
算法原理
工作流程
gorilla paper encoding就是针对这些8字节的float进行压缩的。
这个压缩过程其实就是一个字节流（位流）按照一定格式的不断追加。
详细流程如下
第一个字节置为 0x10, 代表这个算法名字
接着写入第一个数，无压缩，8字节。
写入一个数流程图（从第二个数开始）
在所有数都添加完之后，再添加一个结束的数字
0x7FF8000000000001， not-a-number，代表结束符
最后补全一些位0，使得字节流完整。
压缩结构
从流程图可知，添加一个数 就有三种情况：
从第一个数开始是一个完整的8 bytes数，后面的所有树存的都是与上一个数异或得到的delta值。
简要分析
存delta值有什么好处？
1. 通过delta值也很容易求出实际值
delta = A^B
那么 B = delta^B
2. 相近的数字(这个相近其实很宽)，异或的delta值 前导0 和 后导0 数量会很多，也就是有效位会很少，提高压缩率
举例：
2300 ， float类型表示为 40A1F80000000000
10000， float类型表示为 40C3880000000000
这两个数字异或delta = 0062700000000000
二进制0000000001100010011100000000000000000000000000000000000000000000
前导0， 9个； 后导0， 44个。 有效位数，11。
压缩率测试
写入800个整数，以浮点数形式压缩，实测结果如下：
| 原始数据类型 | 数量 | 数据规律 | 原始数据size | 压缩后数据size | 压缩率 |
| INT | 800 | 随机数0~100000 | 3200 bytes | 2156 bytes | 67% |
| INT | 800 | 随机数1000~10000 | 3200 bytes | 1816 bytes | 57% |
| INT | 800 | 起始为10000 每次递增0~500随机数 |
3200 bytes | 1793 bytes | 56% |
小结：
这篇描述了gorilla paper encoding的算法逻辑，回头看来很简单，一开始从decode代码开始看就很难懂，后来从encode的部分开始看，就通俗易懂了。
有时间的话，自己实现这个压缩算法，做一些数据测试，看看压缩率根据数据的特点最高最低能怎样。