Komprimierung

Dieses Dokument gilt für die Update API (Version 4): threatListUpdates.fetch.

Komprimierung

Die Komprimierung ist eine Hauptfunktion der Safe Browsing APIs (v4). Durch die Komprimierung wird der Bandbreitenbedarf 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. Stattdessen wird die RAW-Komprimierung verwendet.

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

RICE-Komprimierung

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

Komprimierung/Dekomprimierung

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

Für die Entfernungsindizes wird die Indexliste in aufsteigender Reihenfolge sortiert und dann mit RICE-Codierung deltacodiert. Bei Ergänzungen werden die 4-Byte-Hash-Präfixe als Little-Endian-Uint32s neu interpretiert, in aufsteigender Reihenfolge sortiert und dann mit RICE-Codierung deltacodiert. Beachten Sie den Unterschied im Hash-Format zwischen der RICE-Komprimierung und dem RAW-Format: Roh-Hashes sind lexikografisch sortierte Byte, während Rice-Hashes uint32-Hashes sind, die in aufsteigender Reihenfolge (nach der 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 Reis-Parameter k (siehe unten) wird in RiceParameter gespeichert. Das Feld numEntries enthält die Anzahl der im Rice-Encoder codierten Deltas (in unserem Beispiel oben drei, 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) eine Konstante und ein Parameter des Rice-Encoders/-Decoders ist. Die Werte für q und r werden im Bitstream mit verschiedenen Codierungsschemata codiert.

Der Quotient q wird unär codiert, gefolgt von einer 0. Das heißt, 3 wird als 1110, 4 als 11110 und 7 als 11111110 codiert. Der Quotient q wird zuerst decodiert.

Der Rest r wird mit abgeschnittenen binären Codierungen codiert. Nur die am wenigsten wichtigen k Bit von r werden aus dem Bitstream geschrieben (und somit gelesen). Der Rest r wird decodiert, nachdem q decodiert wurde.

Bit-Encoder/-Decoder

Der Rice-Encoder basiert auf einem Bit-Encoder/-Decoder, bei dem einzelne Bits an den Bit-Encoder angehängt werden können, d. h. zum Codieren eines Quotienten q, der nur zwei Bit lang sein kann.

Der Bit-Encoder ist eine Liste von (8-Bit-) Byte. Bits werden vom niedrigstwertigen Bit im ersten Byte bis zum höchsten signifikanten Bit im ersten Byte festgelegt. Wenn für ein Byte bereits alle Bits gesetzt sind, wird ein neues (auf null initialisiertes) Byte an das Ende der Byteliste angehängt. Wenn das letzte Byte nicht vollständig genutzt wird, werden die Bits mit der höchsten Signifikanz 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]