Komprimierung

Die Komprimierung ist eine wichtige Funktion von Web Risk. Durch die Komprimierung werden Bandbreitenanforderungen erheblich reduziert, was insbesondere für Mobilgeräte relevant ist. Der Web Risk-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. Web Risk verwendet den Typ COMPRESSION_TYPE_UNSPECIFIED, wenn der Komprimierungstyp nicht festgelegt ist (RAW-Komprimierung wird ersetzt).

Der Web Risk-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. Weitere Informationen finden Sie im Wikipedia-Artikel zur HTTP-Komprimierung.

RICE-Komprimierung

Wie bereits erwähnt, unterstützt der Web Risk-Server derzeit die RICE-Komprimierung. Weitere Informationen 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-Bit 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. Bit 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]