Kompresi

Tentang kompresi

Kompresi adalah fitur utama Web Risk. Kompresi mengurangi persyaratan bandwidth secara signifikan, yang sangat relevan untuk perangkat seluler. Server Web Risk saat ini mendukung kompresi Rice. Metode kompresi lainnya mungkin akan ditambahkan di masa mendatang.

Kompresi ditetapkan menggunakan kolom supportedCompressions dan CompressionType. Klien harus menggunakan jenis kompresi RICE dan RAW. Web Risk menggunakan jenis COMPRESSION_TYPE_UNSPECIFIED jika jenis kompresi tidak ditetapkan (kompresi RAW akan diganti).

Server Web Risk juga akan menggunakan kompresi HTTP standar untuk mengompresi respons lebih lanjut, apa pun jenis kompresi yang dipilih, selama klien menetapkan header kompresi HTTP yang benar. Untuk mempelajari lebih lanjut, lihat artikel Wikipedia tentang kompresi HTTP.

Kompresi beras

Seperti yang telah disebutkan, server Web Risk saat ini mendukung kompresi Rice. Untuk informasi selengkapnya, lihat artikel Wikipedia Pengkodean Golomb.

Kompresi/dekompresi

Objek RiceDeltaEncoding mewakili data yang dienkode ke Rice-Golomb dan digunakan untuk mengirim indeks penghapusan terkompresi atau awalan hash 4 byte yang dikompresi. Awalan hash yang lebih dari 4 byte tidak akan dikompresi, dan akan disajikan dalam format mentah.

Untuk indeks penghapusan, daftar indeks diurutkan dalam urutan menaik, lalu delta dienkode menggunakan encoding RICE. Sebagai tambahan, awalan hash 4 byte diinterpretasikan ulang sebagai uint32 small-endian, diurutkan dalam urutan menaik, lalu dienkodekan delta menggunakan encoding RICE. Perhatikan perbedaan format hash antara kompresi RICE dan RAW: hash mentah adalah byte yang diurutkan secara leksikografis, sedangkan hash RICE diurutkan dalam urutan menaik (setelah dekompresi).

Artinya, daftar bilangan bulat [1, 5, 7, 13] akan dienkode sebagai 1 (nilai pertama) dan delta [4, 2, 6].

Nilai pertama disimpan di kolom firstValue dan delta dienkode menggunakan encoder Golomb-Rice. Parameter Rice k (lihat di bawah) disimpan di riceParameter. Kolom numEntries berisi jumlah delta yang dienkode dalam encoder Rice (3 dalam contoh di atas, bukan 4). Kolom encodedData berisi delta yang dienkode yang sebenarnya.

Encoder/decoder

Dalam encoder/decoder Rice, setiap n delta dienkode sebagai q dan r dengan n = (q<<k) + r (atau, n = q * (2**k) + r). k adalah konstanta dan parameter dari encoder/decoder Rice. Nilai untuk q dan r dienkode dalam aliran bit menggunakan skema encoding yang berbeda.

Hasil bagi q dienkode dalam coding unary yang diikuti dengan 0. Artinya, 3 akan dienkode sebagai 1110, 4 sebagai 11110, dan 7 sebagai 11111110. Hasil bagi q didekodekan terlebih dahulu.

r sisanya dienkode menggunakan encoding biner yang terpotong. Hanya k bit r paling tidak signifikan yang akan ditulis (dan dibaca) dari aliran bit. r sisanya didekode setelah q didekode.

Encoder/decoder bit

Encoder Rice bergantung pada bit encoder/decoder yang memungkinkan penambahan bit tunggal ke encoder bit; yaitu, untuk mengenkode q hasil bagi yang panjangnya hanya dua bit.

Encoder bit adalah daftar byte 8-bit. Bit ditetapkan dari bit signifikan terendah pada byte pertama ke bit signifikan tertinggi dalam byte pertama. Jika satu byte sudah menetapkan semua bitnya, byte baru yang diinisialisasi ke nol akan ditambahkan ke akhir daftar byte. Jika byte terakhir tidak sepenuhnya digunakan, bit signifikan tertingginya akan ditetapkan ke nol. Contoh:

Bit Ditambahkan BitEncoder Setelah Menambahkan Bit
[]
0 [00000000]
1 [00000010]
1 [00000110]
1,0,1 [00101110]
0,0,0 [00101110, 00000000]
1,1,0 [00101110, 00000110]