Komprimierung

Dieses Dokument bezieht sich auf die folgende Methode: Update API (Version 4): threatListUpdates.fetch.

Komprimierung

Die Komprimierung ist eine wichtige Funktion der Safe Browsing APIs (v4). Durch die Komprimierung werden Bandbreitenanforderungen erheblich reduziert, was insbesondere, aber nicht ausschließlich, für Mobilgeräte relevant ist. Der Safe Browsing-Server unterstützt derzeit die Rice-Komprimierung. Weitere Komprimierungsmethoden werden möglicherweise in Zukunft hinzugefügt.

Die Komprimierung wird über das Feld supportedCompressions und CompressionType festgelegt. Clients sollten die Komprimierungstypen RICE und RAW verwenden. Safe Browsing verwendet den Typ COMPRESSION_TYPE_UNSPECIFIED, wenn der Komprimierungstyp nicht festgelegt ist (RAW-Komprimierung wird ersetzt).

Der Safe Browsing-Server verwendet außerdem die Standard-HTTP-Komprimierung, um Antworten unabhängig vom ausgewählten Komprimierungstyp weiter zu komprimieren, solange der Client den richtigen HTTP-Komprimierungs-Header festlegt (siehe den Wikipedia-Artikel HTTP-Komprimierung).

RICE-Komprimierung

Wie bereits erwähnt, unterstützt der Safe Browsing-Server derzeit die RICE-Komprimierung. Eine ausführliche Beschreibung der Golomb-RICE-Codierung finden Sie im Wikipedia-Artikel Golomb-Codierung.

Komprimierung/Dekomprimierung

Das RiceDeltaEncoding-Objekt stellt die Rice-Golomb-codierten Daten dar und wird zum Senden komprimierter Entfernungsindexe oder komprimierter 4-Byte-Hash-Präfixe verwendet. Hash-Präfixe, die länger als 4 Byte sind, werden nicht komprimiert und stattdessen im RAW-Format bereitgestellt.

Bei Entfernungsindexen wird die Liste der Indexe in aufsteigender Reihenfolge sortiert und dann mit RICE-Codierung Delta-codiert. Bei Hinzufügungen werden die 4-Byte-Hash-Präfixe als Little-Endian-Uint32s neu interpretiert, in aufsteigender Reihenfolge sortiert und dann mit RICE-Codierung Delta-codiert. Beachten Sie den Unterschied im Hash-Format zwischen RICE-Komprimierung und RAW: RAW-Hashes sind lexikografisch sortierte Byte, während RICE-Hashes Uint32s in aufsteigender Reihenfolge (nach Dekomprimierung) sortiert sind.

Das heißt, die Liste der Ganzzahlen [1, 5, 7, 13] wird als 1 (der erste Wert) und die Deltas [4, 2, 6] codiert.

Der erste Wert wird im Feld firstValue gespeichert und die Deltas werden mit einem Golomb-Rice-Encoder codiert. Der Rice-Parameter k (siehe unten) wird in „riceParameter“ gespeichert. Das Feld numEntries enthält die Anzahl der mit dem Rice-Encoder codierten Deltas (3 in unserem Beispiel oben, nicht 4). Das Feld encodedData enthält die tatsächlich codierten Deltas.

Encoder/Decoder

Im Rice-Encoder/-Decoder wird jedes Delta „n“ als „q“ und „r“ codiert, wobei „n“ = (q<<k) + r (oder „n“ = q * (2**k) + r) ist. „k“ ist eine Konstante und ein Parameter des Rice-Encoders/-Decoders. Die Werte für q und r werden im Bitstream mit unterschiedlichen Codierungsschemas codiert.

Der Quotient q wird in einer unären Codierung gefolgt von einer 0 codiert. Das bedeutet, dass 3 als 1110 codiert wird, 4 als 11110 und 7 als 11111110. Der Quotient q wird zuerst decodiert.

Der Rest r wird mit abgeschnittener Binärcodierung codiert. Nur die niedrigstwertigen k Bits von r werden aus dem Bitstream geschrieben (und daher gelesen). Der Rest r wird nach der Decodierung von q decodiert.

Bit-Encoder/-Decoder

Der Rice-Encoder verwendet einen Bit-Encoder/-Decoder, bei dem einzelne Bit an den Bit-Encoder angehängt werden können d. h. um einen Quotienten q zu kodieren, der nur zwei Bits lang sein kann.

Der Bit-Encoder ist eine Liste von (8-Bit-)Byte. Die Bits werden vom niedrigstwertigen Bit im ersten Byte bis zum höchstwertigen Bit im ersten Byte gesetzt. Wenn alle Bit eines Byte bereits gesetzt sind, wird ein neues Byte, das auf null initialisiert ist, an das Ende der Byte-Liste angehängt. Wenn das letzte Byte nicht vollständig verwendet wird, werden die höchstwertigen Bit auf null gesetzt. Beispiel:

Bit wurden hinzugefügt	BitEncoder nach dem Hinzufügen von Bit
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]