Compactação

Sobre a compactação

A compactação é um recurso fundamental da Web Risk. A compactação reduz significativamente os requisitos de largura de banda, o que é particularmente relevante para dispositivos móveis. No momento, o servidor da Web Risk é compatível com a compactação de arroz. Mais métodos de compactação podem ser adicionados no futuro.

A compactação é definida usando o campo supportedCompressions e CompressionType. Os clientes devem usar os tipos de compactação RICE e RAW. A Web Risk usa o tipo COMPRESSION_TYPE_UNSPECIFIED quando o tipo de compactação não está definido (a compactação RAW será substituída).

O servidor da Web Risk também usará a compactação HTTP padrão para compactar ainda mais as respostas, independentemente do tipo de compactação selecionado, desde que o cliente defina o cabeçalho de compactação HTTP correto. Para saber mais, consulte o artigo da Wikipédia sobre compactação HTTP.

Compactação Rice

Conforme observado, o servidor da Web Risk é compatível atualmente com a compactação Rice. Para mais informações, consulte o artigo da Wikipédia Codificação Golomb.

Compactação/descompactação

O objeto RiceDeltaEncoding representa os dados com codificação Rice-Golomb e é usado para enviar índices de remoção compactados ou prefixos de hash compactados de 4 bytes. Prefixos de hash com mais de 4 bytes não serão compactados e serão exibidos no formato bruto.

Para índices de remoção, a lista de índices é classificada em ordem crescente e codificada em delta usando a codificação RICE. Para adições, os prefixos de hash de 4 bytes são interpretados novamente como uint32s pequenos, classificados em ordem crescente e codificados em delta usando a codificação RICE. Observe a diferença no formato de hash entre a compactação RICE e o RAW: os hashes brutos são bytes lexicograficamente classificados, enquanto os hashes RICE são uint32s classificados em ordem de envio (após a descompactação).

Ou seja, a lista de números inteiros [1, 5, 7, 13] será codificada como 1 (o primeiro valor) e os deltas [4, 2, 6].

O primeiro valor é armazenado no campo firstValue, e os deltas são codificados usando um codificador Golomb-Rice. O parâmetro k (veja abaixo) é armazenado em riceParameter. O campo numEntries contém o número de deltas codificados no codificador Rice (três no exemplo acima, não quatro). O campo encodedData contém os deltas codificados reais.

Codificador/decodificador

No codificador/decodificador 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/decodificador Rice. Os valores para q e r são codificados no fluxo de bits usando esquemas de codificação diferentes.

O quociente q é codificado em codificação unária seguida por um 0. Ou seja, 3 seriam codificados como 1110, 4 como 1110 e 7 como 11111110. O quociente q é decodificado primeiro.

O restante r é codificado usando a codificação binária truncada. Somente os bits k menos significativos de r são gravados (e, portanto, lidos) do fluxo de bits. O restante r é decodificado depois de decodificar q.

Codificador/decodificador de bits

O codificador Rice depende de um codificador/decodificador de bits em que bits únicos podem ser anexados 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 a partir do bit significativo mais baixo no primeiro byte para o bit mais significativo no primeiro byte. Se um byte tiver todos os bits já definidos, um novo byte, inicializado como zero, será anexado ao final da lista de bytes. Se o último byte não for totalmente usado, os bits significativos mais altos serão definidos como zero. Exemplo:

Bits adicionados	BitEncoder após adicionar bits
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]