Huffman Kodlaması

#Nasıl çalışır?

Huffman kodlaması, kayıpsız veri sıkıştırmanın temel yöntemlerinden biridir. Her harfe sabit uzunlukta (ör. 8 bit) kod vermek yerine, sık geçen harflere kısa, nadir harflere uzun kodlar verir.

Kodlar önek-serbesttir (prefix-free): hiçbir kod başka bir kodun başlangıcı değildir. Bu sayede kodlar arasına ayraç koymadan metin tek anlamlı olarak çözülebilir.

Açgözlü kural: her harf, frekansı kadar ağırlıklı tek düğümlü bir ağaçtır. Her adımda en hafif iki ağaç yeni bir düğümün altında birleştirilir. Sonunda kökten bir harfe giden yol o harfin kodudur: sola gitmek 0, sağa gitmek 1. ABRACADABRA için Huffman 23 bit kullanır; 3 bitlik sabit kodla 33 bit gerekirdi.

#Kendin dene

#Adım adım

1. 01Her harfin frekansını say ve her harf için tek düğümlü bir ağaç oluştur.
2. 02En hafif iki ağacı seç (öncelik kuyruğu ile).
3. 03Bunları ağırlıkları toplamı olan yeni bir düğümün altında birleştir.
4. 04Tek ağaç kalana kadar tekrarla; kökten yapraklara giden yollar kodları verir.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

import heapq
from collections import Counter


def huffman_bits(text: str) -> int:
    """Total bits of the Huffman-coded text: each merge adds its weight once per level."""
    heap = list(Counter(text).values())
    heapq.heapify(heap)
    bits = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)  # the two lightest trees
        b = heapq.heappop(heap)
        bits += a + b            # every letter below the new node gets one more bit
        heapq.heappush(heap, a + b)
    return bits


text = "ABRACADABRA"
print(huffman_bits(text))  # 23
distinct = len(set(text))
print(len(text) * (distinct - 1).bit_length())  # a fixed-length code: 3 bits per letter

#Karmaşıklık

n metnin uzunluğu, k farklı harf sayısıdır. k − 1 birleştirmenin her biri öncelik kuyruğunda O(log k) sürer. Huffman, harf başına kod kullanan önek-serbest kodlar arasında toplam uzunluğu en küçük olanı verir; eşit frekanslarda farklı ama aynı uzunlukta kodlar çıkabilir.

#Ne zaman kullanılır?

ZIP/DEFLATE, gzip, PNG, JPEG ve MP3 gibi formatlar sıkıştırmanın bir aşamasında Huffman kodlaması kullanır. Fikir; veri sıkıştırma, iletişimde bant genişliği tasarrufu ve karar ağaçlarının optimizasyonunda da karşımıza çıkar.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.