Kode sebagai Pohon
Kode bebas-awalan memetakan ke pohon biner: akar mewakili awal dekoding, cabang kiri mewakili bit 0, cabang kanan mewakili bit 1, dan daun mewakili kode-kata lengkap.
Kendala geometris: setiap daun mengakhiri jalur dari-akar-ke-daun. Tidak ada daun yang dapat memiliki keturunan (jika demikian, kode-katanya akan menjadi awalan dari kode-kata keturunan, melanggar sifat bebas-awalan).
Ini memberikan ketidaksamaan Kraft interpretasi geometris:
Setiap daun pada kedalaman d 'menempati' fraksi 2^(−d) dari kapasitas pohon total. Kapasitas total pohon biner lengkap pada kedalaman D adalah 1. Kode bebas-awalan menggunakan daun pada berbagai kedalaman; jumlah Kraft mengukur penghunian total.
Jumlah Kraft = 1: kode lengkap (setiap jalur berakhir di daun — pengemasan sempurna).
Jumlah Kraft < 1: kode tidak lengkap (beberapa kapasitas pohon tidak digunakan — simbol lebih dapat ditambahkan).
Jumlah Kraft > 1: tidak mungkin untuk kode bebas-awalan (beberapa jalur harus berbagi daun).
Daun Lebih Dalam = Kode Lebih Panjang = Kapasitas Lebih Sedikit
Daun pada kedalaman 1 menggunakan setengah kapasitas pohon (2^(−1) = 0,5).
Daun pada kedalaman 3 menggunakan satu-delapan (2^(−3) = 0,125).
Menempatkan kode-kata pendek tinggi di pohon menghalangi semua keturunannya agar tidak digunakan — Anda menukar satu kode pendek dengan banyak kode yang berpotensi lebih panjang.
Membangun Pohon Bebas-Awalan
Pertimbangkan 5 simbol dengan panjang l = {1, 2, 3, 3, 3}. Jumlah Kraft = 2^(−1) + 2^(−2) + 3·2^(−3) = 0,5 + 0,25 + 0,375 = 1,125 > 1.
Ini melebihi 1: panjang ini tidak kompatibel dengan kode bebas-awalan. Setidaknya satu panjang harus meningkat.
Perbaiki: ubah l_1 dari 1 ke 2. Panjang baru {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0,5 + 0,375 = 0,875 < 1. Valid, tetapi tidak lengkap.
Perbaiki: ubah l_1 dari 2 ke 2, tambahkan l_2 = 3 untuk menggunakan kapasitas yang tersisa. Kraft = 0,875; sisa = 0,125 = 2^(−3): ruang untuk satu daun kedalaman-3 lagi.
Mengapa Entropi Membatasi Panjang Kode
Ketidaksamaan Kraft membatasi struktur kode (panjang harus sesuai di pohon). Entropi Shannon membatasi efisiensi kode (panjang rata-rata tidak dapat mengalahkan lantai teoretis).
Panjang kode optimal. Untuk simbol dengan probabilitas p_i, panjang kode ideal adalah log₂(1/p_i). Simbol langka layak mendapat kode panjang; simbol sering layak mendapat kode pendek. Ini mencerminkan kesetaraan Kraft: 2^(−l_i) = p_i ketika l_i = log₂(1/p_i).
Tetapi log₂(1/p_i) jarang merupakan bilangan bulat. Pembulatan ke atas menjadi ⌈log₂(1/p_i)⌉ memberikan panjang Huffman, yang memenuhi H ≤ L < H + 1.
Pembacaan geometris. Plot setiap simbol sebagai titik pada pohon biner pada kedalaman l_i. Jumlah Kraft mengukur penutupan daun total. Entropi mengukur kedalaman rata-rata tertimbang, tertimbang dengan probabilitas. Teorema Shannon: kedalaman rata-rata tertimbang probabilitas ≥ konten informasi tertimbang probabilitas.
Verifikasi Batas Entropi
Contoh yang terselesaikan: p = [1/2, 1/4, 1/8, 1/8] untuk simbol {A, B, C, D}.
Panjang optimal: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Ini semua bilangan bulat — kecocokan sempurna. Kode Huffman: A=0, B=10, C=110, D=111.
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 0,5 + 0,5 + 0,375 + 0,375 = 1,75.
H = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75. L = H tepat: kode optimal.
Contoh Terselesaikan Lengkap
Alur lengkap: diberikan probabilitas, hitung entropi, verifikasi kode memenuhi batas.
Sumber: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 bit (dihitung di atas).
Kode blok naif: 4 simbol → 2 bit masing-masing → L = 2,0. Overhead atas entropi: 2,0 − 1,75 = 0,25 bit/simbol = pemborosan 12,5%.
Kode panjang variabel menghemat 12,5% dibandingkan dengan panjang tetap. Untuk pesan besar, ini signifikan.
Laju entropi Inggris. Shannon memperkirakan entropi bahasa Inggris tertulis pada sekitar 1,0 hingga 1,3 bit per karakter, meskipun menggunakan kode ASCII 5-bit. Rasio 4:1 itu mencerminkan redundansi besar dalam bahasa alami — huruf umum berkluster, kata berulang, tata bahasa membatasi urutan.
Kompresi Tidak Dapat Mengalahkan Entropi
Rasio kompresi: H / (panjang kode blok). Untuk contoh kami: 1,75/2,0 = 0,875 — efisiensi 87,5%.
Bisakah Anda mengompres lebih jauh? Hanya dengan menggunakan konteks: jika Anda mengenkode pasangan atau rangkap tiga simbol bersama-sama, entropi gabungan H(X,Y) mungkin kurang dari 2·H(X) karena ketergantungan statistik. Ini adalah perpanjangan dari teorema pengkodean tanpa gangguan ke n-gram.