Huffman Kodlaması

Metin algoritmalarının son sorusu aramadan farklıdır: aynı bilgiyi daha az yerle saklamak.

Sabit uzunluklu kodlama, her simgeye eşit sayıda bit ayırır; Bilgisayarlar Nasıl Çalışır kursundaki karakter kodlamaları bu düzendeydi. Oysa simgeler eşit sıklıkta geçmez. Sık geçene kısa, seyrek geçene uzun kod verilirse toplam uzunluk düşer.

Önek İçermeyen Kodlar

Değişken uzunluk bir belirsizlik doğurur: A → 0, B → 01 atanırsa, 001 dizisi hem AB hem AA… başlangıcı gibi okunabilir.

Çözüm önek içermeyen (prefix-free) koddur: hiçbir simgenin kodu, başka bir simgenin kodunun öneki olamaz. Böyle bir kod tek anlamlı çözülür — okunan bitler bir koda uyduğu anda o simge kesinleşir.

Önek içermeyen kodlar ikili ağaçlarla birebir eşleşir: simgeler yapraklarda durur, kod kökten yaprağa giden yolun bitleridir (sol 0, sağ 1). Yaprakta durma koşulu, önek içermeme koşulunun ta kendisidir.

Bir simgenin kod uzunluğu, yaprağının derinliğidir. Amaç, ağırlıklı derinlik toplamını en küçüklemektir:

$$\text{maliyet} = \sum_{i} f_i \cdot d_i$$

Burada $f_i$ simgenin sıklığı, $d_i$ yaprağının derinliğidir.

Açgözlü Kurulum

Huffman yöntemi, ağacı yapraklardan köke doğru kurar: en seyrek iki simge birleştirilip tek bir düğüm gibi ele alınır ve işlem tek düğüm kalana kadar sürer.

Sezgi şudur: en seyrek iki simge, en derin yaprakları hak eder; onları birleştirmek, maliyeti en az artıran adımdır.

import heapq
from collections import Counter


def huffman_kodlari(sikliklar: dict[str, int]) -> dict[str, str]:
    """Simge → ikili kod eşlemesi."""
    if len(sikliklar) == 1:                      # tek simgeli özel durum
        return {next(iter(sikliklar)): "0"}

    sayac = 0
    yigin: list[tuple[int, int, dict[str, str]]] = []
    for simge, f in sorted(sikliklar.items()):   # belirli sıra: yığın eşitlikte kararsızdır
        heapq.heappush(yigin, (f, sayac, {simge: ""}))
        sayac += 1

    while len(yigin) > 1:
        f1, _, sol = heapq.heappop(yigin)        # en seyrek iki düğüm
        f2, _, sag = heapq.heappop(yigin)
        birlesik = {s: "0" + k for s, k in sol.items()}
        birlesik.update({s: "1" + k for s, k in sag.items()})
        heapq.heappush(yigin, (f1 + f2, sayac, birlesik))
        sayac += 1

    return yigin[0][2]


metin = "ABRACADABRA"
sikliklar = dict(Counter(metin))
print(dict(sorted(sikliklar.items())))
# {'A': 5, 'B': 2, 'C': 1, 'D': 1, 'R': 2}

kod = huffman_kodlari(sikliklar)
print(dict(sorted(kod.items())))
# {'A': '0', 'B': '110', 'C': '100', 'D': '101', 'R': '111'}

En sık geçen A bir bitle, en seyrek C ve D üç bitle kodlanır. Hiçbir kod diğerinin öneki değildir.

Yığına konan üçüncü alan (sayac), eşit sıklıklarda sıralamayı belirli kılar. Bu olmadan kod eşitliklerde çalıştırmadan çalıştırmaya değişebilir; sıkıştırılmış veriyi çözecek tarafın aynı ağacı kurması gerektiğinden bu istenmeyen bir belirsizliktir.

Kazanç ve Çözme

import math


def kodla(metin: str, kod: dict[str, str]) -> str:
    return "".join(kod[karakter] for karakter in metin)


def coz(bitler: str, kod: dict[str, str]) -> str:
    ters = {v: k for k, v in kod.items()}
    sonuc: list[str] = []
    tampon = ""
    for bit in bitler:
        tampon += bit
        if tampon in ters:                # önek içermediği için ilk uyum kesindir
            sonuc.append(ters[tampon])
            tampon = ""
    return "".join(sonuc)


bitler = kodla(metin, kod)
sabit = len(metin) * math.ceil(math.log2(len(sikliklar)))

print(len(bitler), sabit)          # 23 33
print(coz(bitler, kod) == metin)   # True

Beş farklı simge sabit uzunlukla üç bit gerektirir: 33 bit. Huffman kodu aynı metni 23 bitle saklar — yaklaşık üçte bir azalma.

Çözme işlemi, önek içermeme özelliğinin doğrudan sonucudur: biriken bit dizisi bir koda uyduğu anda karar verilir, geri dönüş gerekmez.

Eniyilik

Huffman kodu, simge başına kod atayan yöntemler arasında en küçük toplam uzunluğu verir. Gerekçe iki gözleme dayanır.

Birincisi: Eniyi bir ağaçta, en seyrek iki simge en derin düzeyde ve kardeş olacak biçimde bulunabilir. Değilse, yer değiştirme maliyeti artırmaz — Minimum Kapsayan Ağaç dersindeki değiş tokuş akıl yürütmesinin aynısı.

