Huffman kodlaması: ağaç kurma, kodlar, toplam bit

Huffman kodlaması bir metni sıkıştırmak için her karaktere değişken uzunlukta bir bit dizisi verir: sık geçen karakter kısa kod, nadir geçen uzun kod alır. Algoritma greedy’dir: her adımda en küçük iki frekansı birleştirir. Sınavda hemen her zaman aynı soru gelir: “Bu frekanslarla Huffman ağacını kur, kodları yaz, toplam biti hesapla.” Bazen arkasından “şu bit dizisini çöz” ya da “sabit uzunluklu koda göre tasarruf ne?” eklenir.

Altın kurallar:

1. Her adımda kuyruktaki en küçük iki düğümü birleştir. Yeni düğümün ağırlığı ikisinin toplamı.
2. Yeni düğüm kuyruğa geri girer ve sonraki adımlarda bir yaprak gibi yarışır.
3. Sol 0, sağ 1. Hangisinin sola gideceği sorudaki kurala bağlı; yaz ve ona uy.
4. Toplam bit = Σ (frekans × kod uzunluğu).
5. Eşitlik kuralı kodları değiştirebilir, toplam biti asla.

Sabit uzunluk ve değişken uzunluk

6 farklı karakterli 50 karakterlik bir metin düşün. Sabit uzunluklu kodda her karakter için $\lceil \log_2 6 \rceil = 3$ bit gerekir: 50 × 3 = 150 bit. Ama karakterlerin hepsi aynı sıklıkta değil:

C’ye kısa kod, E’ye uzun kod verirsek toplam düşer. Tek koşul: çözülebilirlik. Bunun için kod önek kodu (prefix code) olmalı. Hiçbir kod başka bir kodun başlangıcı olamaz. Kodları bir ikili ağacın yapraklarına koyarsan bu otomatik sağlanır: bir yaprağa giden yol başka bir yaprağa giden yolun başı olamaz, çünkü yaprağın altında başka düğüm yok.

Algoritma

1. Her karaktere bir yaprak, hepsi min-PQ'ya
2. PQ'da birden fazla düğüm varken:
     x = deleteMin   (sol çocuk)
     y = deleteMin   (sağ çocuk)
     z = yeni düğüm: ağırlık x+y, çocuklar x, y
     z'yi PQ'ya ekle
3. Kalan tek düğüm kök

n karakter için tam n−1 birleştirme yapılır. Heap ile her işlem $O(\log n)$: toplam $O(n \log n)$.

Çözümlü örnek

Frekanslar E=2, B=4, D=7, A=10, F=12, C=15. Her satırda kuyruğun sıralı hâlini yaz; sınavda hata yapmamanın en güvenli yolu bu.

kuyruk (sıralı)              birleştir
E2 B4 D7 A10 F12 C15         E2 + B4   = 6
6 D7 A10 F12 C15             6 + D7    = 13
A10 F12 13 C15               A10 + F12 = 22
13 C15 22                    13 + C15  = 28
22 28                        22 + 28   = 50
50                           kök

  merge 1: E(2) + B(4) = 6
  merge 2: (EB)(6) + D(7) = 13
  merge 3: A(10) + F(12) = 22
  merge 4: ((EB)D)(13) + C(15) = 28
  merge 5: (AF)(22) + (((EB)D)C)(28) = 50

3. adıma dikkat: 13 yeni oluştu ama A10 ve F12 ondan küçük, önce onlar birleşti. Yeni düğüm otomatik olarak sıradaki birleştirmeye girmez; sadece ağırlığı en küçük ikiden biriyse girer.

Ağaç (sol kenar 0, sağ kenar 1):

              (50)
            0/    \1
          (22)    (28)
         0/ \1   0/  \1
        A10 F12 (13)  C15
               0/  \1
              (6)   D7
             0/ \1
            E2   B4

Kodları kökten yaprağa giden yoldan oku:

  codes {A=00, B=1001, C=11, D=101, E=1000, F=01} total bits 119 of 50 symbols, avg 2.38

Ortalama kod uzunluğu $119 / 50 = 2.38$ bit. Sabit kod 150 bit tutuyordu; tasarruf 31 bit, yaklaşık %20.7.

İPUCU · toplam biti iki yoldan kontrol et. İç düğümlerin ağırlıklarını topla: 6 + 13 + 22 + 28 + 50 = 119. Her karakterin frekansı, kökten yaprağa giden yoldaki her iç düğümde bir kez sayılır, yani tam olarak kod uzunluğu kadar. İki yol aynı sayıyı vermiyorsa ağaçta hata var.

