Neden Açgözlü Strateji Optimaldir
Huffman algoritması bir açgözlü algoritmadır: her adımda lokal olarak en uygun seçimi yapar (en ucuz iki düğümü birleştirir) ileri bakmadan. Açgözlü algoritmalar her zaman küresel olarak en uygun değildir — ancak burada öyledir.
Optimallik Argümanı
Bir C kodu minimum ortalama uzunluğu L'ye sahip olduğunu varsayalım. Düşük olasılığa sahip iki sembolü düşünün, p_a ve p_b diyelim. Herhangi bir optimal kodda, bu iki sembol ağacın en derin seviyesinde kardeş yaprakları olarak görünmelidir. Neden?
Eğer ortak bir ebeveyne sahip olmayan sembol kodunu daha kısa bir kodla değiştirebilir, L'yi azaltabilirsiniz. Bu nedenle en derin yapraklar en az olasılıklı semboller olmalıdır.
Şimdi, eğer a ve b'yi bir meta-sembol ab'ye (p_ab = p_a + p_b ile) birleştirirseniz, azaltılmış alfabe eksi bir sembol için herhangi bir optimal kod, azaltılmış problemdeki Huffman kodudur. İndüksiyon argümanı tamamlar.
Geometrik Görüş
Huffman algoritması ikili ağacı aşağıdan yukarıya inşa eder, en az olasılıklı sembolleri en büyük derinliğe yerleştirir. Bu Σ p_i · depth(i) = L'yi en aza indirir.
Eşdeğer bir görüş: ağaç yapraklarına ağırlıklı yol uzunluğunu en aza indirmek için etiketler atarsınız, burada her yaprak'ın ağırlığı olasılığıdır.
Açgözlü Adımları Yürütme
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) (beraberlik — 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) → kök(1.0) birleştir. A=0, BCD=1 ata.
Geriye: 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 Varyansı
İki Huffman kodu aynı L'yi başarabilir ancak farklı kod-uzunluğu dağılımlarına sahip olabilir. Kod uzunluklarının varyansı bu yayılımı ölçer:
Var(l) = E[l²] − (E[l])²
burada E[l] = L (ortalama kod uzunluğu) ve E[l²] = Σ p_i · l_i².
Neden varyans önemlidir:
1. Tampon gereksinimleri. Gerçek zamanlı dekodlamada, her sembol değişken sayıda bit alır. Yüksek varyans, bazı sembollerin birçok biti alması anlamına gelir — her zaman tam bir sembol okuyabilecek olacağını garantilemek için daha büyük bir giriş tamponu gerekir.
2. Dekodlama gecikmesi. Yüksek varyans kodları uzun en-kötü durumda dekodlama yollarına sahiptir. Düşük varyans (geniş) kodları en-kötü durumu daha sıkı şekilde sınırlar.
3. Sağlamlık. Yüksek varyans kodundaki kayıp bir bit daha fazla senkronizasyon hasarına neden olur çünkü uzun kod sözcükleri tamamen yeniden okunmalıdır.
Hamming'in tavsiyesi: birden fazla geçerli Huffman kodu olduğunda (beraberlik kırma seçimleri), daha düşük varyansa sahip olanı tercih edin — geniş ağaç.
İki Ağaç İçin Varyans Hesaplama
p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 & kod A=0, B=10, C=110, D=111 kullanarak:
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 Uçtan Uca
Komple uçtan uca bir örnek: Huffman kodu inşa et, L hesapla, H hesapla, L ≥ H'yi doğrula, Var hesapla.
Kaynak: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Huffman inşası:
Adım 1: Sıralanmış: 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), YZ(0.4) → kök(1.0) birleştir. X=0, YZ=1 ata.
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. Entropi üzerinde 8.1%.
Varyans: 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.
Sizin Sıranız: Tam Bir Boru Hattı
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.