Compresión

Información sobre la compresión

La compresión es una característica 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. El servidor de Web Risk admite actualmente la compresión de arroz. Es posible que se agreguen más métodos de compresión en el futuro.

La compresión se establece 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 se establece el tipo de compresión (se reemplazará la compresión RAW).

El servidor de Web Risk también utilizará 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 se mencionó, el servidor de Web Risk admite actualmente la compresión de arroz. Para obtener más información, consulta el artículo de Wikipedia sobre 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 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/decodificador de 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/decodificador de arroz. Los valores de q y r se codifican en el flujo de bits mediante diferentes esquemas de codificación.

El cociente q está codificado en codificación unaria seguida de 0. Es decir, 3 se codificaría como 1110, 4 como 11110 y 7 como 11111110. El cociente q se decodifica primero.

El r restante se codifica mediante una codificación binaria truncada. Solo se escriben (y, por lo tanto, se leen) los bits k menos significativos de r desde la transmisión de bits. El r restante se decodifica después de que se decodifica q.

Codificador o 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 más bajo en el primer byte hasta el más significativo en el primer byte. Si un byte ya tiene todos sus bits configurados, 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]