Как работает распаковка значений для Gorilla Facebook в случае, когда количество ведущих нулей не сохраняется

Question

Я имею в виду вот эту бумагу: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

Мой вопрос касается раздела 4.1.2, где сказано:

Когда XOR не нулевой, вычислите количество ведущих и следственных нулей в XOR, храните бит «1», а затем а) ​​или б):

(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». означает хранить кусочки с все конечные и ведущие нули удалены, поскольку «значимое значение, обработанное исключающим ИЛИ» — это значение без начального и конечного нуля.Но, согласно эталонной реализации, вы просто удаляете такое же количество начальных и конечных нулей, что и дельта предыдущего значения;значимые биты в этом случае все еще могут содержать некоторые ведущие и конечные нули.

Итак, для примера в вопросе мы должны сохранить 0ff0 как значимые биты, а не просто ff.