Comment la valeur de décompression de travail pour Facebook de Gorilles dans le cas où le nombre de zéros ne sont pas stockées

Question

Je me réfère à ce document: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

Ma question est concernant la section 4.1.2 où il est dit:

Lorsque XOR est non nul, calculer le nombre d'attaque et de fuite des zéros dans le XOR, magasin de bits à ‘1’ suivi par de a) ou b):

(a) (Contrôle de bits ‘0’) Si le bloc de bits significatifs les chutes à l'intérieur du bloc de la précédente significative bits, c'est à dire, il y a au moins autant de zéros et de comme beaucoup de zéros à droite comme avec la valeur précédente, utiliser cette information pour la position du bloc et de l'enregistrer dans le sens XORed valeur.

Lors de la décompression, comment savons-nous si nous devons ajouter des zéros de gauche ou de résidus de zéros?Par exemple, disons que nous avons 48 bits des nombres:

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

et

A xor B = 0x000 ffff 00000

B xor C = 0x000 0ff0 00000

Si nous suivons l'algorithme de compression pour A xor B nous allons stocker le nombre de zéros , ce qui est 12, ainsi que le sens de bits ffff.

Maintenant, pour B xor C parce que "il y a au moins autant de zéros et comme beaucoup de zéros à droite comme avec la précédente valeur", de sorte que nous ne stocker les bits significatifs ff.Quand je veux décoder ff, de base , sur les précédentes comprimé bits, je sais que j'ai au moins 12 zéros et 20 de résidus de zéros, mais j'ai encore besoin de remplir de 8 zéros;dois-je faire ff00 ou 00ff ou autre combinaison?

Answer 1

J'ai trouvé ma réponse après la lecture de l'implémentation de référence: https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp

L'utilisation du terme "significatif bits" dans le document est ambigu.J'ai pensé à la phrase "l'utilisation de cette information pour la position du bloc et de l'enregistrer dans le sens XORed de la valeur". des moyens pour stocker les bits avec tous la fuite et de zéros dépouillé parce que "significatif XORed valeur" est une valeur sans attaque et de fuite de zéro.Mais, selon l'implémentation de référence vous venez d'enlever la même quantité d'attaque et de fuite des zéros comme valeur précédente delta;le sens de bits dans ce cas peut encore contenir certains des principaux et des zéros à la fin.

Ainsi, pour l'exemple de la question, nous devrions magasin 0ff0 comme significative bits au lieu de juste ff.