圧縮

圧縮について

圧縮は Web Risk の重要な機能です。圧縮により、帯域幅の要件が大幅に削減されます。これは特にモバイル デバイスに関連します。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]