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. En la actualidad, el servidor de Web Risk es compatible con la compresión Rice. Es posible que se agreguen más métodos de compresión en el futuro.

La compresión se configura mediante 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 está configurado el tipo de compresión (se sustituirá la compresión RAW).

El servidor de Web Risk también usará la compresión HTTP estándar para comprimir aún más las respuestas, sin importar el 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 ya se mencionó, el servidor de Web Risk actualmente admite la compresión Rice. Para obtener más información, consulta el artículo de Wikipedia sobre codificación 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 los 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 o decodificador Rice, cada n delta 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 o decodificador Rice. Los valores para q y r se codifican en la transmisión de bits con diferentes esquemas de codificación.

El cociente q se codifica en una 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 r restante se codifica con la codificación binaria truncada. Solo los bits k menos significativos de r se escriben (y, por lo tanto, se leen) desde el flujo de bits. El r restante 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 más alto en el primer byte. Si un byte ya tiene todos sus bits configurados, se adjunta un byte nuevo, inicializado en cero al final de la lista de bytes. Si el último byte no se usa por completo, sus bits más significativos se establecen en cero. Ejemplo:

Partes agregadas	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]