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