Como funciona a descompressão de valores para o Gorilla do Facebook no caso em que a contagem de zeros à esquerda não é armazenada

Question

Refiro-me a este artigo: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

Minha pergunta é em relação à seção 4.1.2, onde diz:

Quando o XOR não for zero, calcule o número de zeros líderes e à direita no XOR, armazene '1' seguido por a) ou b):

(a) (Bit de controle '0') Se o bloco de bits significativos se enquadra no bloco de bits significativos anteriores, ou seja, existem pelo menos tantos zeros líderes e tantos zeros à direita quanto no valor anterior, use essas informações para a posição do bloco e basta armazenar o valor Xorle significativo.

Ao descompactar, como sabemos se devemos adicionar zeros à esquerda ou zeros à cauda?Por exemplo, digamos que temos os seguintes números de 48 bits:

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 seguirmos o algoritmo de compressão para A xor B armazenaremos o número de zeros à esquerda, que é 12, bem como os bits significativos ffff.

Para agora B xor C porque "há pelo menos tantos zeros à esquerda e tantos zeros à direita quanto no valor anterior", então armazenamos apenas os bits significativos ff.Quando eu quero decodificar ff, com base nos bits compactados anteriores, sei que tenho pelo menos 12 zeros iniciais e 20 zeros finais, mas ainda preciso preencher 8 zeros;Eu deveria fazer ff00 ou 00ff ou outra combinação?

Answer 1

Encontrei minha resposta depois de ler a implementação de referência: https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp

O uso do termo “pedaços significativos” no artigo é ambíguo.Eu pensei que a frase "use essas informações para a posição do bloco e apenas armazene o valor XOREILED SIGNIFICADO". significa armazenar os pedaços com todos os zeros à direita e à esquerda foram removidos porque "valor XOR significativo" é um valor sem zero à esquerda e à direita.Mas, de acordo com a implementação de referência, você apenas remove a mesma quantidade de zeros à esquerda e à direita do valor delta anterior;os bits significativos neste caso ainda podem conter alguns zeros à esquerda e à direita.

Então, para o exemplo da questão, devemos armazenar 0ff0 como bits significativos em vez de apenas ff.