Mengapa Strategi Greedy Optimal
Algoritma Huffman adalah algoritma greedy: di setiap langkah, ia membuat pilihan yang optimal secara lokal (menggabungkan dua simpul termurah) tanpa melihat ke depan. Algoritma greedy tidak selalu optimal secara global — tetapi di sini mereka adalah.
Argumen Optimalitas
Misalkan kode C memiliki panjang rata-rata minimum L. Pertimbangkan dua simbol dengan probabilitas terendah, katakanlah p_a dan p_b. Dalam kode apa pun yang optimal, dua simbol ini harus muncul sebagai daun bersaudara di tingkat terdalam pohon. Mengapa?
Jika mereka tidak berbagi induk, Anda dapat menukar simbol yang lebih dalam dengan kode yang lebih pendek — mengurangi L. Oleh karena itu, daun terdalam harus berupa simbol-simbol yang paling tidak mungkin.
Sekarang, jika Anda menggabungkan a dan b menjadi meta-simbol ab (dengan p_ab = p_a + p_b), kode apa pun yang optimal untuk alfabet yang dikurangi minus satu simbol adalah persis kode Huffman pada masalah yang dikurangi. Induksi menyelesaikan argumen.
Pandangan Geometris
Algoritma Huffman membangun pohon biner dari bawah ke atas, menempatkan simbol-simbol yang paling tidak mungkin pada kedalaman terbesar. Ini meminimalkan Σ p_i · depth(i) = L.
Pandangan yang setara: Anda menetapkan label ke daun pohon untuk meminimalkan panjang jalur tertimbang, di mana berat setiap daun adalah probabilitasnya.
Menjalankan Langkah-langkah Greedy
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) (seri — keduanya 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 penyebaran ini:
Var(l) = E[l²] − (E[l])²
di mana E[l] = L (panjang kode rata-rata) dan E[l²] = Σ p_i · l_i².
Mengapa varian penting:
1. Persyaratan buffer. Dalam dekodean real-time, setiap simbol membutuhkan jumlah bit yang berbeda-beda. Varian tinggi berarti beberapa simbol membutuhkan banyak bit — Anda memerlukan buffer input yang lebih besar untuk menjamin Anda selalu dapat membaca simbol yang lengkap.
2. Latensi dekodean. Kode dengan varian tinggi memiliki jalur dekodean worst-case yang panjang. Kode dengan varian rendah (lebat) mengikat worst-case lebih ketat.
3. Ketangguhan. Bit yang hilang dalam kode varian tinggi menyebabkan kerusakan sinkronisasi yang lebih besar karena codeword panjang harus dibaca ulang sepenuhnya.
Rekomendasi Hamming: ketika beberapa kode Huffman yang valid ada (pilihan tie-breaking), pilih yang memiliki varian lebih rendah — pohon yang lebat.
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
Kode Huffman 3-Simbol Dari Awal hingga Akhir
Contoh lengkap end-to-end: 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.
Pembuatan Huffman:
Langkah 1: Diurutkan: 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) → akar(1.0). Tetapkan 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.
Varian: 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: Saluran 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.