Huffman kodlaması açıklandı
Bilgisayarlar genellikle her harfi aynı sayıda bitle saklar; düz ASCII'de sekiz bitle. Bu basittir ama savurgandır, çünkü bazı harfler diğerlerinden çok daha yaygındır. 1951'de bir öğrenci, her sembole kendi uzunluğunda bir kod vermenin, yani sık sembollere kısa, nadir olanlara uzun kod vermenin en iyi yolunu, birkaç satıra sığacak kadar basit bir yöntemle buldu. Huffman kodlaması bugün açtığınız neredeyse her sıkıştırılmış dosyanın, görüntünün ve sesin içinde yer alır.
Sık semboller için kısa kodlar
Mors alfabesi bu fikri 1830'larda zaten kullanıyordu: İngilizcenin en yaygın harfi olan E tek bir noktadır, Q ise çizgi, çizgi, nokta, çizgi. Böyle bir kod, bazı semboller diğerlerinden daha sık geçtiğinde zamandan ve yerden tasarruf sağlar. Ama değişken uzunluklar, Morse'un duraklamalarla çözdüğü bir sorunu doğurur: Bir kodun nerede bitip sonrakinin nerede başladığını nasıl bilirsiniz? Ve toplamı olabildiğince küçük tutmak için her sembole hangi uzunluklar verilmelidir?
Önek kodları
Hiçbir kod başka bir kodun başlangıcı değilse ilk sorun ortadan kalkar. A = 0, B = 10, C = 110 ve D = 111 kodlarıyla 0101100 bitleri yalnızca A B C A olarak okunabilir: O ana kadar okunan bitler bir kod oluşturur oluşturmaz o kod tamamlanmıştır. Bu tür önek kodları, sembollerin yapraklarda bulunduğu ikili ağaçlara tam olarak karşılık gelir; bu ağaçlarda her sol dal 0'ı, her sağ dal 1'i temsil eder. Bir kod seçmek bir ağaç seçmektir.
Huffman'ın yöntemi
Her sembol için, ne sıklıkta geçtiğine göre ağırlıklandırılmış bir yaprakla başlayın. En hafif iki ağacı alın ve ağırlığı ikisinin toplamı olan yeni bir düğümün altında birleştirin; tek bir ağaç kalana kadar tekrarlayın. Algoritmanın tamamı bu kadar. Nadir semboller ilk birleştirilir ve uzun kodlarla ağacın derinlerine düşer; sık semboller en son birleştirilir ve kısa kodlarla tepeye yakın kalır. Bir öncelik kuyruğuyla bu işlem, n sembol için n log n ile orantılı süre alır.
Neden optimaldir
Mümkün olan en iyi ağaçta en nadir iki sembol her zaman en derin düzeyde kardeş olarak yerleştirilebilir: Onları orada bulunan herhangi bir şeyle yer değiştirmek toplamı yalnızca kısaltabilir. Onları ağırlıkları toplamıyla tek bir sembolde birleştirin; geri kalanı, bir sembol eksik aynı problemdir. Bu yüzden açgözlü adım en iyi yanıtın yolunu asla kapatmaz. Kullanılan toplam bit sayısı tüm iç düğümlerin ağırlıklarının toplamına eşittir ve birleştirme bu toplamı olabildiğince küçük tutar.
Sınav yerine dönem ödevi
1951'de MIT'de lisansüstü öğrencisi olan David Huffman, Robert Fano'nun bilgi kuramı dersini aldı. Fano öğrencilerine bir seçenek sundu: Final sınavına girmek ya da en verimli ikili kodu bulmak üzerine bir dönem ödevi yazmak. Huffman ödevden neredeyse vazgeçmişti ki ağacı Shannon–Fano yöntemindeki gibi yukarıdan aşağı bölmek yerine aşağıdan yukarı kurmanın her zaman en iyi sonucu verdiğini gördü. Yöntemi 1952'de yayımladı; öğrencinin yöntemi, hocasının Claude Shannon'la birlikte geliştirdiği yöntemi geride bıraktı.
Entropiye yakın
Claude Shannon, hiçbir kodun ortalamada sembol başına kaynağın entropisinden daha az bit kullanamayacağını gösterdi. Bir Huffman kodu, her olasılık yarımın bir kuvveti olduğunda entropiye tam olarak ulaşır ve entropinin sembol başına asla tam bir bit üstüne çıkmaz. Bu fark, bir sembol çok yaygın olduğunda önem kazanır: Payı %99 olan bir sembol, yalnızca yaklaşık 0,015 bit bilgi taşımasına rağmen yine de en az bir tam bite ihtiyaç duyar. Aritmetik kodlama ve yeni sıkıştırıcılardaki asimetrik sayı sistemleri bu sınırdan kaçınır.
Her yerde Huffman kodları
Huffman kodlaması nadiren tek başına kullanılır ama pek çok biçimin son aşamasını oluşturur. ZIP, gzip ve PNG'nin içindeki deflate önce tekrarları göndermelerle değiştirir, ardından sonucu Huffman kodlarıyla yazar. JPEG bunları görüntüyü dönüştürdükten sonra kalan sayılar için, MP3 ses verisi için, faks makineleri de siyah ve beyaz serilerin uzunlukları için kullanır. Biçimler genellikle yalnızca kod uzunluklarının saklanmasının yettiği kanonik bir Huffman kodu gönderir, çünkü kodların kendisi bu uzunluklardan yeniden oluşturulabilir.
Keşfedin
ABRACADABRA, MISSISSIPPI RIVER, kendi cümleniz ya da başka herhangi bir metnin ağacını adım adım oluşturmak için Huffman kodu oluşturucuyu açın. Her adımda en hafif iki ağacın birleşmesini izleyin, kodunu görmek için bir yaprağa tıklayın, bir sembolü kodlanmış bitler boyunca takip edin ve toplamı sabit uzunluklu bir kodla, UTF-8 ve entropiyle karşılaştırın.
Sık sorulan sorular
Huffman kodlaması ile Shannon–Fano kodlaması arasındaki fark nedir?
Shannon–Fano kodlaması ağacı yukarıdan kurar ve sembolleri tekrar tekrar ağırlıkları neredeyse eşit iki gruba böler. Çoğu zaman iyidir ama her zaman optimal değildir. Huffman ise ağacı en hafif iki ağacı birleştirerek aşağıdan kurar ve her zaman mümkün olan en kısa önek kodunu verir.
Kod çözücünün ağaca ihtiyacı var mı?
Evet, aynı koda ihtiyacı vardır. Bu yüzden sıkıştırılmış dosyalar kodu saklar; genellikle kanonik bir kod için kod uzunluklarının listesi olarak, ki bu yalnızca birkaç düzine bayt tutar. Kısa metinlerde bu ek yük tasarrufu aşabilir; oluşturucu yalnızca kodlanmış bitleri sayar.
Huffman kodlaması bir dosyayı büyütebilir mi?
Kodlanmış semboller, aynı semboller için sabit uzunluklu bir koddan asla daha fazla bit kaplamaz. Ama kod tablosunun da saklanması gerekir; bu yüzden çok kısa ya da neredeyse rastgele verilerde sonuç orijinalden biraz büyük olabilir.
Kraft eşitsizliği ne der?
Kod uzunlukları l₁, l₂, … olan bir önek kodunun ancak ve ancak tüm semboller üzerinden 2 üzeri −l değerlerinin toplamı en fazla 1 olduğunda var olduğunu söyler. Her Huffman ağacı gibi en az iki sembollü tam bir ağaç için toplam tam olarak 1'dir.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Huffman kodu oluşturucuyu aç