Artikel ini mungkin menarik bagi mereka yang terlibat dalam kompresi data atau ingin menulis pengarsipan mereka sendiri.
Artikel ini ditulis terutama pada bahan
blog , yang dikelola oleh Fabian Giesen.
Pendahuluan
Metode pengkodean entropi rANS (
r ange + ANS) adalah saudara kandung dari algoritma FSE, yang saya
tulis sebelumnya . Singkatan ANS berarti
Sistem Angka Asimetris , dan rentang kata dalam namanya mengisyaratkan kesamaan metode ini dengan
pengkodean interval . Penulis rans adalah
Yarek Duda .
Metode RANS memungkinkan Anda mencapai kompresi yang hampir optimal pada kecepatan yang sangat tinggi. Dalam rANS ini tidak lebih buruk daripada FSE, yang tidak mengejutkan: kedua algoritma didasarkan pada landasan teori umum. Namun, algoritma rANS jauh lebih mudah diimplementasikan daripada FSE.
Pertama, akan ada bagian "teoretis" yang panjang, dan kemudian kita akan mencoba menulis pengarsipan sederhana.
Deskripsi Metode
Pengoperasian algoritma ditentukan oleh rumus sederhana berikut:
Pengkodean: C(s,x): x := (x / Fs) * M + Bs + (x % Fs)Decoding: D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - BsMari kita analisa secara detail.
Fungsi pengkodean
C (s, x) menerima karakter
s untuk dikodekan (biarkan bilangan bulat) dan keadaan saat ini dari enkoder
x (juga bilangan bulat).
F s - frekuensi simbol
s . Pembagian oleh Fs di atas adalah bilangan bulat.
M adalah jumlah frekuensi semua simbol alfabet (
M = Ξ£
F s ).
Dalam s , awal interval sesuai dengan karakter yang dikodekan (pada gambar di bawah).
x %
Fs adalah sisa dari pembagian
x oleh
F s .
Prinsip operasi adalah sama seperti dalam
pengkodean aritmatika : kita mengambil segmen
[ 0,
M) dan membaginya menjadi bagian-bagian sehingga setiap karakter sesuai dengan interval yang sama ukurannya dengan frekuensi karakter
Fs . Terjadinya nilai
x% M dalam interval apa pun menunjukkan pengkodean simbol yang sesuai.
Di awal pengkodean, inisialisasi
x dengan nilai yang sesuai sewenang-wenang, dan kemudian hitung fungsi
C (s, x) untuk semua karakter yang disandikan secara berurutan.
Setiap perhitungan fungsi
C (s, x) meningkatkan nilai
x . Ketika terlalu besar, Anda harus membuang data dalam output:
while (x >= x_max) { writeToStream(x % b);
Langkah ini disebut
renormalisasi . Setelah itu, Anda dapat melanjutkan pengkodean.
Di atas kode, konstanta baru muncul:
x_max dan
b . Secara teori, angka
M ,
b, dan
x_max terkait oleh beberapa hubungan, tetapi dalam praktiknya paling efektif untuk menggunakan nilai berikut jika negara uint32 digunakan untuk negara
x :
M = 2 ^
k , di mana
k <= 16
b = 2 ^ 16 (setengah ukuran uint32)
Pilihan
M = 2 ^
k disebabkan oleh fakta bahwa ada pembagian oleh
M dalam fungsi dekode, sehingga pembagian dengan sisanya dapat diganti dengan operasi bitwise.
Nilai
k dipilih dari pertimbangan berikut: semakin besar, semakin tinggi akurasi
Fs dan semakin efisien kompresi. Dalam hal ini, beberapa overhead untuk menyimpan tabel frekuensi harus diperhitungkan, sehingga tidak selalu layak menggunakan nilai maksimum
k .
Nilai
x_max harus sedemikian rupa sehingga tidak terjadi overflow. Berdasarkan fungsi enkode, kita mendapatkan
x <
uint32_max *
Fs /
M atau cara yang sedikit berbeda:
x_max <= (
b *
L ) *
Fs /
M , di mana
L <=
uint32_max /
b . Dalam kode nyata, kondisi tersebut mengambil bentuk x / b> = L / M * Fs untuk menghindari kelebihan dalam perhitungan.
Nilai
b = 2 ^ 16 (setengah ukuran uint32) dipilih sedemikian rupa sehingga jika
x melebihi
x_max , maka satu pembagian dengan
b cukup untuk terus bekerja. Akibatnya,
while akan berakhir setelah iterasi pertama, yang berarti dapat diganti dengan
if sederhana.
Akibatnya, fungsi enkode mengambil bentuk berikut:
typedef uint32_t RansState; constexpr uint32_t RANS_L = 1u << 16; constexpr uint32_t k = 10;
Di akhir pengkodean, Anda harus menyimpan nilai
x , karena decoding akan dimulai dari itu. Dan ya, kita akan memecahkan kode dari akhir ke awal, yaitu, dari karakter yang terakhir disandikan ke yang pertama. (Artikel tentang
FSE menjelaskan hal ini secara cukup rinci.)
Saya ingin sedikit lebih memikirkan bagaimana rumus encoding bekerja.
x := (x / Fs) * M + Bs + (x % Fs)
Setelah komputasi (
x / Fs) * M , variabel
x berisi
k bit paling signifikan (ingat bahwa
M = 2 ^
k ). Menambahkan
+ Bs + (x % Fs) pada dasarnya menulis ke bit-bit ini nilai tertentu dari
interval karakter
s , karena
Bs adalah awal dari interval, dan (x% Fs) adalah angka dalam interval ini (ukuran intervalnya adalah Fs). Jadi, ketika decoding, kita dapat menentukan karakter yang dikodekan oleh interval di mana ia jatuh (x% M).
DecodingMari kita beralih ke fungsi decoding.
D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs
Seperti yang sudah kita pahami di atas, karakter yang diinginkan ditentukan oleh sisa divisi
x %
M. Dalam interval berapa nilai (x% M) jatuh, karakter seperti itu dikodekan.
Sebelumnya, kami secara khusus mendefinisikan M = 2 ^ k untuk menyederhanakan fungsi decoding. Itu berakhir seperti ini:
uint32_t RansDecode(RansState& x, RansInBuf& in) { assert(x >= RANS_L);
Decoding dimulai dengan
x yang sama yang diperoleh pada akhir pengkodean. Untuk melakukan ini, itu harus disimpan bersama dengan data yang disandikan.
Pada akhir decoding, keadaan decoder
x harus persis sama dengan encoding. Secara umum, pada setiap langkah
x harus persis sama seperti pada langkah pengkodean yang sesuai. Fakta ini sangat membantu ketika melakukan debugging.
Seperti yang Anda lihat, decoding bekerja lebih cepat daripada encoding, karena tidak ada operasi pembagian.
Momen paling sulit dalam fungsi decoding adalah metode penentuan interval yang nilainya turun (x% M).
Metode termudah dan tercepat adalah dengan menggunakan tabel
sym [] , ukuran
M. Dalam hal ini, kita mendapatkan tabel dengan ukuran yang sama seperti pada algoritma FSE, dengan perbedaan bahwa dalam rANS tabel tidak βtercampurβ, karakternya teratur, dan tabel seperti itu jauh lebih mudah untuk dibuat.
Kelemahan utama dari pendekatan ini adalah ukuran tabel
sym , yang tumbuh secara eksponensial dengan meningkatnya
k .
Metode Alias
Metode alias diciptakan untuk lebih efisien menentukan hit dalam suatu interval. Metode ini memungkinkan Anda untuk dengan cepat menentukan interval yang diinginkan menggunakan tabel kecil - dengan jumlah karakter dalam alfabet.
Penjelasan panjang dan panjang dapat ditemukan di sini:
Darts, Dice and Coins . Saya akan menjelaskan esensi metode ini secara singkat: kami mengambil sepotong interval terpanjang dan melampirkannya pada interval terpendek sehingga ukuran totalnya persis
M /
N (di mana
N adalah jumlah karakter dalam alfabet). Ternyata jika Anda melakukan ini secara berurutan, Anda akan selalu berakhir dengan
N pasang ukuran
M /
N.Secara alami,
M harus dapat dibagi oleh
N. Dan jika kita ingat bahwa kita memiliki
M = 2 ^
k , maka ukuran alfabet ternyata juga menjadi kekuatan dua. Ini bukan masalah, karena Anda selalu dapat menambah alfabet ke ukuran yang diinginkan dengan karakter yang tidak digunakan dengan frekuensi nol.
Fakta bahwa interval karakter dibagi menjadi beberapa bagian menyulitkan prosedur pengkodean sedikit, tetapi tidak banyak. Jika Anda mengingat FSE, interval yang ada umumnya tersebar di seluruh rentang, seolah-olah mixer gila bekerja pada mereka, dan tidak ada yang berhasil =)
Menentukan interval yang diinginkan tidak sulit: bagi
x dengan
N , dan jatuh ke dalam salah satu pasangan. Selanjutnya, kami membandingkan sisa pembagian
x% N dengan batas antara segmen dalam pasangan dan jatuh dalam satu interval atau dalam yang lain.
Kami mencoba dalam praktik
Kami akan menggunakan kode
contoh yang sudah jadi .
Kami mengambil data untuk kompresi dari file:
size_t in_size; uint8_t* in_bytes = read_file("book1", &in_size);
1. Pertama, Anda perlu memutuskan
struktur data .
Kami menggunakan opsi paling sederhana: kami akan menyandikan satu byte menggunakan alfabet [0 ... 255].
2. Langkah selanjutnya adalah menentukan
frekuensi karakter alfabet:
(fungsi
stats.count_freqs )
for (size_t i = 0; i < in_size; i++) { freqs[in_bytes[i]]++; }
3. Jadi, kita memiliki frekuensi simbol, tetapi sekarang mereka perlu
dinormalisasi , yaitu dikurangi secara proporsional (atau meningkat) sehingga secara total kita mendapatkan M = 2 ^ k. Sepertinya ini bukan tugas yang sederhana, jadi kami menggunakan fungsi yang sudah jadi:
stats.normalize_freqs(...);
Omong-omong, Anda perlu menentukan nilai
k . Karena alfabet kami terdiri dari 256 karakter,
k kurang dari 8 tidak boleh diambil. Pertama, ambil maksimum - 16, dan kemudian coba nilai lainnya.
4. Bangun
tabel alias :
stats.make_alias_table();
5. Kami mengkodekan
dari akhir , lalu mendekode dalam urutan normal.
RansState rans;
Selanjutnya, contoh dengan referensi menerjemahkan data terkompresi menggunakan statistik siap pakai. Dalam kehidupan nyata, untuk decoding, Anda perlu menyimpan tabel frekuensi (statistik) bersama dengan data terkompresi. Dalam kasus yang paling sederhana, Anda harus menghabiskan bit N * k untuk itu.
Seperti yang dijanjikan di atas, mari kita lihat hasil kompresi untuk berbagai nilai k (dalam kode ini
prob_bits ), dengan mempertimbangkan peningkatan ukuran karena pencatatan tabel frekuensi:
(
Ukuran file book1 asli: 768771)
k = 16: 435059 + 512 = 435571 byte
k =
15 : 435078 + 480 =
435558 byte
k = 14: 435113 + 448 = 435561 byte
k = 13: 435239 + 416 = 435655 byte
k = 12: 435603 + 384 = 435987 byte
k = 11: 436530 + 352 = 436882 byte
k = 10: 440895 + 320 = 441215 byte
k = 9: 453418 + 288 = 453706 byte
k = 8: 473126 + 256 = 473382 byte
Anda dapat melihat bahwa semakin tinggi k, semakin baik kompresi. Tetapi pada titik tertentu (pada k = 16), overhead dari tabel frekuensi mulai lebih besar daripada manfaat dari peningkatan akurasi. Jika Anda mengompres file yang lebih kecil, efek ini akan muncul pada k yang lebih kecil.
Anda juga perlu mengatakan beberapa kata tentang trik yang disebut "interleaved rans", yang juga diterapkan
dalam contoh ini . Idenya adalah bahwa secara bergantian menggunakan dua variabel keadaan bebas membuat penggunaan paralelisme prosesor lebih baik. Akibatnya, decoding lebih cepat.
Sebagai kesimpulan, saya ingin mencatat bahwa metode kompresi file yang dipilih terlalu sederhana. Itu tidak mempertimbangkan fitur data, itulah sebabnya kompresi jauh dari optimal. Jika Anda memperhatikan input dengan cermat, Anda dapat menemukan bahwa beberapa
kombinasi huruf lebih umum daripada yang lain, dan beberapa tidak terjadi sama sekali. Dengan menggunakan fakta ini, kompresi dapat ditingkatkan secara signifikan. Tetapi ini adalah topik untuk artikel terpisah.
Kata penutup
Mengapa menulis arsip Anda sendiri ketika ada banyak utilitas yang teruji waktu? Jawabannya cukup sederhana: pengarsip yang dirancang untuk kompres format tertentu jauh lebih baik.
Saat mengembangkan game di
Playrix , kita sering mengandalkan kebutuhan untuk mengurangi ukuran build. Game terus berkembang, jumlah konten terus bertambah, dan ruang terbatas.
Sekali lagi
, melihat dengan
penuh perhatian pada sumber daya, kami menyadari bahwa beberapa file dapat dikompresi jauh lebih baik daripada zip, mengingat strukturnya. Selama percobaan, kami berhasil mengurangi ukuran format animasi kami secara signifikan, ada juga beberapa perubahan dalam kompresi file grafik.
Saat mengembangkan algoritma kompresi, encoder entropi universal, seperti rANS atau FSE, adalah alat yang sangat diperlukan. Ini sepenuhnya mengambil tugas menulis karakter dengan jumlah bit paling sedikit, memungkinkan pengembang untuk fokus pada detail utama dari algoritma. Dan itu juga berfungsi sangat cepat baik dalam encoding dan decoding.
Saya harap artikel ini membantu Anda mengenal RANS dan mulai menggunakannya dalam proyek Anda.
Referensi
Di sini Anda dapat melihat contoh kerja implementasi RANS (dengan berbagai opsi optimisasi):
Fabian Giesen:
github.com/rygorous/ryg_ransAnda dapat membaca detail dan detail menarik di blog Fabian (dalam bahasa Inggris):
β
RANS noteβ
RANS dengan distribusi probabilitas statisβ
RANS dalam praktek