Wie funktioniert die Wertdekomprimierung für Facebooks Gorilla, wenn die Anzahl der führenden Nullen nicht gespeichert wird?

Question

Ich beziehe mich auf dieses Papier: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

Meine Frage bezieht sich auf Abschnitt 4.1.2, wo es heißt:

Wenn XOR ungleich Null ist, berechnen Sie die Anzahl der führenden und nachfolgenden Nullen im XOR, und speichern Sie Bit '1', gefolgt von a) oder b):

(a) (Kontrollbit '0') Wenn der Block aus sinnvollen Bits in den Block früherer aussagekräftiger Bits fällt, dh mindestens so viele führende Nullen und so viele nachfolgende Nullen wie beim vorherigen Wert, verwenden Sie diese Informationen für Die Blockposition und speichern Sie einfach den aussagekräftigen Xored -Wert.

Woher wissen wir beim Dekomprimieren, ob wir führende Nullen oder abschließende Nullen hinzufügen sollten?Nehmen wir zum Beispiel an, wir haben die folgenden 48-Bit-Zahlen:

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

Und

A xor B = 0x000 ffff 00000

B xor C = 0x000 0ff0 00000

Wenn wir dem Komprimierungsalgorithmus für folgen A xor B Wir werden die Anzahl der führenden Nullen speichern 12, sowie die sinnvollen Bits ffff.

Jetzt für B xor C denn „es gibt mindestens so viele führende Nullen und so viele nachgestellte Nullen wie beim vorherigen Wert“, also speichern wir nur die sinnvollen Bits ff.Wenn ich entschlüsseln möchte ff, Basierend auf den vorherigen komprimierten Bits weiß ich, dass ich mindestens 12 führende Nullen und 20 abschließende Nullen habe, aber ich muss noch 8 Nullen ausfüllen;soll ich tun ff00 oder 00ff oder eine andere Kombination?

Answer 1

Ich habe meine Antwort gefunden, nachdem ich die Referenzimplementierung gelesen hatte: https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp

Die Verwendung des Begriffs „bedeutungsvolle Bits“ in der Arbeit ist nicht eindeutig.Ich dachte, der Satz "Verwenden Sie diese Informationen für die Blockposition und speichern Sie einfach den aussagekräftigen Xored -Wert." bedeutet, die Teile mit zu speichern alle Die nachgestellten und führenden Nullen werden entfernt, da der „aussagekräftige XOR-Wert“ ein Wert ohne führende und nachgestellte Null ist.Aber gemäß der Referenzimplementierung entfernen Sie einfach die gleiche Anzahl führender und nachfolgender Nullen wie das vorherige Wertdelta;Die sinnvollen Bits können in diesem Fall noch einige führende und nachgestellte Nullen enthalten.

Für das Beispiel in der Frage sollten wir also speichern 0ff0 als bedeutungsvolle Bits statt nur ff.