在不存储前导零计数的情况下，Facebook 的 Gorilla 的值解压如何工作

Question

我指的是这篇论文： http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

我的问题是关于第 4.1.2 节，它说：

当XOR不为零时，计算XOR中的前导和尾随零的数量，存储位“ 1”，然后是a）或b）：

（a）（控制位'0'）如果有意义的位块属于先前有意义的位的块，即，至少有许多领先的零和尾随零与上一个值一样多，请使用该信息，块位置，只存储有意义的Xored值。

解压缩时，我们如何知道是否应该添加前导零或尾随零？例如，假设我们有以下 48 位数字：

A = 0xfff ffff fffff
B = 0xfff 0000 fffff
C = 0xfff 0ff0 fffff

和

A xor B = 0x000 ffff 00000

B xor C = 0x000 0ff0 00000

如果我们遵循压缩算法 A xor B 我们将存储前导零的数量，即 12, ，以及有意义的位 ffff.

现在，为了 B xor C 因为“至少有与前一个值一样多的前导零和尾随零”，所以我们只存储有意义的位 ff. 。当我想解码的时候 ff, ，根据之前的压缩位，我知道我至少有12个前导零和20个尾部零，但我仍然需要填写8个零；我应该做什么 ff00 或者 00ff 或者其他组合？

Answer 1

我在阅读参考实现后找到了答案： https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp

论文中“有意义的位”一词的使用含糊不清。我认为该句子“将这些信息用于块位置，而只是存储有意义的Xored值”。意味着与 全部 尾随零和前导零被删除，因为“有意义的异或值”是没有前导零和尾随零的值。但是，根据参考实现，您只需去掉与先前值增量相同数量的前导零和尾随零即可；在这种情况下，有意义的位可能仍包含一些前导零和尾随零。

因此，对于问题中的示例，我们应该存储 0ff0 作为有意义的位而不仅仅是 ff.