Bagaimana Huffman Membangun Kode Optimal
Hamming mempresentasikan Huffman coding sebagai algoritma yang membangun kode prefix bebas dengan panjang rata-rata minimum. Ide kunci: bangun pohon dari bawah ke atas, selalu gabungkan dua simbol probabilitas terendah.
Langkah Depan (Bangun)
1. Urutkan semua simbol berdasarkan probabilitas, dari yang tertinggi ke yang terendah.
2. Ambil dua simbol probabilitas terendah. Gabungkan mereka menjadi simbol meta dengan probabilitas = jumlah dari kedua simbol tersebut.
3. Masukkan simbol meta dalam posisi terurut.
4. Ulangi sampai hanya dua simbol yang tersisa.
5. Assign 0 dan 1 kepada dua simbol yang tersisa.
Langkah Balik (Assign Kode)
Balikkan penggabungan di sebaliknya: pada setiap pemisahan, dua simbol yang digabungkan menerima prefix bit yang sama seperti induk mereka yang digabungkan, ditambah bit tambahan 0 (anak satu) atau 1 (anak lain). Pengaturan 0/1 adalah sembarang - baik itu valid.
Mengapa ini adalah yang optimal: jika ada kode lain dengan panjang rata-rata L' yang lebih kecil, mengaplikasikan penurunan depan yang sama akan menghasilkan dua simbol dengan panjang rata-rata kurang dari 1 bit - tidak mungkin untuk kode 2-symbol. Kontradiksi.
Mengikuti 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 Depan:
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 yang tersisa: A(0.5), BCD(0.5). Assign A=0, BCD=1.
Langkah Balik:
BCD → B mendapatkan 10, CD mendapatkan 11. CD → C mendapatkan 110, D mendapatkan 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 bit.
Kode Huffman yang Valid Berbeda
Hamming mencatat dua sumber non-unik:
1. Penetapan acak 0/1. Pada setiap pembagian, Anda bisa memberikan 0 pada anak mana pun. Menggantikan 0 dan 1 secara keseluruhan memberikan kode yang berbeda dengan L yang sama.
2. Pengambilan keputusan serempak. Ketika dua node memiliki probabilitas yang sama, salah satu dapat ditempatkan 'tinggi' (dibandingkan terlebih dahulu). Pilihan pengambilan keputusan yang berbeda dapat menghasilkan struktur pohon yang berbeda - 'panjang' vs 'busuk' - dengan L yang sama tapi distribusi panjang kode yang berbeda.
Panjang vs Busuk
Pohon Panjang (tidak seimbang): satu simbol pada setiap tingkat kedalaman (struktur Fibonacci-like). Panjang kode bervariasi: satu simbol mendapatkan kode pendek, simbol lain jatuh ke kode yang lebih panjang.
Pohon Busuk (seimbang): simbol tersebar merata di tingkat kedalaman. Panjang kode berkumpul di sekitar rata-rata. Varian lebih kecil.
Rekomendasi Hamming: ketika diberi pilihan, pilih pohon busuk. L yang sama, tapi varian panjang kode yang lebih kecil → waktu dekoding yang lebih merata → kebutuhan buffer yang lebih kecil dalam aplikasi real-time.
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
Suatu kode busuk alternatif untuk simbol probabilitas sama menggunakan semua kode panjang-2: L=2, Var=0.
Pengurangan Kompresi vs Distribusi Simbol
Aturan Hamming: Koding Huffman menghasilkan keuntungan hanya ketika probabilitas simbol berbeda secara signifikan.
Probabilitas sama. Jika semua 2^k simbol memiliki probabilitas 1/2^k, Huffman menghasilkan kode blok: setiap simbol mendapatkan panjang k. L = H = k. Tidak ada keuntungan atas kode blok sederhana.
Probabilitas tidak seimbang. Jika satu simbol mendominasi (p >> 1/2^k untuk yang lain), Huffman mengasign-nya kode yang sangat pendek (panjang 1 atau 2), secara drastis 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, ..., hingga dua kode panjang yang sama di akhir. Ini adalah 'kode koma': nol setelah urutan 1 bertindak seperti koma.
Hamming catatan: kompresi data nyata (backup, arsip file) dapat mengurangi penyimpanan lebih dari setengah ketika sumber memiliki probabilitas tidak seimbang - teks Inggris adalah contoh yang baik.
Huffman vs Kode Blok: Perbandingan Angka
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 setiap satu → L_block = 3.
Hamming menghitung kode Huffman dan melaporkan L_Huffman ≈ 2,58 bit.
Simpanan: (3 - 2.58) / 3 ≈ 14% kompresi atas pengodean blok.
Ketika probabilitas simbol berbeda secara signifikan (1/3 vs 1/30 di sini, rasio 10: 1), pengodean berdasarkan panjang pembayaran secara signifikan.
Program Otomatiskompilasi
Hamming mengakhiri Bab 11 dengan ide menarik: encoder Huffman dapat mengkodekan dirinya sendiri. Pohon dekodifikasi (yang memberitahu decoder bagaimana membaca pesan yang dikompresi) ditransmisikan bersama dengan data yang dikompresi. Penerima tidak membutuhkan pengetahuan sebelumnya tentang kode.
Encoder: mengambil contoh data, menaksir probabilitas, membuat kode Huffman, mengkodekan pohon dekodifikasi sebagai header, lalu mengkodekan data.
Decoder: membaca header untuk memulihkan pohon, lalu mendekode data menggunakan itu.
Poin Hamming: seluruh pipa ini dapat berjalan sebagai fungsi perpustakaan dengan tidak ada campur tangan manusia. Anda memanggilnya, itu mengkompresi dan mendekompresi secara otomatis. Format arsip modern (ZIP, gzip, bzip2) mengimplementasikan pola yang sama.
Prinsip yang lebih dalam: kecerdasan ada dalam algoritma, bukan dalam tabel kode tetap. Algoritma beradaptasi dengan data apa pun yang diterimanya. Ini adalah pola yang dilihat Hamming di seluruh sistem pengembangan besar: adaptabilitas dibangun, bukan dirangkai.