Compresió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 especialmente importante en los dispositivos móviles. Actualmente, el servidor de Web Risk admite la compresión Rice. Es posible que se añadan más métodos de compresión en el futuro.

La compresión se define mediante los campos 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 ha definido el tipo de compresión (se sustituirá por 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, independientemente del tipo de compresión seleccionado, siempre que el cliente defina el encabezado de compresión HTTP correcto. Para obtener más información, consulta el artículo de Wikipedia sobre la compresión HTTP.

Compresión de arroz

Como se ha indicado, el servidor de Web Risk admite la compresión Rice. Para obtener más información, consulta el artículo de Wikipedia sobre la codificación Golomb.

Compresión/descompresión

El objeto RiceDeltaEncoding representa los datos codificados con 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 se servirán en formato sin procesar.

En el caso de los índices de eliminación, la lista de índices se ordena de forma ascendente y, a continuación, se codifica con delta mediante la codificación RICE. En el caso de las adiciones, los prefijos hash de 4 bytes se reinterpretan como uint32s little-endian, se ordenan de forma ascendente y, a continuación, se codifican con delta mediante la codificación RICE. Ten en cuenta la diferencia en el formato del hash entre la compresión RICE y RAW: los hashes RAW son bytes ordenados lexicográficamente, mientras que los hashes RICE son uint32s ordenados de forma 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 mediante un codificador Golomb-Rice. El parámetro Rice k (consulta la información más abajo) se almacena en riceParameter. El campo numEntries contiene el número de deltas codificados en el codificador Rice (3 en el ejemplo anterior, no 4). El campo encodedData contiene los deltas codificados.

Codificador/decodificador

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

El cociente q se codifica en código unario seguido 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 mediante codificación binaria truncada. Solo se escriben (y, por lo tanto, se leen) los k bits menos significativos de r del flujo de bits. El resto r se decodifica después de decodificar q.

Codificador o decodificador de bits

El codificador Rice se basa en un codificador o decodificador de bits en el que se pueden añadir bits individuales al codificador de bits. Es decir, para codificar un cociente q que solo puede tener dos bits.

El codificador de bits es una lista de bytes de 8 bits. Los bits se definen desde el bit menos significativo del primer byte hasta el bit más significativo del primer byte. Si un byte tiene todos sus bits ya definidos, se añade un nuevo byte, 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 definen como cero. Ejemplo:

Bits añadidos	BitEncoder After Adding Bits
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1.0.1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]