Kodun bir Ağacı Olarak
Ön-free kod, iki basamaklı bir ağa karşılık gelir: köke kodlama başlamasını temsil eder, sol dallar 0 bitini temsil eder, sağ dallar 1 bitini temsil eder ve dallar tam kod sözcüklerini temsil eder.
Geometrik kısıtlama: her yaprak kökte-sona doğru bir kökte-sona doğru yolun sonunu bitirir. Hiçbir yaprak torununa (eğer olsaydı, onun kod sözcüğünün önünü keserdi, ön-free özelliğini ihlal ederdi) sahip olamaz.
Bu, Kraft'in eşik koşulu için bir geometrik yorum sağlar:
Her d derinliğinde bir yaprak, toplam ağaç kapasitesinin % 2^(-d) 'ini işgal eder. D profili olan tam iki basamaklı bir ağaçın toplam kapasitesi 1'dir. Ön-free kod, farklı derinliklerde yapraklar kullanır; Kraft toplam işgalini ölçer.
Kraft toplamı = 1: tam kod (her yol bir yaprağa sonlanır - mükemmel bir paketlenme).
Kraft toplamı < 1: tam olmayan kod (bazı ağaç kapasitesi kullanılmamış - ek simgeler eklenmeyebilir).
Kraft toplamı > 1: ön-free kodlar için imkansız (bazı yolların aynı yaprağa sahip olması gerekecekti).
Daha Derin Yapraklar = Uzun Kodlar = Az Kapasite
Bir yaprağın derinliği 1'de kullanılabilecek ağaç kapasitesi (2^(-1) = 0.5).
Bir yaprağın derinliği 3'te kullanılabilecek ağaç kapasitesi (2^(-3) = 0.125).
Kısa bir kod sözcüğünü yüksek bir ağacın üstüne yerleştirin - bunu, birini kısa kod için birçok olası uzun kod kullanmaktan feda edersiniz.
Ön-free Ağacı Oluşturma
5 sembol düşünün, uzunluklar l = {1, 2, 3, 3, 3}. Kraft toplamı = 2^(-1) + 2^(-2) + 3·2^(-3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
Bu 1'den daha fazla: bu uzunluklar, ön-free kod ile uyumlu değildir. En az bir uzunluk artmalıdır.
Düzelt: l_1'i 1'den 2'ye değiştirin. Yeni uzunluklar {2, 2, 3, 3, 3}: Kraft = 2·2^(-2) + 3·2^(-3) = 0.5 + 0.375 = 0.875 < 1. Geçerli, ancak tam değil.
Düzelt: l_1'i 2'den 2'ye değiştirin, ek olarak l_2 = 3'u kullanılabilir kalan kapasiteye. Kraft = 0.875; kalan = 0.125 = 2^(-3): daha fazla derinlik-3 yaprağa yer var.
Neden Entropi, Kod Uzunluğunu Sınırlar
Kraft eşitsizliği, kod yapısı üzerinde bir kısıtlama uygular (uzunluklar ağacın içinde yer almalıdır). Shannon'ın entropisi, kod verimliliği üzerinde bir kısıtlama uygular (ortalama uzunluk teorik bir zeminin üzerinde olamaz).
En iyi kod uzunlukları. Sembol için p_i olasılığına sahip olduğunda, ideal kod uzunluğu log₂(1/p_i) dir. Nadir semboller uzun kodlar, sıklıkla görülen semboller kısa kodlar gerektirir. Bu, Kraft eşitliğiyle uyumludur: 2^(−l_i) = p_i olduğunda l_i = log₂(1/p_i).
Ama log₂(1/p_i) genellikle tam sayı değildir. log₂(1/p_i)'ye çıkarak ⌈ ⌉, Huffman uzunluğunu elde eder, bu da H ≤ L < H + 1 şeklinde ifade edilir.
Jeodik okuma. Her sembolü, binary ağacın derinliğinde bir nokta olarak temsil edin l_i. Kraft toplamı, tüm yaprakların toplam kaplamasını ölçer. Entropi, olasılık ağırlıklı ortalama derinliği ölçer. Shannon'ın teoremi: olasılık ağırlıklı ortalama derinlik, olasılık ağırlıklı bilgi içeriği olanaklı olanın altında bulunur.
Entropi Sınır Kontrolü
Çalışma örneği: p = [1/2, 1/4, 1/8, 1/8] semboller için A, B, C, D.
En iyi uzunluklar: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Bütün tam sayılar - mükemmel bir eşleşme. Huffman kodları: 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 tam olarak: optimal kod.
Tam Çalışma Örneği
Tam süreç: verilen olasılıklar, entropi hesabı, bir kodun sınırları karşıp edip etmediğini doğrula.
Kaynak: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 bit (yukarıda hesaplandı).
Bir basit bloğ kodu: 4 sembol → her biri için 2 bit → L = 2,0. Entropiden fazla olan yük: 2,0 - 1,75 = 0,25 bit/symbol = %12,5 israf.
Değişken uzunlukta kod, sabit uzunlukta koddan %12,5 daha az yer kaplar. Büyük mesajlar için bu önemli bir tasarruf sağlar.
İngilizce'nin entropi oranı. Shannon, yazılı İngilizce'nin entropisini yaklaşık olarak 1,0 ila 1,3 bit/karakter olarak tahmin etti, 5 bitlik ASCII kodlarını kullanıyordu. Bu 4:1 oranı, doğal dilde bulunan devasa israfta olanlık gösterir - ortak harfler gruplar, kelimeler tekrarlanır, dilbilgisi sınırların dizileri -
Sıkıştırma Entropiden Daha Az Başarır
Sıkıştırma oranı: H / (blok kod uzunluğu). Örnek için: 1,75/2,0 = 0,875 - %87,5 etkinlik.
Daha fazla sıkıştırmaya ne dersiniz? Sadece bağlamı kullanarak, sembollerin ikili veya üçlü gruplarını birlikte kodlarsanız, bağlı olasılıklar H(X,Y) H(X) 'nin iki katından daha az olabilir. Bu, sessiz kodlama teoreminin n-gramlara kadar olan uzantısıdır.