先行ゼロの数が格納されていない場合、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値を保存するだけだと思いました。"ビットを格納することを意味します すべて "意味のあるXORed値"は、先頭と末尾のゼロを持たない値であるため、末尾と先頭のゼロは削除されます。しかし、参照実装によれば、前の値のデルタと同じ量の先頭と末尾のゼロを取り除くだけです;この場合の意味のあるビットには、先頭と末尾のゼロが含まれている可能性があります。

したがって、質問の例では、次のように保存する必要があります 0ff0 ちょうどの代わりに意味のあるビットとして ff.