Huffman Kodlama: JPEG, MP3 ve ZIP'in Arkasındaki Optimum Sıkıştırma Algoritması

1951 yılı, MIT (Massachusetts Institute of Technology). Profesör Robert Fano bilgi teorisi dersinde öğrencilerine bir seçenek sundu: ya zorlu bir final sınavına gir, ya da hâlâ çözülmemiş bir problem üzerinde çalış. David A. Huffman (1925–1999) adındaki bir doktora öğrencisi ikinci seçeneği aldı.

Problemin tarifi şuydu: bir mesaj, harflerden oluşur; her harfin bir sıklığı vardır (Türkçe'de "e" çok sık, "ğ" nadirdir). En kısa toplam uzunlukla bu mesajı ikili koda nasıl çevirebilirsin? Sık harflere kısa kod, nadir harflere uzun kod ver — bu sezgi temeldir; ama "optimum" çözümün matematik formülü neydi?

Huffman bu problemi haftalarca düşündü. Profesörü Fano ve bilgi teorisinin kurucusu Claude Shannon, bu problem üzerinde uzun süredir çalışıyordu; ama optimum çözümü bulamamışlardı. Huffman, problemin çözümüne tersinden yaklaştı: en az sık iki harfi alıp birleştirerek başla. Bu basit fikirden, bugün adıyla anılan Huffman algoritması doğdu.

Huffman, çözümünü 1952'de yayımladı. Sonraki 70 yıl boyunca bu algoritma, modern dünyanın dijital altyapısının görünmez bir parçası oldu. JPEG fotoğraflarınız, MP3 müziğiniz, ZIP arşivleriniz, PNG görüntüleriniz, hatta cep telefonunuzun ses kodlaması — hepsi içinde Huffman kullanır.

Sıkıştırmanın temel sezgisi

Bir kelime düşünün: "MATEMATİK". 9 harf, 7 farklı sembol. Eğer her harfi sabit 8-bit ASCII ile yazarsak: $9 \times 8 = 72$ bit.

Ama harflerin sıklığını kullanırsak daha akıllı olabiliriz. "M" iki kez var, "A" iki kez, "T" iki kez, "E, İ, K" birer kez. Sık olanlara kısa kod, nadir olanlara uzun kod verirsek toplam bit sayısı azalır.

Bu fikrin tarihsel kökeni Morse kodudur (1830-40'lar). Samuel Morse, İngiliz dilindeki en sık harf olan "E"ye en kısa kodu verdi (tek nokta, ·); en nadirine ("Q") uzun kodlar (− − · −). Morse, bu fikirden mesaj iletim süresini ciddi şekilde azalttı.

Morse'un fikri sezgiseldi; optimum değildi. Huffman, matematiksel olarak ispatlanabilir biçimde en iyi sıkıştırmayı veren algoritma sundu.

Huffman algoritması

Algoritma şu şekilde çalışır:

1. Her sembolün sıklığını say. Örnek metin: "MATEMATİK" → M:2, A:2, T:2, E:1, İ:1, K:1.

2. Sıklıklara göre küçük → büyük sırala. Her sembol bir "ağaç düğümü" olur:

   $E(1), İ(1), K(1), M(2), A(2), T(2)$

3. En küçük iki sıklığı al ve birleştir. Yeni bir düğüm oluştur; ağırlığı iki çocuğun toplamı.

   $E(1) + İ(1) → ?(2), K(1), M(2), A(2), T(2)$

4. Yeniden sırala ve adımı tekrarla. En küçük iki sıklığı al, birleştir:

   $K(1) + ?(2) → ?(3), M(2), A(2), T(2)$
   $M(2) + A(2) → ?(4), T(2), ?(3)$
   $T(2) + ?(3) → ?(5), ?(4)$
   $?(4) + ?(5) → ?(9)$ (kök)

5. İkili kod ata. Ağacın her dalında sol = 0, sağ = 1. Her sembol için kök'ten yapraklarına giden yolu yaz.

Sonuç: en sık harflere kısa kod, nadir olanlara uzun kod.

Niçin "optimum"?

Huffman algoritmasının kanıtlanabilir özelliği şudur:

Sembol başına ortalama bit sayısı (kod uzunluğu), herhangi bir önek-koşulu (prefix-free) ikili kodun verebileceği minimum değerdir.

"Önek koşulu" şu demek: hiçbir kodun, başka bir kodun öneki olmaması. Örneğin "01" ve "010" birlikte olamaz, çünkü "01" diğerinin önekidir. Bu koşul, mesajı kodlanmış akıştan tekrar açabilmek için gereklidir.

Bu sınıf içinde, Huffman bilinen en iyi kodu verir. Bu, Shannon'ın bilgi teorisi (1948) ile yakından akrabadır: Shannon, herhangi bir kodun ortalama uzunluğunun entropiden ($H = -\sum p_i \log_2 p_i$) az olamayacağını gösterdi. Huffman algoritması, entropi sınırına çok yakın (genellikle 1 bitten az) bir performans verir.

Bir basit örnek

5 sembollü bir alfabe; sıklıkları: A=0.40, B=0.20, C=0.15, D=0.15, E=0.10.

Sabit-uzunluklu ASCII benzeri kod: her sembol 3 bit (5 sembol için), toplam ortalama: 3 bit.

Huffman kodları:

• A: 0 (1 bit)
• B: 10 (2 bit)
• C: 110 (3 bit)
• D: 1110 (4 bit)
• E: 1111 (4 bit)

Ortalama uzunluk: $0{,}40 \times 1 + 0{,}20 \times 2 + 0{,}15 \times 3 + 0{,}15 \times 4 + 0{,}10 \times 4 = 2{,}25$ bit.

Sıkıştırma oranı: $3 / 2{,}25 = 1{,}33×$ daha verimli.

Entropi: $H = -\sum p_i \log_2 p_i \approx 2{,}19$ bit. Yani Huffman entropi limitinin %97'sine kadar gelmiştir.

Modern dünyada Huffman

Huffman'ın algoritması neredeyse her veri sıkıştırma standardının bir bileşenidir:

• DEFLATE algoritması: ZIP, gzip, PNG, HTTP gzip-encoded içeriği — hepsi LZ77 + Huffman kombinasyonu kullanır.
• JPEG: Görüntü sıkıştırma. Görüntü, DCT (kosinüs dönüşümü) ile frekans bileşenlerine ayrıştırılır; ardından bu bileşenler Huffman ile kodlanır.
• MP3: Ses sıkıştırma. Aynı prensip: MDCT ile frekans alanına geçilir; sonra Huffman.
• MPEG/H.264: Video sıkıştırma. CABAC ve diğer Huffman varyantları kullanır.
• Faks: Eski faks makinelerinin ilk siyah-beyaz görüntü sıkıştırması (modified Huffman) ile başladı.
• TIFF, BZIP2: Çeşitli görüntü/arşiv formatları.

Modern bir akıllı telefon, bir gün boyunca milyonlarca kez Huffman algoritmasının bir varyantını çalıştırır — fotoğraf yüklenmesi, video oynaması, web sayfası açılması, ses kaydı kaydedilmesi, vs.

Sınırlar ve uzantıları

Huffman'ın matematiksel olarak optimum olduğu hâl: sembol sıklıkları biliniyor ve sembollerin frekansları sabit. Gerçek hayatta her zaman böyle değildir; bu yüzden modern uzantılar vardır:

• Adaptive Huffman: Sıklıklar gerçek zamanlı olarak öğrenilir. Akış verisi için uygundur.
• Arithmetic coding: Huffman'dan daha verimli bir alternatif; tamsayı bit sayısına yuvarlama yapmaz, kesirli bit hassasiyeti verir. Modern uygulamada bazı yerlerde Huffman'ı yerinden eder (örneğin H.265 video kodek'inde CABAC).
• Range coding: Aritmetik kodlamanın bir varyantı.
• Asymmetric Numeral Systems (ANS): 2014 sonrası gelişen modern alternatif; Facebook ZStandard ve Apple ProRes RAW gibi sistemlerde kullanılır.

Yine de pratikte Huffman, basitliği ve donanımsal kolaylığı nedeniyle hâlâ varsayılan tercih olur. Bir milyar cihazda çalışacak bir algoritma için, "optimum + sade" çoğu zaman "daha optimum + karmaşık"tan üstündür.

David A. Huffman kimdi?

David A. Huffman, 1925'te ABD'nin Ohio eyaletinde doğdu. MIT'de doktora çalışmasını tamamladıktan sonra MIT ve sonra UC Santa Cruz'da öğretim üyesi oldu. İlginç bir not: Huffman, hayatının kalan kısmında algoritmasından patentleme veya ticaret ile para kazanmadı. Sadece akademik bir profesör olarak yaşadı.

Hayatının diğer önemli ilgi alanları:

• Origami matematiği: Huffman, origami (kağıt katlama) sanatının matematik temelleri üzerine erken araştırmalar yaptı. "Curved-crease origami" (eğri katlamalı origami) yaklaşımları onun çalışmalarıdır.
• Sıralı mantık devreleri: Bilgisayar donanım tasarımı için temel teorik yaklaşımlar.
• Sonlu durum makineleri üzerine eserler.

7 Ekim 1999'da, 74 yaşında kanserden öldü. Mütevazı bir hayat sürdü; ama matematiksel mirası, modern dijital dünyanın görünmez köşelerinde sürekli çalışmakta.

Bir hayat dersi

Huffman'ın hikâyesi, "doğru zamanda doğru problem" şanslılığının matematik tarihinde nasıl tezahür edebildiğini gösterir. Bir doktora öğrencisi, sınavdan kaçmak için bir matematik problem üzerinde yorgun bir gece geçirmek istedi; sonuçta modern dünyanın temel algoritmik araçlarından birini icat etti.

Bu, daha geniş bir hayat dersi: bazen en büyük başarılar, planlanmış kariyer çizgileri yerine "merak edip çözmeye çalışmak" düşüncesinden gelir. Profesörü Fano, Shannon ile yıllarca aynı problemi düşünüyordu; bir doktora öğrencisi, taze gözleriyle bir başka açıdan baktı ve çözümü buldu.

Bir sonraki sefer telefonunuza bir fotoğraf çekip otomatik olarak sıkıştırılması, bir müzik dosyasının indirilmesi, bir web sayfasının açılması — hepsinin arkasında 1951'de bir doktora öğrencisinin yazdığı sade bir algoritmanın çalıştığını hatırlayabilirsiniz. Huffman, modern dijital dünyamızın sessiz bir temel taşıdır.