Huffman Optimal Kodu Nasıl Oluşturur
Hamming, Huffman kodlamayı, minimum ortalama uzunluklu önizlemesiz kod oluştıran bir açgözlü algoritma olarak sunar. Ana fikir: ağacı alttan üste doğru inşa etmek, her zaman en düşük olasılık sembollerini birleştirmek.
İlerlemeli Geçiş (Oluştur)
1. Tüm sembolleri olasılık sırasına göre en yüksekten en düşükere sırala.
2. En düşük olasılık sembolleri olan iki sembolü birleştir. Yeni bir meta sembol oluşturun, olasılık = iki sembolün toplamı.
3. Yeni sembolü sıralamadaki yerini bul.
4. İki sembol kalana kadar tekrarla.
5. Kalan iki sembolun her birine 0 ve 1 atama.
Geri Dönük Geçiş (Kod Atama)
Ayrıntıları geri alır: her birleşimde birleştirilen iki sembol, birleştiği ebeveyn sembolün aynı ön bitlerini alır ve ek olarak 0 (bir çocuk) veya 1 (diğer çocuk) ekler. 0/1 ataması rastgele - her ikisi de geçerli.
Neden bu optimal: herhangi bir diğer kodun daha küçük bir L'li ortalama uzunluksa, aynı ileri azaltma işlemine uygulandığında sonunda iki sembolün ortalama uzunluğu 1 bitten daha az olur - imkansız bir 2 sembol kodu için. Zıtlık.
Algoritmayı İzlemek
Örnek: Hamming'den: dört sembol A, B, C, D ile p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
İlerlemeli Geçiş:
Adım 1: Sıralama: A(0.5), B(0.25), C(0.125), D(0.125). En düşük iki: C, D.
Adım 2: CD'yi p=0.25 ile birleştir. Yeni liste: A(0.5), B(0.25), CD(0.25).
Adım 3: En düşük iki: B(0.25), CD(0.25). BCD'yi p=0.5 ile birleştir.
Adım 4: İki sembol kalır: A(0.5), BCD(0.5). A=0, BCD=1 ataması.
Geri Dönük Geçiş:
BCD → B 10, CD 11 alır. CD → C 110, D 111 alır.
Son kod: 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.
Birden Çok Geçerli Huffman Kodu
Hamming iki kaynaklı benzersiz olmayanlığı belirtir:
1. Rastgele 0/1 ataması. Her bölünmede, her iki çocuğa da 0 verebilirsiniz. Herhangi bir yerde 0 ve 1'i değiştirerek, aynı L'ye sahip farklı bir kod elde edebilirsiniz.
2. Beraberlik. İki düğümün eşit olasılığı varsa, hangisinin 'üstte' (ilk birleştirilecek) yerleştirileceği belirlenebilir. Aynı beraberlik seçimleri, aynı L'ye sahip ancak kod uzunlukları dağılımında farklı yapıda ağaçlar oluşturabilir - 'uzun' vs 'sert' -
Uzun ve Sert
Uzun ağaç (eğri): her derinlik seviyesinde bir sembol (Fibonacci benzer bir yapı). Kod uzunlukları büyük ölçüde değişir: bir sembol kısa bir kod alır, diğerleri kademeli olarak daha uzun kodlara doğru ilerler.
Sert ağaç (dengeli): semboller düzgünce derinlik seviyeleri boyunca yayılır. Kod uzunlukları ortalamaya yakın bir grup içinde yoğunlaşır. Düşük varyans.
Hamming'in önerisi: rastgelelik durumunda dengeli ağacı tercih edin. Aynı L, ancak kod uzunlukları varyansının daha küçük olması → daha düzenli bir kodlama zamanı → gerçek zamanlı uygulamalar için daha küçük tampon gereksinimi.
Kod Uzunlukları Varyansını Hesaplama
Kod uzunlukları varyansı: Var = E[l²] − (E[l])²
Kod {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} için 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
Bir eşit olasılıklı semboller için alternatif dallıbudak kodu, tüm 2 karakterli kodları kullanır: L=2, Var=0.
Kompresyon Kazançları vs Sembol Dağılımı
Hamming kuralı: Huffman kodunun ödeme sadece sembol olasılıkları önemli ölçüde farklı olduğunda gerçekleşir.
Eşit olasılıklar. Tüm 2^k sembolunun eşit olasılık 1/2^k olması durumunda Huffman, her sembole k karakterli bir blok kodu verir. L = H = k. Basit blok kodundan daha fazla kazanç yoktur.
Yanlış orantılı olasılıklar. Bir sembolün hakim olduğu durumda (p >> 1/2^k diğerleri için), Huffman onu çok kısa bir kod (1 veya 2 karakter) atar ve L'yi dramatik olarak azaltır.
Virgül kodu (Hamming'in terimi). Her olasılığın 2/3'ten fazla olduğu durumda, Huffman doğal olarak: p(s1)→0, p(s2)→10, p(s3)→110, ..., sonuna kadar iki eşit uzunlukta kod üretir. Bu, bir dizi 1'in ardından gelen 0'nin like bir virgül gibi çalıştığı 'virgül kodu'dur.
Hamming notları: gerçek dünya veri sıkıştırması (yedekleme, dosya arşivlenmesi) kaynağın olasılıkları yanlış yönlendirirse, depolama yarı yarıya azalabilir - İngilizce metin bunun mükemmel bir örneğidir.
Huffman vs Blok Kod: Sayısal Karşılaştırma
Hamming'in ikinci örneği: 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.
Blok kod: 8 sembol → her biri 3 bit → L_block = 3.
Hamming, Huffman kodunu hesaplar ve L_Huffman ≈ 2.58 bit olduğunu bildirir.
Kazanç: (3 - 2.58) / 3 ≈ %14 sıkıştırma blok kodlamadan.
Sembol olasılıklarının büyük ölçüde farklı olduğu durumlarda (burada 1/3 karşılaştırın 1/30, burada 10: 1 oran), değişken uzunluklu kodlama önemli ölçüde ödüller sağlar.
Özelleştirilebilir Programlar
Hamming, 11. bölümü sonlandırmakla şaşırtıcı bir fikirle: Huffman encoder kendi kendini kodlayabilir. Şifreleme ağacı (şifreleyiciyi nasıl sıkıştırmayı okuyacağını gösteren) sıkıştırılmış mesajla birlikte iletilir. Alıcı, kodu önceden bilmez.
Şifreleyici: Verileri örnekler, olasılıkları tahmin eder, Huffman kodu oluşturur, şifreleme ağacını bir başlık olarak kodlar ve sonra verileri kodlar.
Şifrelayıcı: Başlığı okuyarak ağacı yeniden oluşturur ve sonra verilere göre kullanır.
Hamming'in noktası: Bu entire döngü, bir kütüphane fonksiyonu olarak çalışabilir ve hiçbir insan katılımı gerektirmez. Çağrı yaptığınızda, otomatik olarak sıkıştırır ve decompresses. Modern arşiv formatları (ZIP, gzip, bzip2) tam olarak bu deseni uygular.
Daha derindeki prensip: zeka algoritmadadır, değil kod tablosu içinde. Algoritma aldığı verilere göre adapte olur. Bu, Hamming'in büyük mühendislik sistemleri üzerinde gördüğü desenle aynıdır: adaptabilit, içe yerleştirilir, değil dışarıya eklenir.