Adaptive Arithmetic Coding

Raymond Kelvin Nando — Adaptive Arithmetic Coding merupakan teknik kompresi yang mengandalkan pendekatan probabilistik dinamis untuk memodelkan data secara berkelanjutan selama proses encoding berlangsung. Metode ini berbeda dari sistem kompresi tradisional karena bukan hanya membangun model probabilitas di awal, melainkan memperbaruinya setiap kali simbol baru diproses. Hal ini membuat teknik ini mampu beradaptasi dengan pola data yang berubah-ubah sehingga tingkat efisiensinya jauh lebih tinggi pada berbagai jenis konten. Adaptive Arithmetic Coding menjadi bagian penting dari banyak algoritma kompresi modern karena kemampuannya mencapai batas teoritis kompresi menurut informasi Shannon.

Pengertian Adaptive Arithmetic Coding

Adaptive Arithmetic Coding adalah metode kompresi entropi yang mengubah rangkaian simbol menjadi representasi bilangan pecahan dalam interval [0,1). Dalam pendekatan adaptif, probabilitas setiap simbol tidak ditentukan sejak awal, tetapi diperbarui seiring encoding berjalan. Dengan perbaikan model secara dinamis ini, sistem dapat menangkap distribusi simbol yang berubah, menjadikannya sangat efektif untuk data yang tidak memiliki pola tetap.

Berbeda dari Huffman Coding yang menggu­nakan kode tetap untuk setiap simbol, Arithmetic Coding bekerja dengan memperkecil interval probabilitas secara bertahap berdasarkan urutan simbol yang muncul. Pendekatan ini memberikan keuntungan berupa rasio kompresi yang sangat mendekati entropy limit, terutama ketika probabilitas simbol bersifat tidak stabil atau tidak diketahui sebelumnya.

Adaptive Arithmetic Coding digunakan dalam berbagai aplikasi seperti kompresi citra, audio, dokumen, dan format multimedia, karena fleksibilitasnya yang sangat tinggi serta sifatnya yang lossless dalam tahap entropi.

Sejarah Perkembangan Adaptive Arithmetic Coding

Konsep dasar Arithmetic Coding mulai berkembang pada 1970-an ketika metode kompresi probabilistik mulai dieksplorasi sebagai alternatif Huffman Coding. J. Rissanen dan G. Langdon dari IBM pada akhir 1970-an memperkenalkan Arithmetic Coding modern, kemudian menyusul penelitian lanjutan yang memperluas kemampuan adaptifnya.

Pada era 1980–1990-an, penelitian intensif menghasilkan versi adaptif yang mampu memperbarui model probabilitas secara real-time. Hal ini menjadi terobosan penting karena menghilangkan kebutuhan memodelkan distribusi simbol terlebih dahulu, membuat metode ini cocok untuk data dinamis seperti citra dan teks.

Adaptive Arithmetic Coding mulai diterapkan secara luas dalam standar-standar kompresi seperti JPEG, JBIG, dan H.263, meskipun implementasinya sering dibatasi oleh faktor paten pada masa itu. Setelah paten utama berkaitan dengan Arithmetic Coding berakhir pada awal 2000-an, metode ini menjadi lebih terbuka untuk penelitian dan digunakan secara bebas dalam algoritma kompresi modern. Kini, teknik ini tetap menjadi pilihan utama pada sistem kompresi yang membutuhkan presisi probabilistik tinggi dan efisiensi maksimal.

Prinsip Dasar dan Metode Adaptive Arithmetic Coding

Adaptive Arithmetic Coding bekerja dengan prinsip memperkecil interval probabilitas berdasarkan urutan simbol, dengan model yang berubah secara adaptif. Metode utamanya sebagai berikut:

1. Interval Probabilitas

Semua simbol ditempatkan dalam interval awal [0,1). Setiap simbol memiliki sub-interval proporsional dengan probabilitas kemunculannya.

2. Pembaruan Interval

Setiap kali simbol dibaca, interval diperbarui menjadi sub-interval sesuai probabilitas simbol tersebut. Interval semakin kecil seiring bertambahnya simbol.

3. Pemodelan Adaptif

Frekuensi simbol diperbarui setiap kali simbol muncul. Probabilitas dihitung ulang terus-menerus sehingga sistem beradaptasi dengan pola data.

4. Estimasi Probabilitas Real-Time

Pada awalnya, semua simbol diasumsikan memiliki probabilitas yang sama atau pseudo-count. Ketika data diproses, probabilitas menjadi lebih akurat.

5. Representasi Akhir

Hasil encoding adalah satu nilai dalam interval akhir—yang kemudian direpresentasikan dalam bentuk bitstream.

6. Proses Dekoding

Decoder gunakan model adaptif yang sama (dimulai dari kondisi awal identik) dan memperbarui probabilitas secara sinkron untuk merekonstruksi simbol tepat dari interval.

Pendekatan adaptif membuat algoritma ini sangat fleksibel, akurat, dan efisien menghadapi distribusi simbol yang berubah atau tidak diketahui.

Contoh Input dan Output Adaptive Arithmetic Coding

Contoh berikut hanya bersifat ilustratif untuk menunjukkan pola kerja:

Input

A B A A C

Model Awal (Probabilitas Setara)

A = 1/3
B = 1/3
C = 1/3

Proses Interval (Ilustrasi Konseptual)

• Setelah membaca A → interval dipersempit ke bagian A.
• Setelah membaca B → interval dipersempit lagi ke sub-interval B pada interval sebelumnya.
• Setelah setiap simbol, jumlah kemunculan diperbarui sehingga probabilitas berubah.

Output Encoding (Representasi Pecahan)

0.347918...  (disajikan dalam bitstream sebagai rangkaian bit)

Output sebenarnya berupa bitstream panjang yang merupakan pengkodean dari interval final tersebut.

Kelebihan & Kekurangan Adaptive Arithmetic Coding

Kelebihan

• Mampu mendekati batas kompresi teoretis Shannon.
• Sangat efisien pada data dengan pola probabilitas yang berubah.
• Tidak memerlukan model probabilitas awal.
• Cocok untuk kompresi lossless dan sebagai tahap entropi pada kompresi lossy.
• Lebih efisien daripada Huffman pada distribusi simbol yang tidak merata.
• Mendukung data dengan konteks adaptif secara real-time.

Kekurangan

• Lebih kompleks untuk diimplementasikan dibanding metode berbasis kode tetap.
• Perhitungan interval membutuhkan ketelitian tinggi untuk menghindari underflow atau overflow.
• Proses encoding dan decoding lebih lambat dibanding kompresor sederhana.
• Memerlukan sinkronisasi model yang tepat antara encoder dan decoder.
• Kompleksitas numerik lebih besar dibanding metode probabilistik lain.

Referensi

• Rissanen, J., & Langdon, G. (1979). Arithmetic Coding for Data Compression. IBM Journal of Research and Development.
• Witten, I., Neal, R., & Cleary, J. (1987). Arithmetic Coding for Data Compression. Communications of the ACM.
• Sayood, K. (2017). Introduction to Data Compression. Morgan Kaufmann.
• Bell, T., Cleary, J., & Witten, I. (1990). Text Compression. Prentice Hall.
• Cover, T., & Thomas, J. (2006). Elements of Information Theory. Wiley.

FAQ