圧縮

圧縮について

圧縮はウェブリスクの重要な機能です。圧縮により帯域幅の要件が大幅に削減されます。これはモバイル デバイスに特に関連します。Web Risk サーバーは現在、Rice の圧縮をサポートしています。今後、さらに圧縮方法が追加される可能性があります。

圧縮は、supportedCompressions フィールドと CompressionType を使用して設定します。クライアントは RICE 圧縮タイプと RAW 圧縮タイプを使用する必要があります。圧縮タイプが設定されていない場合、Web Risk は COMPRESSION_TYPE_UNSPECIFIED タイプを使用します（RAW 圧縮が代用されます）。

また、Web Risk サーバーは、クライアントが正しい HTTP 圧縮ヘッダーを設定している限り、選択した圧縮タイプに関係なく、標準の HTTP 圧縮を使用してレスポンスをさらに圧縮します。詳細については、HTTP 圧縮に関する Wikipedia の記事をご覧ください。

Rice 圧縮

前述のとおり、Web Risk サーバーは現在、Rice 圧縮をサポートしています。詳しい情報については、Wikipedia の記事の Golomb コーディングをご覧ください。

圧縮 / 解凍

RiceDeltaEncoding オブジェクトは、Rice-Golomb でエンコードされたデータを表し、圧縮された削除インデックスまたは圧縮された 4 バイトのハッシュ プレフィックスを送信するために使用されます。4 バイトを超えるハッシュ プレフィックスは圧縮されず、未加工の形式で配信されます。

削除インデックスの場合、インデックスのリストは昇順で並べ替えられ、RICE エンコードを使用してデルタ エンコードされます。また、4 バイトのハッシュ プレフィックスは、リトル エンディアンの uint32 として再解釈され、昇順で並べ替えられ、RICE エンコードを使用してデルタ エンコードされます。RICE 圧縮と RAW のハッシュ形式は異なります。未加工のハッシュは辞書順で並べ替えられたバイトですが、RICE ハッシュは昇順（解凍後）で並べ替えられた uint32 です。

つまり、整数のリスト [1、5、7、13] は 1（最初の値）として、デルタは [4、2、6] としてエンコードされます。

最初の値は firstValue フィールドに格納され、デルタは Golomb-Rice エンコーダを使用してエンコードされます。Rice パラメータ k（下記参照）は、riceParameter に保存されます。numEntries フィールドには、Rice エンコーダでエンコードされたデルタの数が含まれます（上記の例では 4 ではなく 3）。encodedData フィールドには、実際にエンコードされたデルタが含まれます。

エンコーダ / デコーダ

Rice のエンコーダ / デコーダでは、すべてのデルタ n が q と r としてエンコードされます。ここでは、n = (q<<k) + r （または n = q * (2**k) + r）です。k は定数であり、Rice エンコーダ / デコーダのパラメータです。q と r の値は、異なるエンコード スキームを使用してビット ストリームでエンコードされます。

除算の商 q は、単項コーディングの後に 0 でエンコードされます。つまり、3 を 1110、4 を 11110、7 を 11111110 としてエンコードします。除算の商 q が最初にデコードされます。

残りの r は切り捨てられたバイナリ エンコードを使用してエンコードされます。r の最下位の k ビットのみがビット ストリームから書き込まれます（つまり、読み取られます）。残りの r は q をデコードした後にデコードされます。

ビット エンコーダ / デコーダ

Rice エンコーダは、ビット エンコーダに単一のビットを追加できるビット エンコーダ / デコーダに依存しています。つまり、2 ビット長の除算の商 q をエンコードします。

ビット エンコーダは 8 ビットバイトのリストです。ビットは最初のバイトの最下位ビットから最初のバイトの最上位ビットに設定されます。バイトのすべてのビットがすでに設定されている場合、ゼロに初期化された新しいバイトがバイトリストに追加されます。最後のバイトが完全に使用されていない場合、その最上位ビットはゼロに設定されます。例:

追加されたビット	ビットの追加後の BitEncoder
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]