📚 Entropy Informasi (Shannon) & Hubungannya dengan Kompresi

Kategori: Information Theory · Level: Intermediate–Advanced

🎯 Tujuan Belajar

Setelah sesi ini:

1. Bisa menghitung entropy Shannon dari sebuah distribusi dan menjelaskan mengapa rumusnya berbentuk -Σ p log p.
2. Memahami entropy sebagai batas bawah teoretis panjang kode rata-rata — bukan sekadar "ukuran ketidakpastian".
3. Bisa menjelaskan mengapa Huffman optimal untuk kode simbol-tunggal tapi tetap bisa melampaui H, dan kapan arithmetic coding menutup celah itu.
4. Bisa membedakan entropy dari "jumlah data" dan dari "kompleksitas Kolmogorov".

🧠 Penjelasan Inti

Masalah yang diselesaikan

Shannon (1948, A Mathematical Theory of Communication) menghadapi pertanyaan engineering: berapa bit minimum yang dibutuhkan untuk mengirim pesan dari sumber tertentu, tanpa kehilangan informasi? Sebelumnya orang menganggap ini soal pemilihan algoritma. Shannon menunjukkan ini soal batas matematis yang melekat pada distribusi sumber, independen dari algoritma apa pun.

Definisi

Untuk variabel acak diskret X dengan distribusi p(x):

H(X) = - Σ p(x) · log₂ p(x)     [satuan: bit]

Konvensi: 0 · log 0 = 0 (karena limit p log p → 0 saat p → 0).

• H = 0 ⟺ sumber deterministik (satu simbol probabilitas 1). Tidak ada informasi baru; penerima sudah tahu isinya.
• H maksimum log₂|X| saat distribusi uniform — ketidakpastian maksimal.

Kenapa berbentuk -log p?

Tiga aksioma yang memaksa bentuk ini (Shannon–Khinchin, terbukti unik hingga konstanta skala):

1. Monoton terhadap ukuran alfabet (uniform atas n simbol harus naik dengan n).
2. Kontinu terhadap perubahan kecil probabilitas.
3. Additivitas/decomposability: memecah pilihan menjadi tahap berurutan tidak mengubah total ketidakpastian.

-log₂ p(x) sendiri adalah "surprisal" atau self-information dari kejadian x: makin jarang, makin besar informasinya. Entropy = ekspektasi surprisal. Kejadian probabilitas 1/2 memberi tepat 1 bit; 1/1024 memberi 10 bit.

Justifikasi operasional: jika ada 2^n kemungkinan equally likely, butuh n bit untuk mengindeks. Generalisasi ke probabilitas tidak uniform menghasilkan log₂(1/p) bit — inilah jumlah minimum bit untuk "menunjuk" kejadian itu dalam skema kode ideal.

⚙️ Cara Kerjanya — Jembatan ke Kompresi

Source Coding Theorem (Shannon, 1948)

Untuk sumber i.i.d. dengan entropy H, ada kode lossless dengan panjang rata-rata L yang memenuhi:

H ≤ L < H + 1     (bit per simbol)

Dan tidak ada kode lossless yang bisa mencapai L < H rata-rata. Ini bukan klaim tentang algoritma tertentu — ini hukum, setara dengan konservasi energi di domain informasi.

Konsekuensi langsung: entropy adalah garis finish kompresi. Rasio kompresi maksimum untuk sumber = (bit_asli) / H.

Mengapa Huffman bisa > H

Huffman menghasilkan kode prefix optimal untuk satu simbol per codeword. Tapi panjang codeword harus bilangan bulat. Kalau p = 0.35, idealnya -log₂0.35 ≈ 1.515 bit — Huffman harus memilih 1 atau 2 bit. Selisih inilah overhead, terikat L − H < 1 bit/simbol.

Verifikasi numerik (saya jalankan):

Kasus pertama tepat mencapai H karena semua probabilitas adalah pangkat ½ — setiap -log₂ p sudah bilangan bulat, jadi tidak ada pembulatan. Ini bukti bahwa batas H bisa dicapai, bukan cuma didekati. Kasus kedua menunjukkan overhead klasik.

Cara menutup celah: block coding & arithmetic coding

• Block coding: kodekan blok n simbol sekaligus. Overhead jadi < 1/n bit per simbol → menuju H saat n besar. Mahal secara komputasi (tabel eksponensial).
• Arithmetic coding / range coding: tidak mengkodekan simbol, tapi interval dalam [0,1) yang menyempit sesuai probabilitas. Output ≈ -log₂ P(seluruh pesan) bit — praktis mencapai H tanpa pembulatan per simbol. Dipakai di H.264/HEVC, FLAC, bzip2, dan kebanyakan codec modern.
• ANS (Asymmetric Numeral Systems) (Duda, 2009–2014): kecepatan arithmetic coding mendekati Huffman, sekarang dominan di zstd, LZMA, dan codec video modern.

Contoh konkret

String "aaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbccccdd" (38 char):

H = 1.4574 bit/char
ASCII mentah = 8 bit/char  → 38 byte
Batas ideal  = 1.4574 × 38 / 8 ≈ 6.92 byte

Ruang kompresi teoretis ~5.5×. Entropy tidak memberitahu bagaimana mencapainya — hanya bahwa 6.92 byte adalah lantai. Algoritma (Huffman, LZ, arithmetic) adalah cara mendekati lantai itu.

💡 Analogi

Entropy = ukuran kamar; algoritma kompresi = cara menata barang di kamar itu. Kamar 10 m² tidak bisa menampung 15 m² barang, sebagus apa pun penataannya. Huffman adalah penata yang sangat baik tapi terpaksa pakai rak berukuran bulat; arithmetic coding adalah penata yang boleh memotong rak presisi milimeter.