Kodlama ve çözme (encode / decode)

Kodlama: her karakterin kodunu art arda yaz. FACE → 01 00 11 1000 = 0100111000 (10 bit).

Çözme: bitleri soldan oku, ağaçta kökten aşağı in (0 sol, 1 sağ). Bir yaprağa varınca o karakteri yaz ve köke dön.

bit dizisi: 1001001110100
1 0 0 1   → yaprak B   kök'e dön
0 0       → yaprak A
1 1       → yaprak C
1 0 1     → yaprak D
0 0       → yaprak A
sonuç: BACDA

  decode 1001001110100 -> BACDA
  encode FACE -> 0100111000 (10 bits)

Eşitlik (tie) durumları

Aynı ağırlıkta iki düğüm olursa hangisinin önce çıkacağı tanımlı değildir. Sınavda kural verilir; verilmezse kendi kuralını yaz ve tutarlı uygula. Yaygın kural: “kuyruğa önce giren önce çıkar”, yani yapraklar yeni oluşan iç düğümlerden önce gelir.

Örnek: a=1, b=1, c=2, d=3, e=5.

a1 b1 c2 d3 e5      a1 + b1   = 2
c2 2 d3 e5          c2 + 2    = 4 (c önce)
d3 4 e5             d3 + 4    = 7
e5 7                e5 + 7    = 12

      (12)
     0/  \1
     e   (7)
        0/ \1
        d  (4)
          0/ \1
          c  (2)
            0/ \1
            a   b

  codes {a=1110, b=1111, c=110, d=10, e=0} total bits 25 of 12 symbols, avg 2.0833333333333335

Frekanslar Fibonacci gibi büyüyünce ağaç bir yana yatar ve en nadir karakter n−1 bitlik kod alır. Tersine, tüm frekanslar eşitse (w=x=y=z=4) Huffman sabit uzunluklu koda döner: 00, 01, 10, 11.

TUZAK · c ile (ab) yer değiştirirse? Kodlar değişir (c=111, a=1100 gibi) ama her iki ağaçta toplam 25 bit. Sınavda kodlar kurala göre farklı çıkabilir; hoca toplam biti ve ağacın geçerliliğini kontrol eder. Kuralını cevabının başına yaz.

Neden greedy burada doğru?

İki gözlem yeter:

1. Optimum bir önek kodunda en düşük frekanslı iki karakter en derin seviyede kardeştir. Değilse, daha derindeki bir karakterle yer değiştirmek toplamı artırmaz.
2. Bu iki karakteri tek bir “birleşik karakter” gibi düşünürsen geriye bir eksik karakterli aynı problem kalır (optimal substructure).

Yani “en küçük iki frekansı birleştir” seçimi her zaman bir optimum ağaca götürür.

Java ile kurma

static class Node {
    char ch; int freq; Node left, right;
    Node(char ch, int freq, Node left, Node right) {
        this.ch = ch; this.freq = freq; this.left = left; this.right = right;
    }
}
static Node build(char[] ch, int[] freq) {
    PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
    for (int i = 0; i < ch.length; i++) pq.add(new Node(ch[i], freq[i], null, null));
    while (pq.size() > 1) {
        Node l = pq.poll(), r = pq.poll();
        pq.add(new Node('\0', l.freq + r.freq, l, r));
    }
    return pq.poll();
}

Sık yapılan hatalar

1) E2 + B4   = 6
2) 6  + D7   = 13
3) A10 + F12 = 22
4) 13 + C15  = 28
5) 22 + 28   = 50 (kök)

1) a1 + b1   = 2  (yeni düğüm en sona)
2) c2 + (ab)2 = 4 (c önce girdi, sol)
3) d3 + 4    = 7
4) e5 + 7    = 12

static Node build(char[] ch, int[] freq) {
    PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
    for (int i = 0; i < ch.length; i++)
        pq.add(new Node(ch[i], freq[i], null, null));
    while (pq.size() > 1) {
        Node left = pq.poll();               // en küçük
        Node right = pq.poll();              // ikinci en küçük
        pq.add(new Node('\0', left.freq + right.freq, left, right));
    }
    return pq.poll();
}

static void printCodes(Node n, String code) {
    if (n == null) return;
    if (n.left == null && n.right == null) {
        System.out.println(n.ch + " = " + code);
        return;
    }
    printCodes(n.left, code + "0");
    printCodes(n.right, code + "1");
}