Zorlamalı Stratejinin Optimal Olmasının Nedeni
Huffman algoritması zorlamalı bir algoritmadır: her adımda, yerel optimum seçeneği (en ucuz iki düğümü birleştirir) olmadan ileriye bakmaz. Zorlamalı algoritmalar her zaman küresel optimum olmayabilir - ancak burada öyle.
Optimalite Argümanı
Bir kod C'nin en küçük ortalama uzunluğu L olsun. En düşük olasılıklı iki sembolü düşünün, örneğin p_a ve p_b. Herhangi bir optimal kodda, bu iki sembolun en derin seviyede birbirinin kardeşi yaprakları olmalı. Niçin?
Eğer bir arada olmadıklarsa, daha kısa bir kodla değiştirilebilecek en derin sembolu değiştirin - L'yi azaltın. Dolayısıyla en derin yapraklar en az olası semboller olmalıdır.
Şimdi, a ve b'ü bir meta-sembol ab (p_ab = p_a + p_b) ile birleştirin, küçültülmüş alfabe dışındaki herhangi bir optimal kod, küçültülmüş soruna uygulanan Huffman kodudur. Endüktif argüman tamamlanır.
Geometrik Görünüm
Huffman algoritması en alttan yukarı binary tree oluşturur, en az olası sembolleri en büyük derinlikte yer alır. Bu, Σ p_i · depth(i) = L'yi en aza indirir.
Bir başka bakış açısı: her bir yaprağa olan probablilik ağırlıklı yol uzunluğunu en aza indirirken, etiketler atamaktasınız.
Zorlamalı Adımları Gerçekleştirmek
Olasılıklar: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Toplam = 1.0 ✓
Adım 1: En düşük iki: C(0.2), D(0.1). Birleştir → CD(0.3). Liste: A(0.4), B(0.3), CD(0.3).
Adım 2: En düşük iki: B(0.3), CD(0.3) (birlikte - her ikisi de geçerli). Birleştir → BCD(0.6). Liste: A(0.4), BCD(0.6).
Adım 3: A(0.4), BCD(0.6) birleştir → kök(1.0). A=0, BCD=1 ataması.
Geriye Doğru: 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.
Kod Uzunluğu Değişkenliği
Huffman kodları iki farklı şekilde aynı L'yi elde edebilir ancak kod uzunluğu dağılımları farklı olabilir. Kod uzunlukları arasındaki değişkenlik ölçülür:
Var(l) = E[l²] − (E[l])²
nere E[l] = L (ortalama kod uzunluğu) ve E[l²] = Σ p_i · l_i².
Neden değişkenlik önemli:
1. Yüklemesi gereken bufer boyutu. Gerçek zamanlı çözme sırasında her sembol değişken bir sayıdaki bit kullanır. Yüksek değişkenlik bazı sembollerin çok fazla bit kullanması anlamına gelir — sürekli bir sembol okuma garantisi sağlamak için daha büyük bir giriş buferi gerekir.
2. Çözme gecikme süresi. Yüksek- değişkenlikli kodlar en uzun olası çözme yollarına sahip olur. Düşük- değişkenlikli (kabuklu) kodlar en kötü durumu daha sıkı bir şekilde bağlar.
3. Dayanıklılık. Yüksek- değişkenlikli kodlarda bir bit kaybı daha fazla senkronizasyon hasarı nedeni olur çünkü uzun kod sözcükleri tamamen yeniden okunmalıdır.
Hamming'in önerisi: Birden fazla geçerli Huffman kodunun mevcut olduğu durumlarda (ayırma seçenekleri), daha düşük değişkenliğe sahip olanı — kabuklu ağı — tercih edin.
İki Ağ için Değişkenlik Hesaplama
p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 ve kod A=0, B=10, C=110, D=111 kullanılarak:
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
3-Sembol Huffman Kodu Sonu Sonu
Tam bir sondan sona kadar örneği: Huffman kodunu oluşturun, L'yi hesaplayın, H'yi hesaplayın, L ≥ H'yi doğrulayın, Var'ı hesaplayın.
Kaynak: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Huffman oluşturma:
Adım 1: Sırala: X(0.6), Y(0.3), Z(0.1). En düşük iki: Y(0.3), Z(0.1).
Birleştir → YZ(0.4). Liste: X(0.6), YZ(0.4).
Adım 2: X(0.6) ve YZ(0.4)'yi birleştirelim → root(1.0). X=0, YZ=1 ataması yapın.
YZ → Y=10, Z=11.
Kod: 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% üstünde entropi.
Beyannamesi: 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.
Senein Yarı: Tam Bir Piyasa
Referans için log₂ değerleri: 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.