Compression

À propos de la compression

La compression est une fonctionnalité clé de Web Risk. La compression réduit considérablement les besoins en bande passante, ce qui est particulièrement pertinent pour les appareils mobiles. Le serveur Web Risk est actuellement compatible avec la compression RICE. D'autres méthodes de compression pourront être ajoutées ultérieurement.

La compression est définie à l'aide des champs supportedCompressions et CompressionType. Les clients doivent utiliser les types de compression RICE et RAW. Web Risk utilise le type COMPRESSION_TYPE_UNSPECIFIED lorsque le type de compression n'est pas défini (la compression RAW sera remplacée).

Quel que soit le type de compression sélectionné, le serveur Web Risk utilise également la compression HTTP standard pour compresser davantage les réponses, à condition que le client définisse l'en-tête de compression HTTP approprié. Pour en savoir plus, consultez l'article Wikipédia sur la compression HTTP.

Compression RICE

Comme indiqué, le serveur Web Risk est actuellement compatible avec la compression RICE. Pour en savoir plus, consultez l'article Wikipédia sur le codage Golomb.

Compression/décompression

L'objet RiceDeltaEncoding représente les données encodées Rice-Golomb et permet d'envoyer des index de suppression compressés ou des préfixes de hachage compressés à 4 octets. Les préfixes de hachage de plus de 4 octets ne seront pas compressés et seront diffusés au format RAW.

Pour les index de suppression, la liste des index est triée par ordre croissant, puis codée en delta à l'aide de l'encodage RICE. Pour les ajouts, les préfixes de hachage de 4 octets sont réinterprétés en tant que little-endian uint32s, triés par ordre croissant, puis codés en delta à l'aide de l'encodage RICE. Notez la différence de format de hachage entre la compression RICE et la compression RAW : les hachages RAW comportent des octets triés de façon lexicographique, tandis que les hachages RICE contiennent des uint32s triés par ordre croissant (après décompression).

En d'autres termes, la liste des entiers [1, 5, 7, 13] sera encodée en tant que valeur 1 (la première valeur) et valeurs deltas [4, 2, 6].

La première valeur est stockée dans le champ firstValue et les valeurs deltas sont encodées à l'aide d'un encodeur Golomb-Rice. Le paramètre RICE k (voir ci-dessous) est stocké dans riceParameter. Le champ numEntries contient le nombre de valeurs deltas encodées dans l'encodeur RICE (3 dans notre exemple ci-dessus, et non 4). Le champ encodedData contient les valeurs deltas encodées réelles.

Encodeur/Décodeur

Dans l'encodeur/décodeur RICE, chaque valeur delta n est encodée en tant que q et r où n = (q<<k) + r (ou n = q * (2**k) + r). k est une constante et un paramètre de l'encodeur/décodeur RICE. Les valeurs pour q et r sont encodées dans le flux de bits à l'aide de différents schémas d'encodage.

Le quotient q est encodé à l'aide d'un codage unaire et suivi d'un 0. Par exemple, 3 sera encodé au format 1110, 4 au format 11110 et 7 au format 11111110. Le quotient q est d'abord décodé.

Le reste r est encodé à l'aide d'un encodage binaire tronqué. Seuls les bits k les moins significatifs de r sont écrits (et donc lus) dans le flux de bits. Le reste r est décodé après avoir décodé q.

Encodeur/Décodeur de bits

L'encodeur RICE s'appuie sur un encodeur/décodeur de bits où des bits uniques peuvent être ajoutés à l'encodeur de bits, c'est-à-dire pour encoder un quotient q qui ne peut comporter que deux bits.

L'encodeur de bits comprend une liste d'octets de 8 bits. Les bits sont définis du plus petit au plus grand bit significatif dans le premier octet. Si tous les bits d'un octet sont déjà définis, un nouvel octet initialisé sur zéro est ajouté à la fin de la liste d'octets. Si le dernier octet n'est pas entièrement utilisé, ses bits significatifs les plus élevés sont définis sur zéro. Exemple :

Bits ajoutés	Encodeur de bits après l'ajout de bits
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]