Squeeze Compressor

overview

核心的想法是：对于可精确预测的数据，通过曲线拟合；对于难以合适预测的数据，通过二进制表示的分析来进行有损压缩。

implement

压缩前需要的三个参数：绝对误差范围、相对误差范围、压缩率

以下是压缩的具体算法：

convert array

通过实验发现，建立曲线是压缩中最大的时间开销。鉴于有较低的转换开销、良好地保留了局部性的两个优势，使用数据数组原来在内存中的序列用来压缩会更好。

curve-fitting

每个数据点都会检查其能否根据先前的数据，使用以下三种曲线近似方法的一种来表示，若可以，易知即可压缩成2bit的数据。

• PNF：通过前一个数据点的原数据来预测（01）
• LCF：前两个数据点的原数据的线性估计（10）
• QCF：通过前三个数据点的二次曲线来预测（11）
• 无法预测：（00）

该部分会分为以下几步来实现：
假设有M个数据点

• 分配2Mbits的内存，用于存放压缩后的数据
• 计算数据值的变化范围
• 检查数据点，决定近似方法，若可近似，将对应的编号写入内存处；若不可近似，则通过对二进制表示的分析来压缩，并写入另一个数组

由以上的算法，可以看出，该部分的时间复杂度为O(n)，时间和数据量成线性关系十分优秀。

binary representation analysis

以下是二进制表示分析的过程

• 通过将所有数据减去中位数，产生规范化数据，以缩小数值的范围（可以用更少的位数来表示）
• 接着，在误差允许的范围内，抛弃部分影响不大的有效位，再计算需要多少位来表示（注意此处最小的单位为字节，需要将结果约成8的倍数）
• 最后，计算需要填充的0的数量，用2bits即可表示（单位为一个全0的字节）

further explore

SZ压缩提高了数据压缩的速度以及压缩率。可以应用于CPU、GPU、FPGA以及其他科研领域。上文只是SZ的最初实现（SZ 0.1-1.0)的算法。目前SZ以及更新到SZ 3.0了

citations

大部分内容来自于以下的论文：

• SZ 0.1-1.0: Sheng Di, Franck Cappello, “Fast Error-bounded Lossy HPC Data Compression with SZ“, in IEEE International Parallel and Distributed Processing Symposium (IPDPS 2016), Chicago, IL, USA, 2016.