Compressão

Acerca da compressão

A compressão é uma funcionalidade essencial do Web Risk. A compressão reduz significativamente os requisitos de largura de banda, o que é particularmente relevante para dispositivos móveis. Atualmente, o servidor do Web Risk suporta a compressão Rice. Podem ser adicionados mais métodos de compressão no futuro.

A compressão é definida através do campo supportedCompressions e CompressionType. Os clientes devem usar os tipos de compressão RICE e RAW. O Web Risk usa o tipo COMPRESSION_TYPE_UNSPECIFIED quando o tipo de compressão não está definido (a compressão RAW é substituída).

O servidor do Web Risk também usa a compressão HTTP padrão para comprimir ainda mais as respostas, independentemente do tipo de compressão selecionado, desde que o cliente defina o cabeçalho de compressão HTTP correto. Para saber mais, consulte o artigo da Wikipedia sobre a compressão HTTP.

Compressão de arroz

Conforme indicado, o servidor do Web Risk suporta atualmente a compressão Rice. Para mais informações, consulte o artigo da Wikipédia Codificação de Golomb.

Compressão/descompressão

O objeto RiceDeltaEncoding representa os dados codificados por Rice-Golomb e é usado para enviar índices de remoção comprimidos ou prefixos de hash de 4 bytes comprimidos. Os prefixos de hash com mais de 4 bytes não são comprimidos e são publicados no formato não processado.

Para os índices de remoção, a lista de índices é ordenada por ordem ascendente e, em seguida, é codificada por delta através da codificação RICE. Para adições, os prefixos de hash de 4 bytes são re-interpretados como uint32s little-endian, ordenados por ordem ascendente e, em seguida, codificados por delta através da codificação RICE. Tenha em atenção a diferença no formato de hash entre a compressão RICE e RAW: os hashes RAW são bytes ordenados lexicograficamente, enquanto os hashes RICE são uint32s ordenados por ordem ascendente (após a descompressão).

Ou seja, a lista de números inteiros [1, 5, 7, 13] é codificada como 1 (o primeiro valor) e as diferenças [4, 2, 6].

O primeiro valor é armazenado no campo firstValue e as diferenças são codificadas através de um codificador Golomb-Rice. O parâmetro Rice k (veja abaixo) é armazenado em riceParameter. O campo numEntries contém o número de deltas codificados no codificador Rice (3 no nosso exemplo acima, não 4). O campo encodedData contém os deltas codificados reais.

Codificador/descodificador

No codificador/descodificador Rice, cada delta n é codificado como q e r, onde n = (q<<k) + r (ou n = q * (2**k) + r). k é uma constante e um parâmetro do codificador/descodificador Rice. Os valores de q e r são codificados no fluxo de bits através de esquemas de codificação diferentes.

O quociente q é codificado em codificação unária seguido de um 0. Ou seja, 3 seria codificado como 1110, 4 como 11110 e 7 como 11111110. O quociente q é descodificado primeiro.

O resto r é codificado através da codificação binária truncada. Apenas os k bits menos significativos de r são escritos (e, por conseguinte, lidos) a partir do fluxo de bits. O resto r é descodificado depois de ter descodificado q.

Codificador/descodificador de bits

O codificador Rice baseia-se num codificador/descodificador de bits em que é possível anexar bits únicos ao codificador de bits, ou seja, para codificar um quociente q que pode ter apenas dois bits.

O codificador de bits é uma lista de bytes de 8 bits. Os bits são definidos do bit menos significativo no primeiro byte para o bit mais significativo no primeiro byte. Se um byte tiver todos os bits já definidos, é anexado um novo byte, inicializado como zero, ao final da lista de bytes. Se o último byte não for totalmente usado, os respetivos bits mais significativos são definidos como zero. Exemplo:

Bits adicionados	BitEncoder After Adding Bits
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]