¿Cómo funciona la descompresión del valor para el gorila de Facebook en el caso donde no se almacena el recuento de ceroes?
-
29-09-2020 - |
Pregunta
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?
Solución
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
.