Bagaimana Huffman Membangun Kode Optimal
Hamming mempresentasikan Huffman coding sebagai algoritma greedy yang membangun kode bebas-prefiks dengan panjang rata-rata minimum. Ide kuncinya: bangun pohon dari bawah ke atas, selalu menggabungkan dua simbol dengan probabilitas terendah.
Langkah Maju (Bangun)
1. Urutkan semua simbol berdasarkan probabilitas, tertinggi ke terendah.
2. Ambil dua simbol dengan probabilitas terendah. Gabungkan mereka menjadi meta-simbol baru dengan probabilitas = jumlah dari keduanya.
3. Masukkan meta-simbol pada posisi terurutnya.
4. Ulangi sampai hanya dua simbol tersisa.
5. Tetapkan 0 dan 1 untuk dua simbol yang tersisa.
Langkah Mundur (Tetapkan Kode)
Batalkan penggabungan secara terbalik: pada setiap pemisahan, dua simbol yang digabungkan menerima bit prefiks yang sama dengan induk gabungannya, ditambah 0 tambahan (satu anak) atau 1 (anak lainnya). Penugasan 0/1 bersifat sewenang-wenang — keduanya valid.
Mengapa ini optimal: jika ada kode lain dengan panjang rata-rata lebih kecil L', menerapkan pengurangan maju yang sama pada akhirnya akan menghasilkan dua simbol dengan panjang rata-rata kurang dari 1 bit — tidak mungkin untuk kode 2-simbol. Kontradiksi.
Melacak Algoritma
Contoh dari Hamming: empat simbol A, B, C, D dengan p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
Langkah maju:
Langkah 1: Terurut: A(0,5), B(0,25), C(0,125), D(0,125). Dua terendah: C, D.
Langkah 2: Gabung CD dengan p=0,25. Daftar baru: A(0,5), B(0,25), CD(0,25).
Langkah 3: Dua terendah: B(0,25), CD(0,25). Gabung BCD dengan p=0,5.
Langkah 4: Dua simbol tersisa: A(0,5), BCD(0,5). Tetapkan A=0, BCD=1.
Langkah mundur:
BCD → B mendapat 10, CD mendapat 11. CD → C mendapat 110, D mendapat 111.
Kode akhir: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75 bits.
Kode Huffman Sah Ganda
Hamming mencatat dua sumber non-keunikan:
1. Penugasan 0/1 sewenang-wenang. Pada setiap pemisahan, Anda dapat memberikan 0 kepada salah satu anak. Menukar 0 dan 1 di seluruh memberikan kode berbeda dengan L identik.
2. Penghentian-seri. Ketika dua node memiliki probabilitas sama, salah satu dapat ditempatkan 'lebih tinggi' (digabungkan terlebih dahulu). Pilihan penghentian-seri yang berbeda dapat menghasilkan pohon yang secara struktural berbeda — 'panjang' vs 'lebat' — dengan L sama tetapi distribusi panjang kode berbeda.
Panjang vs Lebat
Pohon panjang (miring): satu simbol pada setiap tingkat kedalaman (struktur mirip-Fibonacci). Panjang kode bervariasi luas: satu simbol mendapat kode pendek, yang lain berjajar ke kode yang lebih panjang.
Pohon lebat (seimbang): simbol tersebar merata di seluruh tingkat kedalaman. Panjang kode berkumpul dekat rata-rata. Varians lebih rendah.
Rekomendasi Hamming: ketika diberi pilihan, pilih pohon lebat. L sama, tetapi varians lebih kecil dalam panjang kode → waktu dekoding lebih seragam → persyaratan buffer lebih kecil dalam aplikasi waktu-nyata.
Menghitung Varians Panjang Kode
Varians panjang kode: Var = E[l²] − (E[l])²
Untuk kode {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} dengan p=[0,5, 0,25, 0,125, 0,125]:
E[l] = L = 1,75
E[l²] = 0,5·1² + 0,25·2² + 0,125·3² + 0,125·3² = 0,5 + 1,0 + 1,125 + 1,125 = 3,75
Var = 3,75 − 1,75² = 3,75 − 3,0625 = 0,6875
Kode lebat alternatif untuk simbol probabilitas-sama menggunakan semua kode panjang-2: L=2, Var=0.
Keuntungan Kompresi vs Distribusi Simbol
Aturan Hamming: Huffman coding membayar hanya ketika probabilitas simbol berbeda secara substansial.
Probabilitas sama. Jika semua simbol 2^k memiliki probabilitas sama 1/2^k, Huffman menghasilkan kode blok: setiap simbol mendapat panjang k. L = H = k. Tidak ada keuntungan atas kode blok sederhana.
Probabilitas miring. Jika satu simbol mendominasi (p >> 1/2^k untuk yang lain), Huffman memberikannya kode sangat pendek (panjang 1 atau 2), secara dramatis mengurangi L.
Kode koma (istilah Hamming). Ketika setiap probabilitas melebihi 2/3 dari total yang tersisa, Huffman secara alami menghasilkan: p(s1)→0, p(s2)→10, p(s3)→110, ..., turun ke dua kode panjang-sama di akhir. Ini adalah 'kode koma': trailing 0 setelah rentetan 1s bertindak seperti koma.
Hamming mencatat: kompresi data dunia nyata (cadangan, pengarsipan file) dapat mengurangi penyimpanan lebih dari setengahnya ketika sumber memiliki probabilitas miring — teks Inggris adalah contoh utama.
Huffman vs Kode Blok: Perbandingan Numerik
Contoh kedua Hamming: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Kode blok: 8 simbol → 3 bit masing-masing → L_block = 3.
Hamming menghitung kode Huffman dan melaporkan L_Huffman ≈ 2,58 bits.
Penghematan: (3 − 2,58)/3 ≈ 14% kompresi dibanding kode blok.
Ketika probabilitas simbol berbeda besar (1/3 vs 1/30 di sini, rasio 10:1), kode panjang-variabel membayar secara substansial.
Program yang Mengompresi Diri Sendiri
Hamming menutup Bab 11 dengan ide mencolok: pengkode Huffman dapat mengkode dirinya sendiri. Pohon dekoding (yang memberi tahu dekoder bagaimana membaca pesan terkompresi) ditransmisikan bersama dengan data terkompresi. Penerima tidak memerlukan pengetahuan sebelumnya tentang kodenya.
Pengkode: mengambil sampel data, memperkirakan probabilitas, membangun kode Huffman, mengkode pohon dekoding sebagai header, kemudian mengkode data.
Dekoder: membaca header untuk merekonstruksi pohon, kemudian mendekode data menggunakannya.
Poin Hamming: seluruh saluran ini dapat berjalan sebagai fungsi perpustakaan tanpa keterlibatan manusia. Anda memanggilnya, ia mengompresi dan mendekompres secara otomatis. Format pengarsipan modern (ZIP, gzip, bzip2) menerapkan pola persis ini.
Prinsip yang lebih dalam: kecerdasan berada dalam algoritma, bukan dalam tabel kode tetap. Algoritma menyesuaikan dengan data apa pun yang diterimanya. Ini adalah pola yang Hamming lihat di semua sistem teknik besar: adaptabilitas dibangun, bukan ditambahkan.