Huffman Sıkıştırma Algoritmasının Optimizasyonu

Bu proje, Huffman sıkıştırma algoritmasını hem çalışma maliyeti hem de ortaya çıkan sıkıştırma oranı açısından incelemek için geliştirdiğim masaüstü uygulamasıdır.

Frekanslardan Önek Koduna

Huffman kodlamasında sembollerin görülme sıklıkları hesaplanır ve düşük frekanslı düğümler aşamalı olarak birleştirilerek ikili bir ağaç oluşturulur. Ağacın yapraklarına giden yollar değişken uzunluklu bit kodlarını belirler.

Sık görülen sembollerin daha kısa, seyrek sembollerin daha uzun kod alması toplam bit sayısını azaltabilir. Kodların prefix-free olması, akışın ayraç eklenmeden tek anlamlı biçimde çözülebilmesini sağlar.

Optimizasyon Problemi

Algoritmanın matematiksel fikri tek başına uygulama performansını belirlemez. Frekans tablosunun oluşturulması, en düşük ağırlıklı düğümlerin seçimi, ağaç yapısı, bitlerin paketlenmesi ve dosya G/Ç maliyeti toplam süreyi etkiler.

Projede hız ve sıkıştırma verimini birlikte izledim. Korunan test kaydında sıkıştırılmış dosya boyutunun başlangıç boyutunun yaklaşık %58'i olduğu belirtiliyor.

Bu oran Huffman algoritmasının genel sıkıştırma oranı değildir. Sonuç tamamen giriş verisinin sembol dağılımına bağlıdır; zaten sıkıştırılmış veya yüksek entropili veri çok az kazanç sağlayabilir.

Teorik Bağlam

Huffman kodlama, kayıpsız ve olasılık/frekans tabanlı bir önek kodlama yöntemidir. Daha geniş algoritma ve veri yapısı çerçevesi Veri Yapıları ve Algoritma Analizi notlarımda yer alır.

Bu tür bir karşılaştırmanın tekrarlanabilir olması için sıkıştırma oranı, encode/decode süresi, bellek tüketimi ve kullanılan test veri kümesi ayrı metrikler olarak raporlanmalıdır.