¿Cómo funciona la descompresión del valor para el gorila de Facebook en el caso donde no se almacena el recuento de ceroes?

Question

Me refiero a este documento: http://www.vldb. org / pvldb / vol8 / p1816-Teller.pdf

Mi pregunta es respecto a la Sección 4.1.2 Donde dice:

Cuando Xor no tiene cero, calcule el número de ceros líderes y finales en el XOR, STARTE BIT '1' SIGUIENTE ya sea a) o b):

(a) (Bit de control '0') Si el bloque de bits significativos cae dentro del bloque de bits significativos anteriores, es decir, hay al menos tantos ceros principales y Como muchos ceros que se arrastran, al igual que con el valor anterior, use esa información para la posición de bloque y simplemente almacene el valor Xored significativo.

Cuando descomprimen, ¿cómo sabemos si deberíamos agregar ceros principales o zeros de cola? Por ejemplo, digamos que tenemos los siguientes 48 bits números:

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

y

A xor B = 0x000 ffff 00000

B xor C = 0x000 0ff0 00000

Si seguimos el algoritmo de compresión para A xor B, almacenaremos la cantidad de ceroes principales, que es 12, así como los bits significativos ffff.

ahora, para B xor C porque "hay al menos tantos ceros principales y tantos ceros que se arrastran, al igual que el valor anterior", por lo que solo almacenamos los bits significativos ff. Cuando quiero decodificar ff, base en bits comprimidos anteriores, sé que tengo al menos 12 ceros principales y 20 ceros de cola, pero todavía necesito completar 8 ceros; ¿Debo hacer ff00 o 00ff u otra combinación?

Answer 1

Encontré mi respuesta después de leer la implementación de referencia: https : //github.com/facebookarchive/berneai/blob/92784EC6E22572F28500C76B66927600C76B669276007635C875/BERINGEI/LIB/TIMESERIESSESTREAM.CPP

El uso del término "bits significativos" en el papel es ambiguo. Pensé que la oración "usa esa información para la posición del bloque y solo almacena el valor Xored significativo". significa almacenar los bits con todos los ceros finales y los líderes despojados porque "Valor Xored significativo" es un valor sin un cero líder y final. Pero, de acuerdo con la implementación de referencia, simplemente quita la misma cantidad de ceros principales y al final como delta del valor anterior; Los bits significativos en este caso todavía pueden contener algunos ceros principales y al final.

Entonces, para el ejemplo en la pregunta, deberíamos almacenar 0ff0 como bits significativos en lugar de solo ff.