0. background

物联网小bit蓝牙传输压缩。

1. goal

timestamp	col_1	col_2
123	56	4
124	57	4
130	55	4

对于上表由多条record组成的时间序列block按照列方向进行压缩，打包成压缩块（pack）。

2. Algorithm

选择这些步骤的原因：

forecast：连续样本具有高度相似性
run-length：数据没变化的时候极端压缩
bit pack：同一block使用相同宽度，利用数据周期相关
entropy：提高压缩比

2.1 forecasting

（1）delta 算法

$forecastx = x{i-1}$

例如col_1：$x_1=56,x_2 = 57, x_3 = 55; forecast_x_2=56, forecast_x_3=57$

（2）fast integer regression

$forecast_xi = x{i-1} + \alpha x{i-1} - \alpha x{i-2} + \epsilon_i$

$\alpha $由机器学习算法得到

论文中没有提及fast integer regression的存储和使用，在后续的简介中都是以delta算法为例陈述。

存储

压缩算法不直接存储$x_i$也不存储$forecast_x_i$，而是存储$err_i = x_i-forecast_x_i$

2.2 bit packing

Bit pack 在论文中也是以delta算法为基础介绍的。

sprintz算法以数据块（block）为单位进行压缩。对于每一个数据块而言，上一块数据块的最后一条记录（record），称为“previous value”。

不妨设previous value为：

123	55	4

经过delta算法处理后，得到delta数据块

delta_timestamp	delta_col_1	delta_col_2
0	1	0
1	1	0
6	-2	0

由于出现负数，为方便后续进行二进制编码，进行zigzag encoding。即对于正整数，可以把无意义的0去掉，只存储从1开始的”有效”数据，这样就可以压缩数据了。例如，对于正整数1，其补码(当代计算机中实际按补码表示整数)按位展开，即为(00000000 00000000 00000000 00000001)补，显然，我们可以只用一个字节甚至1bit来存储有效数据。（算术左移低位补0；算术右移，若符号位为0，高位补0；若符号位为1，高位补1；）

得到

zigzag_timestamp	zigzag_col_1	zigzag_col_2
0	2	0
2	2	0
12	3	0

变为二进制表示

bit_timestamp	bit_col_1	bit_col_2
0	10	0
10	10	0
1100	10	0
4bit表示	2bit表示	0bit表示

由最后一行得到header

100（十进制表示4）	10（十进制表示2）	0

整理得到压缩块

header	100	10
payload1	0	10
payload2	10	10
payload3	1100	10

2.3 entropy coding

对Header跟Payload使用哈夫曼编码。

AHHHHHHA

Sprintz