İkincisi: İki simge birleştirilip tek simge sayıldığında, küçülen problemin eniyi çözümü, özgün problemin eniyi çözümünü verir.

İkisi birlikte, açgözlü seçimin her adımda güvenli olduğunu gösterir. Kurulum maliyeti, öncelik kuyruğu nedeniyle $O(k \log k)$’dir; $k$ farklı simge sayısıdır.

Entropi Sınırı

Ne kadar iyileştirilebileceğinin bir sınırı vardır. Simge olasılıkları $p_i$ iken entropi

$$H = -\sum_i p_i \log_2 p_i$$

simge başına ortalama bit sayısının alt sınırıdır. Huffman kodu bu sınıra yakın çalışır: ortalama uzunluğu $H$ ile $H + 1$ arasındadır.

n = len(metin)
H = -sum((f / n) * math.log2(f / n) for f in sikliklar.values())

print(round(H, 3), round(len(bitler) / n, 3))     # 2.04 2.091

Ölçülen ortalama 2,091 bit, kuramsal alt sınır 2,04 bitin hemen üstündedir. Fark, kod uzunluklarının tam sayı olmak zorunda olmasından gelir; bir simge 1,5 bit alamaz.

Bu sınırın aşılması ancak varsayım değiştirilerek mümkündür — tıpkı karşılaştırmalı sıralamanın alt sınırının anahtar yapısı kullanılarak aşılması gibi. Simgeleri tek tek değil öbekler hâlinde kodlayan yöntemler kesirli bit maliyetine yaklaşır; tekrar eden parçaları sözlükleyen yöntemler ise simge bağımsızlığı varsayımını bırakır ve metindeki tekrarlardan yararlanır. İkincisi, önceki dersteki sonek yapılarıyla doğrudan ilişkilidir.

Sınırlar ve Uygulama Ayrıntıları

Sıklık tablosu gerekir. Kodlama iki geçiş ister: önce sıklıklar sayılır, sonra kodlanır. Ayrıca çözücünün ağacı kurabilmesi için tablo da saklanır; kısa metinlerde bu ek yük kazancı yiyebilir.

Uyarlanabilir değişkeler tabloyu akış ilerledikçe günceller ve tek geçişle çalışır; karşılığında kodlayıcı ile çözücünün tam olarak aynı güncelleme kuralını izlemesi gerekir.

Simge bağımsızlığı varsayılır. Yöntem, bir simgenin bir öncekiyle ilişkisini kullanmaz. Doğal dilde bu ilişki güçlüdür; bu nedenle Huffman genellikle tek başına değil, tekrarları önce eleyen bir aşamanın ardından kullanılır.

Kayıpsızdır. Çözülen veri özgün veriyle birebir aynıdır. Görüntü ve ses için kullanılan kayıplı yöntemler farklı bir aileye aittir ve bu kursun dışındadır.

Özet

• Önek içermeyen kodlar tek anlamlı çözülür ve ikili ağaçlarla birebir eşleşir; kod uzunluğu yaprağın derinliğidir.
• Huffman yöntemi en seyrek iki düğümü birleştirerek ağacı yapraklardan köke kurar; maliyeti $O(k \log k)$’dir.
• Eniyiliği, en seyrek iki simgenin kardeş yapılabileceği değiş tokuş akıl yürütmesine dayanır.
• Ortalama kod uzunluğu entropi ile entropi artı bir arasındadır; fark, bit sayılarının tam sayı olmasından gelir.
• Sıklık tablosunun saklanması, simge bağımsızlığı varsayımı ve iki geçişli yapı yöntemin başlıca sınırlarıdır.

Kurs Kapanışı

Algoritmalar kursu, ölçütle başladı ve uygulamayla bitti. Önce bir çözümün maliyeti tanımlandı: işlem sayımı, asimptotik gösterim, karmaşıklık sınıfları, hesaplama yöntemi ve zaman–alan ödünleşimi. Ardından aynı ölçüt üç alanda kullanıldı — arama ve sıralama, çizge algoritmaları, metin algoritmaları.

Tekrar eden birkaç fikir, kursu tek bir sistem hâline getirir:

• Alt sınır düşünmek. Karşılaştırmalı arama $\Omega(\log n)$, karşılaştırmalı sıralama $\Omega(n \log n)$, entropi $H$: her problemin aşılamayan bir tabanı vardır ve bu taban, ancak varsayım değiştirilerek aşılır.
• Açgözlü seçimi kanıtlamak. Dijkstra, Prim, Kruskal ve Huffman aynı kalıbı paylaşır: seçimin güvenli olduğu bir değiş tokuş akıl yürütmesiyle gösterilir.
• Böl ve yönet. Birleştirmeli sıralama, hızlı sıralama, ikili arama ve ters çift sayımı aynı bağıntıdan doğar.
• Önişleme ödünleşimi. İkili arama, sonek dizisi, KMP tablosu ve karma tabanlı yöntemler, “bir kez öde, çok kez kazan” hesabının farklı biçimleridir.

Sonraki kurs, İşletim Sistemi Kavramları, bu algoritmaların üzerinde çalıştığı katmanı ele alır: süreçler, eşzamanlılık, bellek yönetimi ve dosya sistemleri. Planlama algoritmaları, sayfa değiştirme ve kilitlenme tespiti gibi konularda buradaki çözümleme araçları doğrudan kullanılacaktır.