Huffman Optimum Kodu Nasıl İnşa Eder
Hamming, Huffman kodlamasını minimum ortalama uzunluk ön-ek içermeyen bir kod oluşturan açgözlü bir algoritma olarak sunar. Temel fikir: ağacı alttan yukarıya inşa etme, her zaman en düşük olasılıklı iki sembolü birleştirme.
İleri Geçiş (İnşa)
1. Tüm sembolleri olasılığa göre sıralayın, yüksekten düşüğe.
2. En düşük olasılıklı iki sembolü alın. Bunları olasılığı = ikisinin toplamı olan yeni bir meta-sembol içinde birleştirin.
3. Meta-sembolü sıralanmış konumuna ekleyin.
4. Yalnızca iki sembol kalana kadar tekrarlayın.
5. Kalan iki sembole 0 ve 1 atayın.
Geri Geçiş (Kodları Atama)
Birleştirmeleri tersine çevirin: her bölünmede, birleştirilen iki sembol, birleştirilmiş ebeveynleriyle aynı ön-ek bitlerini artı ek 0 (bir çocuk) veya 1 (diğer çocuk) alırlar. 0/1 ataması keyfidir — ikisi de geçerlidir.
Bunun neden optimal olduğu: başka bir kod daha küçük ortalama uzunluğa L' sahip olsaydı, aynı ileri indirgemeyi uygulamak sonunda 1 bitten daha az ortalama uzunluğa sahip iki sembol üretecektir — 2 sembollü bir kod için imkansızdır. Çelişki.
Algoritmayı İzleme
Hamming'den örnek: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125 ile dört sembol A, B, C, D.
İleri geçiş:
Adım 1: Sıralanmış: 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ştirin. 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ştirin.
Adım 4: İki sembol kalır: A(0.5), BCD(0.5). A=0, BCD=1 atayın.
Geri geçiş:
BCD → B 10 alır, CD 11 alır. CD → C 110 alır, 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 benzersiz olmayan iki kaynağını belirtir:
1. Keyfi 0/1 ataması. Her bölünmede, 0'ı her iki çocuğa da verebilirsiniz. 0 ve 1'i her yerde değiştirmek, aynı L'ye sahip farklı bir kod verir.
2. Beraberlik kırma. İki düğüm eşit olasılığa sahip olduğunda, ikisi de 'daha yüksek' yerleştirilebilir (önce birleştirilir). Farklı beraberlik kırma seçimleri, yapısal olarak farklı ağaçlar —'uzun' vs 'geniş' — aynı L ile ancak farklı kod-uzunluğu dağılımları üretebilir.
Uzun vs Geniş
Uzun ağaç (çarpık): her derinlik seviyesinde bir sembol (Fibonacci benzeri yapı). Kod uzunlukları geniş çeşitlilik gösterir: bir sembol kısa bir kod alır, diğerleri daha uzun kodlara basamaklanır.
Geniş ağaç (dengeli): semboller derinlik seviyeleri arasında eşit şekilde dağılır. Kod uzunlukları ortalamaya yakın kümelenirler. Daha düşük varyans.
Hamming'in tavsiyesi: seçim yapma şansınız olduğunda, geniş ağacı tercih edin. Aynı L, ancak kod uzunluklarında daha küçük varyans → daha eşit şekilde kod çözme süresi → gerçek zamanlı uygulamalarda daha küçük arabellek gereksinimi.
Kod-Uzunluğu Varyansını Hesaplama
Kod uzunluklarının varyansı: Var = E[l²] − (E[l])²
p=[0.5, 0.25, 0.125, 0.125] ile {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} kodu için:
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
Eşit olasılıklı semboller için alternatif bir geniş kod, tüm uzunluk-2 kodlarını kullanır: L=2, Var=0.
Sıkıştırma Kazançları vs Sembol Dağılımı
Hamming'in kuralı: Huffman kodlaması yalnızca sembol olasılıkları önemli ölçüde farklı olduğunda kar eder.
Eşit olasılıklar. Tüm 2^k sembolü eşit olasılığa 1/2^k sahipse, Huffman bir blok kod üretir: her sembol k uzunluğu alır. L = H = k. Basit blok kod üzerinde kazanç yok.
Çarpık olasılıklar. Bir sembol baskın ise (diğerleri için p >> 1/2^k), Huffman ona çok kısa bir kod (uzunluk 1 veya 2) atar, L'yi dramatik olarak azaltır.
Virgül kodu (Hamming'in terimi). Her olasılık kalan toplamın 2/3'ünü aştığında, Huffman doğal olarak üretir: p(s1)→0, p(s2)→10, p(s3)→110, ..., sona kadar iki eşit uzunluklu koda kadar. Bu bir 'virgül kodudur': 1'lerin bir dizisinin ardından gelen 0, bir virgül gibi davranır.
Hamming belirtir: gerçek dünyada veri sıkıştırması (yedekleme, dosya arşivleme), kaynak çarpık olasılıklara sahip olduğunda depolamayı yarısından fazla azaltabilir — İngilizce metin birincil örnektir.
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.
Tasarruf: (3 − 2.58)/3 ≈ blok kodlamaya göre %14 sıkıştırma.
Sembol olasılıkları büyük ölçüde farklı olduğunda (burada 1/3 vs 1/30, 10:1 oranı), değişken uzunluklu kodlama önemli ölçüde kar eder.
Kendi Kendini Derleyen Programlar
Hamming Bölüm 11'i çarpıcı bir fikir ile sona erdirir: bir Huffman kodlayıcı kendisini kodlayabilir. Kod çözme ağacı (dekodera sıkıştırılmış mesajı nasıl okuyacağını söyleyen), sıkıştırılmış veri ile birlikte iletilir. Alıcı kodu önceden bilmeye ihtiyaç duymaz.
Kodlayıcı: veriyi örnekler, olasılıkları tahmin eder, Huffman kodunu oluşturur, kod çözme ağacını bir başlık olarak kodlar, ardından veriyi kodlar.
Dekoderı: ağacı yeniden oluşturmak için başlığı okur, ardından bunu kullanarak veriyi kodunu çözer.
Hamming'in noktası: bu tüm ardışık düzen hiçbir insan müdahalesi olmaksızın bir kitaplık işlevi olarak çalışabilir. Onu çağırırsınız, otomatik olarak sıkıştırır ve açar. Modern arşivleme biçimleri (ZIP, gzip, bzip2) tam olarak bu deseni uygular.
Daha derin ilke: zeka algoritmada, sabit bir kod tablosunda değil. Algoritma, aldığı ne olursa olsun veriyi uyarlar. Bu, Hamming'in tüm harika mühendislik sistemlerinde gördüğü desendir: adaptabilite yerleştirilmiş, parçalanmamış.