圧縮

このドキュメントは、Update API（v4）メソッド threatListUpdates.fetch に適用されます。

圧縮について

圧縮は Safe Browsing API（v4）の重要な機能です。圧縮を行うと、帯域幅の要件が大幅に軽減されます。これは特にモバイル デバイスにあてはまりますが、限定的ではありません。セーフ ブラウジング サーバーは現在、ライス圧縮をサポートしています。今後、他の圧縮方法が追加される可能性があります。

圧縮は、supportedCompressions フィールドと CompressionType を使用して設定します。クライアントは RICE 圧縮タイプと RAW 圧縮タイプを使用する必要があります。圧縮タイプが設定されていない場合、セーフ ブラウジングは COMPRESSION_TYPE_UNSPECIFIED タイプを使用します（RAW 圧縮に置き換えられます）。

セーフ ブラウジング サーバーでは、クライアントが正しい HTTP 圧縮ヘッダーを設定していれば、選択した圧縮タイプに関係なく、レスポンスをさらに圧縮するために標準の HTTP 圧縮も使用します（詳しくは Wikipedia の記事 HTTP 圧縮をご覧ください）。

Rice 圧縮

前述のように、セーフ ブラウジング サーバーは現在 Rice 圧縮をサポートしています（Golomb-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（以下を参照）は imagesParameter に格納されます。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 ビット）バイトのリストです。ビットは、第 1 バイトの最下位ビットから第 1 バイトの最上位ビットまでに設定されます。バイトにすべてのビットがすでに設定されている場合、新しいバイト（ゼロに初期化された）がバイトリストの末尾に付加されます。最後のバイトが完全に使用されていない場合、その最上位ビットは 0 に設定されます。例:

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