Compressione

Informazioni sulla compressione

La compressione è una funzionalità chiave di Web Risk. La compressione riduce notevolmente i requisiti di larghezza di banda, aspetto particolarmente pertinente per i dispositivi mobili. Al momento il server Web Risk supporta la compressione Rice. In futuro potrebbero essere aggiunti altri metodi di compressione.

La compressione viene impostata utilizzando il campo supportedCompressions e CompressionType. I client devono utilizzare i tipi di compressione RICE e RAW. Web Risk utilizza il tipo COMPRESSION_TYPE_UNSPECIFIED quando il tipo di compressione non è impostato (verrà sostituita la compressione RAW).

Il server Web Risk utilizzerà anche la compressione HTTP standard per comprimere ulteriormente le risposte, indipendentemente dal tipo di compressione selezionato, a condizione che il client imposti l'intestazione di compressione HTTP corretta. Per scoprire di più, consulta l'articolo di Wikipedia sulla compressione HTTP.

Compressione del riso

Come indicato, il server Web Risk attualmente supporta la compressione Rice. Per ulteriori informazioni, consulta l'articolo di Wikipedia Codifica Golomb.

Compressione/decompressione

L'oggetto RiceDeltaEncoding rappresenta i dati codificati Rice-Golomb e viene utilizzato per inviare indici di rimozione compressi o prefissi hash di 4 byte compressi. I prefissi degli hash più lunghi di 4 byte non verranno compressi e verranno pubblicati in formato non elaborato.

Per gli indici di rimozione, l'elenco degli indici viene ordinato in ordine crescente e poi codificato in delta utilizzando la codifica RICE. Per le aggiunte, i prefissi di hash di 4 byte vengono reinterpretati come uint32 little-endian, ordinati in ordine crescente e poi codificati delta utilizzando la codifica RICE. Tieni presente la differenza nel formato dell'hash tra la compressione RICE e RAW: gli hash non elaborati sono byte ordinati in ordine alfabetico, mentre gli hash RICE sono uint32 ordinati in ordine crescente (dopo la decompressione).

In altre parole, l'elenco di numeri interi [1, 5, 7, 13] verrà codificato come 1 (il primo valore) e i delta [4, 2, 6].

Il primo valore viene memorizzato nel campo firstValue e le differenze vengono codificate utilizzando un codificatore Golomb-Rice. Il parametro Rice k (vedi di seguito) è memorizzato in riceParameter. Il campo numEntries contiene il numero di delta codificati nell'encoder Rice (3 nel nostro esempio precedente, non 4). Il campo encodedData contiene i delta codificati effettivi.

Encoder/decoder

Nell'encoder/decoder di Rice ogni delta n viene codificato come q e r dove n = (q<<k) + r (o n = q * (2**k) + r). k è una costante e un parametro dell'encoder/decoder di Rice. I valori di q e r vengono codificati nel flusso di bit utilizzando diversi schemi di codifica.

Il quoziente q è codificato in codifica unaria seguita da uno 0. In altre parole, 3 verrebbe codificato come 1110, 4 come 11110 e 7 come 11111110. Il quoziente q viene decodificato per primo.

Il resto r viene codificato utilizzando la codifica binaria troncata. Solo i k bit meno significativi di r vengono scritti (e quindi letti) dallo stream di bit. Il resto r viene decodificato dopo aver decodificato q.

Encoder/decoder di bit

Il codificatore Rice si basa su un codificatore/decodificatore di bit in cui i singoli bit possono essere aggiunti al codificatore di bit, ovvero per codificare un quoziente q che potrebbe essere di soli due bit.

L'encoder di bit è un elenco di byte di 8 bit. I bit vengono impostati dal bit significativo più basso nel primo byte al bit significativo più alto nel primo byte. Se un byte ha già tutti i bit impostati, un nuovo byte, inizializzato a zero, viene aggiunto alla fine dell'elenco di byte. Se l'ultimo byte non viene utilizzato completamente, i suoi bit più significativi vengono impostati su zero. Esempio:

Bit aggiunti BitEncoder dopo l'aggiunta di bit
[]
0 [00000000]
1 [00000010]
1 [00000110]
1,0,1 [00101110]
0,0,0 [00101110, 00000000]
1,1,0 [00101110, 00000110]