Compresión

Información acerca de la compresión

La compresión es una función clave de Web Risk. La compresión reduce significativamente los requisitos de ancho de banda, lo que es particularmente relevante para los dispositivos móviles. Actualmente, el servidor de Web Risk admite la compresión Rice. Es posible que se agreguen más métodos de compresión en el futuro.

La compresión se establece con el campo supportedCompressions y CompressionType. Los clientes deben usar los tipos de compresión RICE y RAW. Web Risk usa el tipo COMPRESSION_TYPE_UNSPECIFIED cuando no se establece el tipo de compresión (se sustituirá la compresión sin procesar).

El servidor de Web Risk también usará la compresión HTTP estándar para comprimir aún más las respuestas, independientemente del tipo de compresión seleccionado, siempre que el cliente establezca el encabezado de compresión HTTP correcto. Para obtener más información, consulta el artículo de Wikipedia sobre compresión HTTP.

Compresión Rice

Como se señaló, el servidor de Web Risk actualmente admite la compresión Rice. Para obtener más información, consulta el artículo de Wikipedia Codificación de Golomb.

Compresión/descompresión

El objeto RiceDeltaEncoding representa los datos codificados de Rice-Golomb y se usa para enviar índices de eliminación comprimidos o prefijos de hash de 4 bytes comprimidos. Los prefijos de hash de más de 4 bytes no se comprimirán y, en su lugar, se entregarán en formato sin procesar.

Para los índices de eliminación, la lista de índices se ordena de forma ascendente y, luego, se codifica con delta mediante la codificación RICE. Para las adiciones, los prefijos de hash de 4 bytes se vuelven a interpretar como "uint32s" poco endian, se ordenan de forma ascendente y, luego, se codifican con delta mediante la codificación RICE. Ten en cuenta la diferencia en el formato de hash entre la compresión RICE y RAW: los hash sin procesar son bytes ordenados de manera lexicográfica, mientras que los hash de RICE son uint32s ordenados de manera ascendente (después de la descompresión).

Es decir, la lista de números enteros [1, 5, 7, 13] se codificará como 1 (el primer valor) y las deltas [4, 2, 6].

El primer valor se almacena en el campo firstValue y los deltas se codifican con un codificador de golomb-rice. El parámetro de Rice k (ver a continuación) se almacena en riceParameter. El campo numEntries contiene la cantidad de deltas que se codificó en el codificador de Rice (3 en nuestro ejemplo anterior, no 4). El campo encodedData contiene los deltas que se codificaron reales.

Codificador/decodificador

En el codificador/decodificador de Rice, cada delta n se codifica como q y r, donde n = (q<<k) + r (o n = q * (2**k) + r). k es una constante y un parámetro del codificador/decodificador de Rice. Los valores de q y r se codifican en el flujo de bits con diferentes esquemas de codificación.

El cociente q se codifica en codificación unaria seguida de un 0. Es decir, 3 se codificaría como 1110, 4 como 11110 y 7 como 11111110. Primero, se decodifica el cociente q.

El resto r se codifica con codificación binaria truncada. Solo los k bits menos significativos de r se escriben (y, por lo tanto, se leen) desde el flujo de bits. El resto r se decodifica después de decodificar q.

Codificador/decodificador de bits

El codificador de Rice se basa en un codificador/decodificador de bits en el que se pueden agregar bits individuales al codificador de bits. es decir, codificar un cociente q que podría tener solo dos bits.

El codificador de bits es una lista de bytes de 8 bits. Los bits se establecen desde el bit significativo más bajo en el primer byte hasta el bit significativo más alto en el primer byte. Si un byte ya tiene todos sus bits establecidos, se agrega un byte nuevo, inicializado en cero, al final de la lista de bytes. Si el último byte no se usa por completo, sus bits significativos más altos se establecen en cero. Ejemplo:

Bits agregados	BitEncoder después de agregar bits
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]