Come funziona la decompressione dei valori per Gorilla di Facebook nel caso in cui il conteggio degli zeri iniziali non venga memorizzato

Question

Mi riferisco a questo documento: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

La mia domanda riguarda la sezione 4.1.2 dove dice:

Quando xor è diverso da zero, calcola il numero di zeri di piombo e finali nell'XOR, memorizzare bit '1' seguito da A) o B):

(a) (Bit di controllo '0') Se il blocco di bit significativi rientra nel blocco dei bit significativi precedenti, cioè, ci sono almeno altrettanti zeri iniziali e tanti zeri finali quanti sono i valori precedenti, usa queste informazioni per la posizione del blocco e memorizza solo il valore XOR significativo.

Durante la decompressione, come facciamo a sapere se dobbiamo aggiungere zeri iniziali o zeri finali?Ad esempio, supponiamo di avere i seguenti numeri a 48 bit:

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

E

A xor B = 0x000 ffff 00000

B xor C = 0x000 0ff0 00000

Se seguiamo l'algoritmo di compressione per A xor B memorizzeremo il numero di zeri iniziali, ovvero 12, così come i bit significativi ffff.

Ora, per B xor C perché "ci sono almeno tanti zeri iniziali e tanti zeri finali quanti sono nel valore precedente", quindi memorizziamo solo i bit significativi ff.Quando voglio decodificare ff, in base ai bit compressi precedenti, so di avere almeno 12 zeri iniziali e 20 zeri finali, ma devo ancora inserire 8 zeri;dovrei ff00 O 00ff o altra combinazione?

Answer 1

Ho trovato la mia risposta dopo aver letto l'implementazione di riferimento: https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp

L'uso del termine "pezzi significativi" nel documento è ambiguo.Ho pensato che la frase "usa quelle informazioni per la posizione del blocco e memorizza solo il valore XOR significativo." significhi memorizzare i bit con Tutto gli zeri finali e iniziali vengono rimossi perché il "valore XOR significativo" è un valore senza zero iniziali e finali.Ma, secondo l'implementazione di riferimento, è sufficiente eliminare la stessa quantità di zeri iniziali e finali del delta del valore precedente;i bit significativi in ​​questo caso possono ancora contenere alcuni zeri iniziali e finali.

Quindi, per l'esempio nella domanda, dovremmo memorizzare 0ff0 come bit significativi invece che semplicemente ff.