Analogi 20 pertanyaan: menebak angka 1–1.000.000 butuh ~20 pertanyaan ya/tidak (log₂ 10⁶ ≈ 19.93). Jika angka tidak uniform (misal selalu < 1000), butuh lebih sedikit pertanyaan. Entropy adalah jumlah pertanyaan optimal yang diharapkan.

⚠️ Miskonsepsi Umum

⚖️ Trade-off / Limitasi

Yang diketahui pasti: - Source coding theorem adalah teorema, bukan heuristik. Berlaku untuk semua kode lossless. - Entropy rate untuk sumber Markov: H(X) = lim (1/n) H(X₁...Xₙ) — untuk proses stasioner ergodik, limit ini ada dan teorema tetap berlaku.

Yang bergantung asumsi: - Model adalah segalanya. H dari sumber sebenarnya tidak diketahui; kita mengestimasi dari data. Estimasi buruk → kompresi buruk. Inilah mengapa PPM, context mixing, dan model neural (NNCP, CMIX) jauh mengalahkan Huffman pada teks: mereka punya model yang lebih baik, bukan algoritma entropy coding yang lebih baik. - Model harus dikirim. "Two-part code": deskripsi model + data terkompresi. Untuk file kecil, biaya model bisa melebihi penghematan — sebabnya kompresor adaptif (tanpa header model) menang di file kecil.

Yang belum tuntas / batas praktis: - Lossless vs lossy. Untuk gambar/audio/video, H lossless tetap tinggi (noise sensor tidak bisa dikompresi). Codec lossy sengaja membuang informasi di bawah ambang persepsi — batasnya bukan H melainkan rate–distortion theory, kerangka terpisah dengan fungsi distorsi D. Ini area di mana "entropy" saja tidak cukup menjawab. - Kompleksitas komputasi. Mencapai H secara optimal secara umum butuh waktu eksponensial (optimal parsing). Semua kompresor praktis adalah aproksimasi dengan trade-off kecepatan/rasio. - Entropy estimasi dari data pendek bias ke bawah (plug-in estimator). Perlu Koreksi Miller–Madow atau estimator lain. Untuk n << |X|, estimasi tidak dapat dipercaya.

🛠️ Latihan Praktis

1. Hitung manual. Distribusi [0.5, 0.25, 0.25]. Hitung H, lalu bangun kode Huffman dan hitung L. Apakah L = H? Mengapa?

2. Eksperimen overhead. Ambil file teks ~10 KB. Hitung H empiris per byte (frekuensi byte). Bandingkan dengan ukuran hasil gzip -9. Jelaskan mengapa gzip lebih kecil dari H × n / 8 (petunjuk: gzip memakai model konteks, bukan frekuensi global — H orde-0 adalah batas atas, bukan bawah, untuk model yang lebih baik).

3. Uji batas. Kompres file yang sudah terkompresi (misal .jpg atau .zip) dengan gzip. Amati hasilnya sedikit membesar. Jelaskan dengan source coding theorem.

# kerangka cek cepat
python3 -c "
import math,collections,sys
d=open(sys.argv[1],'rb').read(); n=len(d)
c=collections.Counter(d)
H=-sum((v/n)*math.log2(v/n) for v in c.values())
print(f'H={H:.3f} bit/byte, batas={H*n/8:.0f} byte, asli={n} byte')
" file.txt

✅ Cek Pemahaman

1. Sebuah sumber menghasilkan simbol dengan p = [0.9, 0.1]. Hitung H. Jika Anda mengirim 1000 simbol, berapa bit minimum teoretis? Mengapa Huffman butuh tepat 1 bit/simbol di sini, dan berapa persen overhead-nya?
2. Mengapa menambahkan simbol dengan probabilitas sangat kecil (misal 10⁻⁶) hampir tidak mengubah H, padahal surprisal simbol itu ~20 bit?
3. Sebuah model bahasa memberi P(kalimat) = 2⁻⁴⁰. Berapa bit yang dibutuhkan arithmetic coding untuk mengkodekannya, dan apa hubungannya dengan cross-entropy loss (dalam nats) yang dilaporkan saat training?

🔑 Poin Kunci

• H = -Σ p log₂ p = ekspektasi surprisal. Bukan "jumlah data", tapi ketidakpastian intrinsik distribusi.
• Source coding theorem: H ≤ L < H + 1. Batas bawah keras untuk semua kompresi lossless. Tidak bisa dilanggar dengan algoritma apa pun.
• Huffman kehilangan sampai 1 bit/simbol karena codeword harus bilangan bulat. Arithmetic/ANS coding menutup celah ini dengan mengkodekan interval, bukan simbol.
• Entropy bukan takdir — model yang menentukan seberapa dekat Anda ke H. Model lebih baik = H efektif lebih rendah.
• Cross-entropy loss di ML = H(p) + KL(p‖q). Meminimalkannya secara langsung berarti mendekati entropy sebenarnya dari data.
• Untuk lossy compression, kerangka yang berlaku adalah rate–distortion, bukan entropy saja.

➡️ Eksplorasi Lanjut

Rate–Distortion Theory — generalisasi source coding theorem ke kompresi lossy. Mendefinisikan fungsi R(D): laju bit minimum untuk mencapai distorsi maksimum D di bawah metrik tertentu. Ini fondasi teoretis di balik JPEG, MP3, dan semua codec video, serta menjelaskan mengapa "kompresi lossy yang baik" adalah soal memilih metrik distorsi yang cocok dengan persepsi manusia — masalah yang masih terbuka (lihat perdebatan LPIPS vs SSIM vs metrik berbasis neural).