Mengapa Strategi yang Bersikap Rakus adalah Optimal
Algoritma Huffman adalah sebuah algoritma yang bersikap rakus: pada setiap langkah, ia memilih pilihan yang lokal terbaik (menggabungkan dua node termurah) tanpa melihat ke depan. Algoritma yang bersikap rakus tidak selalu optimal secara global — tetapi di sini mereka adalah.
Argumen Optimalitas
Anggap sebuah koding C memiliki panjang rata-rata minimum L. Pertimbangkan dua simbol terendah, misalnya p_a dan p_b. Dalam kode optimal apa pun, dua simbol ini harus muncul sebagai daun bersaudara di tingkat terdalam pohon. Mengapa?
Jika mereka tidak saling memiliki induk, Anda dapat menukar simbol yang lebih dalam dengan kode yang lebih pendek — mengurangi L. Oleh karena itu, daun terdalam harus merupakan simbol yang paling tidak mungkin.
Sekarang, jika Anda menggabungkan a dan b menjadi simbol meta ab (dengan p_ab = p_a + p_b), kode optimal apa pun untuk alphabet yang diperkecil tanpa satu simbol adalah tepatnya kode Huffman pada masalah yang diperkecil. Induksi menyelesaikan argumen.
Pandangan Geometris
Algoritma Huffman mengonstruksi pohon biner dari bawah ke atas, menempatkan simbol yang paling tidak mungkin pada kedalaman terbesar. Ini mengurangi Σ p_i · kedalaman(i) = L.
Pandangan yang setara: Anda sedang menetapkan label pada daun pohon untuk mengurangi panjang jalur berat, di mana setiap daun beratnya adalah probabilitasnya.
Mengimplementasikan Langkah-Langkah yang Bersikap Rakus
Probabilitas: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Jumlah = 1.0 ✓
Langkah 1: Dua terendah: C(0.2), D(0.1). Gabung → CD(0.3). Daftar: A(0.4), B(0.3), CD(0.3).
Langkah 2: Dua terendah: B(0.3), CD(0.3) (tie — salah satu valid). Gabung → BCD(0.6). Daftar: A(0.4), BCD(0.6).
Langkah 3: Gabung A(0.4), BCD(0.6) → akar(1.0). Tetapkan A=0, BCD=1.
Mundur: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 bit.
Varian Panjang Kode
Dua kode Huffman mungkin mencapai L yang sama tetapi memiliki distribusi panjang kode yang berbeda. Varian panjang kode mengukur seberapa luas distribusi ini:
Var(l) = E[l²] − (E[l])²
di mana E[l] = L (rata-rata panjang kode) dan E[l²] = Σ p_i · l_i².
Mengapa varian penting:
1. Kebutuhan Buffer. Dalam dekoding real-time, setiap simbol membutuhkan jumlah bit yang bervariasi. Tingkat varian tinggi berarti beberapa simbol membutuhkan banyak bit — Anda membutuhkan buffer input yang lebih besar untuk memastikan Anda dapat selalu membaca simbol yang lengkap.
2. Latensi Dekoding. Kode dengan tingkat varian tinggi memiliki jalur dekripsi yang paling lama. Kode dengan varian rendah (berdahan) mengikat batas kasus terburuk lebih erat.
3. Daya Tahan. Sebit yang hilang dalam kode dengan tingkat varian tinggi menyebabkan lebih banyak kerusakan sinkronisasi karena kodeword panjang harus dibaca kembali secara keseluruhan.
Rekomendasi Hamming: ketika ada beberapa kode Huffman yang valid (pilihan pengikat), pilih yang memiliki varian lebih rendah — pohon berdahan.
Menghitung Varian untuk Dua Pohon
Menggunakan p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 dan kode A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
Contoh Akhir ke Akhir: Kode Huffman 3-Simbol
Contoh akhir ke akhir yang lengkap: bangun kode Huffman, hitung L, hitung H, verifikasi L ≥ H, hitung Var.
Sumber: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Bangun Huffman:
Langkah 1: Terurut: X(0.6), Y(0.3), Z(0.1). Dua terendah: Y(0.3), Z(0.1).
Gabung → YZ(0.4). Daftar: X(0.6), YZ(0.4).
Langkah 2: Gabung X(0.6), YZ(0.4) → root(1.0). Assign X=0, YZ=1.
YZ → Y=10, Z=11.
Kode: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 bit.
Entropi: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 bit.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% di atas entropi.
Varians: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
Giliran Anda: Sebuah Pipa Lengkap
Nilai log₂ untuk referensi: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.