压缩篇：XOR & DFCM

前言

该篇主要介绍另一种数值压缩算法：异或 XOR，它与 delta-of-delta 算法有相似之处，但是大部分场景下数值基本都是无规律可寻的，所以差值的思想并不适用。本文主要介绍基于 XOR 的一种高效的压缩算法 DFCM。

XOR & DFCM 参考论文：

http://www.vldb.org/pvldb/vol8/p1816-teller.pdf https://userweb.cs.txstate.edu/~mb92/papers/dcc06.pdf

XOR 运算

摘取论文中的 XOR 数据：

附 Java 浮点数转换十六进制

System.out.println(Long.toHexString(Double.doubleToLongBits(15.5)));

System.out.println(Double.longBitsToDouble(Long.parseLong("402F000000000000", 16)));

DFCM

XOR 运算后的数值可以选择多种通用的压缩算法进行压缩，例如 Gzip、7zip、rar 等。论文中给出了各算法的压缩效率和压缩率的对比：

可见 DFCM 算法在压缩效率和压缩率上的表现都是非常优秀的。下面介绍下 DFCM 的实现原理。

通过 XOR 的运算结果可以看出都存在前导 0 和后导 0，尤其后导 0 的个数更多，DFCM 将前导 0 和后导 0 一并进行了压缩。DFCM 将 XOR 的值拆分为三部分：

• Meaningful Bits: 中间非零的个数
• Leading Zeros: 非零数值前面零的个数
• Trailing Zeros: 非零数值后面零的个数

DFCM 采用前一个 XOR 值对当前 XOR 值进行编码，具体编码规则如下：

• 第一个数值不用于压缩，用于作为参考值。
• 控制位计算规则：
  • 如果 XOR 值为 0，存储 1bit：0
  • 如果 XOR 值不为 0，控制位第一个 bit 存为 1，后续数据的计算方式如下：
    • 如果当前 XOR 的 Meaningful bits 落在了前一个 XOR的 Meaningful bits 范围内（即当前 XOR 的 Leading Zeros 长度大于等于前一个 XOR 的 Leading Zeros 长度并且当前 XOR 的 Trailing Zeros 长度大于等于前一个 XOR 的 Trailing Zeros 长度），则控制位的第二个bit为 1，接下来存 XOR 非零的数值。

    

    • 如果当前 XOR 的 Meaningful bits 不在前一个 XOR 的 Meaningful bits 范围内，则控制位的第二个 bit 为 0，后续存放：
      1. 5bits: Leading bits 个数
      2. 6bits: Meaningful bits 个数
      3. XOR 非零的数值

    

DFCM 压缩后效果：

压缩前：64 * 4 = 256bits

压缩后：64 + 19 + 23 + 12 = 118bits

总结

在时序数据场景，一小段时间范围内数值变化范围很小。XOR & DFCM 压缩算法在时序数据场景可以达到非常高的压缩比，在无序的数据中也可以取得很好的效果，同时系统的存储成本也会大幅度降低。

 

• Previous
  压缩篇：delta-of-delta编码
• Next
  Intellij IDEA高阶DEBUG大杀器