ANS (Asymmetric Numeral Systems)

Raymond Kelvin Nando — ANS (Asymmetric Numeral Systems) merupakan teknik pengkodean entropi modern yang digunakan untuk kompresi data efisien. ANS menggabungkan keuntungan Huffman Coding dan Arithmetic Coding dengan pendekatan numerik yang memungkinkan representasi simbol dengan panjang bit variabel sesuai probabilitasnya, tetapi tetap mempertahankan kecepatan tinggi dan kompleksitas rendah. Sistem ini sangat populer dalam aplikasi kompresi modern seperti Zstandard, Facebook Zippy, dan format multimedia karena rasio kompresinya mendekati batas teoritis Shannon sambil tetap efisien secara komputasi.

Pengertian ANS (Asymmetric Numeral Systems)

ANS adalah metode pengkodean lossless yang memetakan simbol dengan probabilitas berbeda ke dalam satu nilai numerik yang bersifat stateful. Ada dua varian utama: rANS (range ANS) dan tANS (table ANS).

• rANS bekerja dengan menghitung interval numerik dan meng-update state secara bertahap untuk setiap simbol.
• tANS menggunakan tabel pra-hitung untuk mempercepat encoding/decoding.

Dengan ANS, simbol yang lebih sering muncul diwakili oleh bit yang lebih sedikit, sedangkan simbol jarang menggunakan bit lebih banyak, mirip dengan prinsip Arithmetic Coding, namun implementasinya lebih cepat dan sederhana dalam perangkat keras maupun perangkat lunak.

Sejarah Perkembangan ANS

ANS diperkenalkan oleh Jarek Duda pada tahun 2009–2013 sebagai alternatif efisien untuk Huffman dan Arithmetic Coding. Tujuannya adalah mencapai kompresi mendekati entropy limit dengan efisiensi komputasi tinggi.

Sejak diperkenalkan, ANS cepat diadopsi dalam berbagai algoritma kompresi modern:

• Zstandard (Zstd) menggunakan rANS untuk kompresi blok.
• Facebook Zippy menggunakan tANS untuk kecepatan tinggi.
• Algoritma multimedia modern, termasuk video dan audio codecs, memanfaatkan ANS untuk memadatkan data tanpa kehilangan informasi.

ANS menjadi metode penting karena mengurangi overhead komputasi dibanding Arithmetic Coding tradisional sekaligus lebih fleksibel daripada Huffman Coding.

Prinsip Dasar dan Metode ANS

ANS bekerja dengan mengubah aliran simbol menjadi satu nilai integer (state) yang berkembang seiring input diproses. Prinsip dasarnya:

1. State Initialization
   Mulai dengan state numerik awal, misalnya x = x0.
2. Encoding Simbol
   Update state menggunakan fungsi f(x, s) = new_state, di mana s adalah simbol dan probabilitasnya mempengaruhi jumlah bit yang diperlukan untuk memperbarui state.
3. Bitstream Extraction
   State dipecah menjadi bit atau byte untuk disimpan atau ditransmisikan.
4. Decoding
   Decoder menggunakan state awal identik dan membaca bitstream untuk mengembalikan simbol secara berurutan.
5. Varian rANS dan tANS

• rANS: Menghitung interval numerik dinamis, mirip Arithmetic Coding tapi menggunakan satu integer state.
• tANS: Menggunakan tabel pra-hitung untuk mapping simbol → state → output bitstream, mempercepat proses.

6. Efisiensi Entropi
   ANS mendekati entropy limit Shannon, sehingga kompresi sangat optimal untuk berbagai distribusi simbol.

Contoh Input dan Output ANS

Contoh ilustratif sederhana:

Input: A A B C A
Probabilitas simbol:
A = 0.5, B = 0.3, C = 0.2

Encoding langkah demi langkah:

1. Mulai state x = 0
2. Proses simbol pertama A → update state → x = 1
3. Proses simbol kedua A → x = 2
4. Proses simbol B → x = 6
5. Proses simbol C → x = 13
6. Proses simbol A → x = 27

Output akhir: integer 27, yang kemudian dikonversi menjadi bitstream sesuai algoritma rANS atau tANS.

Decoding menggunakan state 27 → mengembalikan urutan simbol asli A A B C A.

Kelebihan & Kekurangan ANS

Kelebihan:

• Rasio kompresi mendekati batas teoritis Shannon.
• Lebih cepat dibanding Arithmetic Coding.
• Implementasi sederhana untuk rANS maupun tANS.
• Cocok untuk streaming dan blok kompresi besar.
• Fleksibel terhadap distribusi simbol yang berubah.

Kekurangan:

• Memerlukan manajemen state yang presisi.
• Lebih kompleks dibanding Huffman Coding sederhana.
• Implementasi tANS memerlukan tabel pra-hitung besar untuk simbol banyak.
• Debugging lebih sulit karena state tersimpan dalam satu integer tunggal.
• Memerlukan perhatian ekstra pada overflow dan underflow integer.

Referensi

• Duda, J. (2013). Asymmetric Numeral Systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:1311.2540.
• Collet, Y. (2016). Zstandard Compression and the use of rANS. Facebook Engineering Blog.
• Salomon, D. (2007). Data Compression: The Complete Reference. Springer.
• Sayood, K. (2017). Introduction to Data Compression. Morgan Kaufmann.
• Mahoney, M. (2012). Data Compression Explained. Springer.

FAQ